A group of $N$ fugitives is running away from the police. They reach a very narrow bridge. Since it's dark and they have a single flashlight, they can only cross the bridge in pairs. The $i^{th}$ fugitive takes $T_i$ minutes to cross the bridge. When a pair of fugitives crosses the bridge, they must go at the speed of the slowest fugitive. In other words, the crossing time for the pair of fugitives $(i,j)$ is $\max\{T_i,T_j\}$.

After a pair of fugitives crosses the bridge, one of those who already crossed must return with the flashlight so that another pair of fugitives can go too (this new pair can include the fugitive who just brought back the flashlight). The process goes on until everyone has crossed the bridge.

If the police is $T_p$ minutes behind the prisoners, and assuming they can no longer safely escape unless all of them have crossed the bridge by the time the police gets to it, can they make it? If yes, how?

I was asked this question during a job interview and found it very interesting, so I decided to write a brute-force solver for this problem and discuss it here.

The problem only becomes interesting if $N \ge 3$. Indeed, if $N = 2$ the two fugitives will make it as long as $\max\{T_1,T_2\} \le T_p$, meaning if the slower fugitive needs longer than $T_p$ to cross the bridge, the police will arrive before they can safely flee. The case $N = 1$ is excluded as we would have a single fugitive crossing the bridge, but the statement of the problem says they should cross it (to the safe side) in pairs (so $N \ge 2$).

NOTE: readers who just wish to play with the brute-force solver should go directly to the end of this post. If you are interested in the discussion of the problem, read on!

Let's first compute the number of steps $S_N$ which must happen until all $N$ fugitives have crossed the bridge. A step can be either a pair of fugitives crossing the bridge or one fugitive returning. We will prove that: $$ \boxed{ S_N = 2N - 3 } $$

To see this, notice first that for $N = 2$ we have only one step (the two fugitives cross the bridge), so the equation above applies since $S_2 = 1$. Now assume the formula formula is valid for $N-1$ fugitives. Then, for $N$ fugitives, after the first two cross and one returns with the flashlight (in other words, after two steps), we have $N-1$ fugitives left to cross the bridge. From there on, there are $S_{N-1}$ steps until all fugitives have crossed. So: $$ S_N = S_{N-1} + 2 = \left[2(N-1) - 3\right] + 2 = 2N-3 $$ as we wanted to prove.

Now let's compute the theoretical maximum number of possibilities that one has to try when using brute force to solve the problem. First notice that if $N$ fugitives have not yet crossed the bridge, the number of possible pairs for crossing it is: $$ \left(\matrix{N \\ 2}\right) = \frac{N(N-1)}{2} $$

When a fugitive must return with the flashlight, and if $M$ fugitives have already crossed the bridge, then the number of choices is, well... $M$.

We will therefore have the scheme shown below. I have marked the side which has the flashlight in green; "crossed" refers to the number of fugitives which have already crossed the bridge while "must still cross" refers to the fugitives which must still cross it:

The maximum number of moves $P_N$ which a brute-force solver must simulate is then: $$ \begin{eqnarray} P_N & = & \displaystyle\frac{N(N-1)}{2}\cdot 2\cdot \frac{(N-1)(N-2)}{2} \ldots (N-2) \frac{3\cdot 2}{2} (N-1) \frac{2 \cdot 1}{2} \nonumber \\[5pt] & = & \left[2 \ldots (N-2)(N-1)\right]\left[\displaystyle\frac{N(N-1)}{2}\frac{(N-1)(N-2)}{2} \ldots \frac{3\cdot 2}{2} \frac{2 \cdot 1}{2}\right] \nonumber \\[5pt] & = & (N-1)! \displaystyle \frac{N(N-1)^2(N-2)^2 \ldots 3^2 \cdot 2^2 \cdot 1}{2^{N-1}} \nonumber \\[5pt] & = & (N-1)! \displaystyle \frac{N^2(N-1)^2(N-2)^2 \ldots 3^2 \cdot 2^2}{2^{N-1}N} \nonumber \\[5pt] & = & \displaystyle\frac{(N-1)!}{2^{N-1}N} (N!)^2 \end{eqnarray} $$ and therefore: $$ \boxed{ P_N = \displaystyle\frac{N!^3}{2^{N-1}N^2} }\label{post_eeb0a9ec9ceed243221955dad220b478_num_possibilities} $$

The table below shows the values of $P_N$ for some values of $N$:

From the numbers above and from equation \eqref{post_eeb0a9ec9ceed243221955dad220b478_num_possibilities}, it is clear that the computational work required to simulate all possibilities grows extremely fast ($N!$ grows much faster than both $2^{N-1}$ and $N$). This will impose a limitation on how many fugitives ($N$) we can have when trying to solve the problem using brute force. The solver can be made more efficient, however, if it uses recursion and only keeps on going down a given branch of possibilities as long as the total crossing time has not yet exceeded the police time on that branch (for the picky reader: recursion will not be a problem here as the number of fugitives will hardly exceed a dozen). Also, the solver can be made more efficient by not distinguishing between fugitives which take the same time to cross the bridge.

Now, to the brute-force solver! On the text fields below, enter the times taken by each fugitive to cross the bridge and the time the police will take to reach it. The values must be separated by commas (the values already entered are the ones I received on my job interview). If two or more fugitives take the same amount of time to cross the bridge, the solver will not output solutions with the same numbers twice.