Six friends Al, Ben, Cal, Dan, Elmer and Frank want to cross a bridge. It is a very dark night but there is only one torch between the six of them. The bridge is narrow so that only two people at a time can cross it. It is known that:
Al takes exactly 1 minute to cross the bridge.
Ben takes exactly 2 minutes to cross the bridge.
Cal takes exactly 4 minutes to cross the bridge.
Dan takes exactly 7 minutes to cross the bridge.
Elmer takes exactly 12 minutes to cross the bridge.
Frank takes exactly 19 minutes to cross the bridge.
When two people cross the bridge, they do so with the pace of the slower person.
Determine the minimum amount of time it will take all six friends to cross the bridge.
Method 1
The simple method is to have Al escort everyone across.
Al and Ben cross, Al comes back - 2+1 min
Al and Cal cross, Al comes back - 4+1 min
Al and Dan cross, Al comes back - 7+1 min
Al and Elmer cross, Al comes back - 12+1 min
Al and Frank cross - 19 min
This adds up to 2+1+4+1+7+1+12+1+19 = 48 minutes.
Method 2
An alternate method (which the classic 1,2,5,10 puzzle uses) is to have the people pair up - Al and Ben; Cal and Dan; Elmer and Frank.
Al and Ben cross, Al comes back - 2+1 min
Cal and Dan cross, Ben comes back - 7+2 min
Al and Ben cross, Al comes back - 2+1 min
Elmer and Frank cross, Ben comes back - 19+2 min
Al and Ben cross - 2 min
This adds up to 2+1+7+2+2+1+19+2+2 = 38 minutes.
Method 3a
It might be possible to speed this up more by mixing the two methods - Have Elmer and Frank cross as a pair and Al escorts the other three.
Al and Ben cross, Al comes back - 2+1 min
Al and Cal cross, Al comes back - 4+1 min
Al and Dan cross, Al comes back - 7+1 min
Elmer and Frank cross, Ben comes back - 19+2 min
Al and Ben cross - 2 min
This adds up to 2+1+4+1+7+1+19+2+2 = 39 minutes.
Method 3b
Mix it up the other way - Have Cal and Dan cross as a pair and Al escorts the other three.
Al and Ben cross, Al comes back - 2+1 min
Cal and Dan cross, Ben comes back - 7+2 min
Al and Ben cross, Al comes back - 2+1 min
Al and Elmer cross, Al comes back - 12+1 min
Al and Frank cross - 19 min
This adds up to 2+1+7+2+2+1+12+1+19 = 47 minutes
Conclusions
The optimum method in this case appears to be Method 2, which finishes in 38 minutes.
Method 3a is very close, and if Cal were to have a 2.5 minute speed then Method 3a would then have a time of 37.5 minutes where Method 2 would still take the same 38 minutes.
Comparing methods
