The Generalized U2-Flashlight Microsoft 5-Minute Puzzle

Shalosh B. EKHAD^{1} and Doron ZEILBERGER ^{1}

Abstract: The celebrated U2-flashlight puzzle, allegedly posed by Microsoft to job applicants, who were required to solve it in 5 minutes, is generalized from four people to an arbitrary number of people, with general crossing times, and then completely solved (in linear time).

Theorem: If n people have to cross a (at most) two-person bridge, and they are equipped with one flashlight, and their times of crossing are a_{1} < … < a_{n}, and when two people go together, they walk at the slower’s pace, then the shortest possible total time for everyone to cross the bridge, let’s call it A_{n}(a_{1}, …, a_{n}), equals

B_{n}(a_{1}, …, a_{n}) := {min \atop 0 ≤ r ≤ [n/2] − 1} [ (n − 2 − r)a_{1} + (2r + 1)a_{2} + ∑_{i=3}^{n−2r} a_{i} + ∑_{i=0}^{r−1} a_{n−2i} ] .

Proof: Obviously a_{n} should only cross once. If his companion is to return, he should be the fastest, a_{1}, whereas, if he is to never return, you can’t go wrong by making him a_{n−1}. But in the latter case, two scouts should be sent first, one of whom will come back with the flashlight, and the other one to bring it latter back. You can’t go wrong by making these scouts a_{1} and a_{2}, hence we have the obvious recurrence, when n > 3:

A_{n}(a_{1}, …, a_{n}) = min ( a_{1} + a_{n} + A_{n−1}(a_{1}, …, a_{n−1}) , a_{1} + 2a_{2} + a_{n} + A_{n−2}(a_{1}, …, a_{n−2}) ) ,

subject to the obvious initial conditions A_{2}(a_{1}, a_{2}) = a_{2}, A_{3}(a_{1}, a_{2}, a_{3}) = a_{1} + a_{2} + a_{3}. But it is purely routine to see that the same recurrence, and initial conditions, are satisfied with A replaced by B.

If the winner in the above minimum was r, then one possible way the crossing could be done is with the 2r slowest people crossing first in pairs, {a_{n}, a_{n−1}}, {a_{n−2}, a_{n−3}}, … with the two fastest (a_{1} and a_{2}) serving as scouts, followed by a_{1} leading in turn, the remaining n−2r −1 people, returning each time to fetch another guy. In particular, A_{4}(1, 2, 5, 10) = min(19, 17) = 17, with r = 1.

1 Department of Mathematics, Temple University, Philadelphia, PA 19122, USA. [ekhad, zeilberg]@math.temple.edu

http://www.math.temple.edu/~[ekhad,zeilberg]/ , Sept. 29, 1998. Supported in part by the NSF. This article is accompanied by a Maple package GetMicrosoftJob available from the second author’s website. We thank Dr.

Jane Legrange for bringing the Microsoft puzzle to our attention. This puzzle, discussed in the forum alt.brain.teasers goes as follows: U2 has a concert that starts in 17 minutes and they must all cross a rope bridge to get there. All four men begin on the same side of the bridge. You must help them across to the other side. It is night. There is one flashlight. A maximum of two people can cross at one time. Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown, etc. Each band member walks at a different speed. A pair must walk together at the rate of the slower man’s pace. The rates are:

Bono - 1 minute to cross, Edge - 2 minutes to cross, Adam- 5 minutes to cross, Larry- 10 minutes to cross.