Rock Star Shuffle

A concert starts in seventeen minutes and four guys must all cross a 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 one or two people) must have the flashlight with them. The flashlight must be walked back and forth. It cannot be thrown etc. Each person walks at a different speed. A pair must walk together at the rate of the slower man's pace.

Bandmate	Time to cross
Bono	1 minute
Edge	2 minutes
Adam	5 minutes
Larry	10 minutes

For example, if Bono and Larry walk across first, ten minutes have elapsed when they get to the other side of the bridge. If Larry then returns with the flashlight, a total of twenty minutes have passed and you have failed the mission. Note: there are two known answers to this problem.

This problem has circulated for some time. We first heard of it from Van Ma at Nicholls State University about a year before this submission.

Need a hint? Click here.

Click here for the complete solution.

Hint 1

This kind of problem is worked by trial and error, so the intellectual challenge is to think of ways to cut down the number of trials. Try this: without worrying about who goes when, think about the number of trips that might be needed and what the time of each trip might be. For example, any trip including Larry is a 10-minute trip, so there is at least one 10-minute trip.

Hint 2

One way to cut down the number of trials is to make some plausible assumptions.

• Let's assume the solution requires exactly 17 minutes (the problem only asks for 17 minutes or less, but "problem psychology" tells us that if it could have been done in 16 minutes, they would have asked for 16 minutes).
• There have to be at least 5 trips, because each round trip across the bridge and back can only increase the number of persons on the far side by 1 (the trip across can increase it by 2, but then 1 has to come back). So after 2 round trips we have at most 2 people on the far side, and the remaining 2 could come on the next one-way trip, for a total of 5 trips. So let's assume the solution can be done in exactly 5 trips.

The possible trip times are 1, 2, 5, and 10 minutes. What are some feasible combinations of 5 numbers, taken from these four (with repetitions allowed), that add up to 17?

Hint 3

As a shorthand let's write T1, T2, T5, T10 for the band members who need 1, 2, 5, and 10 minutes to cross, so that T1 = Bono, T2 = Edge, T5 = Adam, T10 = Larry. We know T10 has to make at least one trip, so one of the numbers in the sum is 10. He can't make two trips, because the sum would be at least 20, which is larger than 17. So excluding T10's trip we have 4 trips left and 7 minutes to make them in. We also know there are not any 5-minute trips, because there would only be 2 minutes left, and we have to make 3 more trips of at least 1 minute each. So the remaining 7 minutes has to be made in 4 trips of 1 or 2 minutes each, and the only solution is 1 trip of 1 minute and 3 trips of 2 minutes. Therefore we know the times for the trips are 1, 2, 2, 2, 10 (not necessarily in that order). We're doing a good job of cutting down the number of trials; now see what feasible sequences of trips there are using these times.

The Rest of the Solution

We have five trips; the first, third, and fifth are across and the second and fourth are returning. We know T10 makes 1 trip, and there is no trip of length 5, so T5 must travel with T10. Their trip across cannot be the first trip (because one of them would have to bring the flashlight back), and cannot be the fifth trip (because one of them would have had to bring the flashlight back on the fourth trip), so their trip must be the third trip.

The first trip must have two people, because otherwise it would be useless (the one person would have to come back on the second trip). So the first trip must be T1 and T2. On the second trip one of them has to return, and in fact either choice of T1 or T2 works: We have the solutions (and times)

1. T1, T2 across (2)
2. T1 return (1)
3. T5, T10 across (10)
4. T2 return (2)
5. T1, T2 across (2)

and

1. T1, T2 across (2)
2. T2 return (2)
3. T5, T10 across (10)
4. T1 return (1)
5. T1, T2 across (2)

References

• Our solution is based on a problem and solution by Alexander Bogomolny that appears on his web site Cut the Knot!, a site that offers clever solutions to intricate mathematical problems.
• A generalization to N persons is The Generalized U2-Flashlight Microsoft 5-Minute Puzzle by Shalosh B. Ekhad and Doron Zeilberger.
• Wikipedia has an article on the similar Bridge and Torch Problem.