Recall the
classic bridge crossing puzzle. Let the crossing times of the four people be represented by A, B, C, and D with 0<A<B<C<D. If the speeds of the four people are distinct random values when is the trivial solution (A escorts everyone else across) faster than the solution required in the classic puzzle?
The trivial solution involves the following 5 crossings:
AB
A
AC
A
AD
for a total elapsed time of 2A+B+C+D
The Classical solution has the following crossings:
AB
B
CD
A
AB
for a total elapsed time of A + 3B + D
The trivial solution is faster if
2A+B+C+D < A + 3B + D.
Simplifying, the trivial solution is faster if A + C < 2B
If A = 1 minute, B = 2, C = 5 and D = 10, then the trivial solution is not the fastest, because A + C > 2B
Solution
