Bridge and torch problem

Premise

Image by Rob Cuthbertson, released under GFDL

The premise is that the Beatles are trying to get to their concert, but find themselves on the wrong side of an impassible river during a pitch-black night. The only way across the river is a narrow bridge. The bridge can't hold more than 2 people at a time, and they only have one flashlight. John can cross the bridge in one minute, Paul takes two minutes, George takes five minutes and Ringo takes seven minutes. When two men cross the bridge together, they must move at the slower man's pace. For example, Paul and George can cross the bridge, taking five minutes. George can then return the flashlight to the other side, taking another five minutes, for a total of ten minutes elapsed time.

Can they all get across the bridge in 15 minutes or less?

Solution

A common first insight is that the cost of returning the flashlight to the remaining men is an unavoidable expense, so clearly that expense should be minimized. This strategy makes John the flashlight bearer, shuttling each band member across the bridge:

Elapsed Time	Remote Side	Action	Concert Side
0	J P G R
2	G R	J+P cross forward, taking 2 min	J P
3	J G R	J return, taking 1 min	P
8	R	J+G cross forward, taking 5 min	J P G
9	J R	J return, taking 1 min	P G
16		J+R cross forward, taking 7 min	J P G R

While it is important to minimize the cost of returning the flashlight, the solution has more to do with minimizing wasted capacity on the bridge. If John crosses the bridge with Ringo, the trip takes seven minutes, effectively wasting six minutes of John's time. If George crosses with Ringo, the trip still takes seven minutes, but only wastes two minutes of George's time. To solve the problem in 15 minutes (or less) the crossing must be ordered to reduce the wasted time:

Elapsed Time	Remote Side	Action	Concert Side
0	J P G R
2	G R	J+P cross forward, taking 2 min	J P
3	J G R	J return, taking 1 min	P
10	J	G+R cross forward, taking 7 min	P G R
12	J P	P return, taking 2 min	G R
14		J+P cross forward, taking 2 min	J P G R

Variations

This puzzle has been updated to a U2 Concert, e.g. rec.puzzles thread (Google Groups)