Six friends, Alex, Ben, Cal, Dan, Elmer and Frank need to cross a river in a small canoe. The canoe can only carry a maximum of 130 kg.
Al weighs 120 kg, Ben weighs 110 kg, Cal weighs 90 kg, Dan weighs 80 kg, Elmer weighs 50 kg, Frank weighs 40 kg and they have 20kg of supplies.
How do they get across in a minimum number of steps?
You don't need a computer at all!
The 20kg of supplies don't matter, there are plenty of opportunities to take them across with a trip that is not fully loaded, such as when Ben crosses solo.
Al and Ben only travel solo.
Cal and Frank can share the canoe.
Any pair of Dan, Elmer, and Frank can share the canoe.
To get Al and Ben over the basic strategy is to send a pair of Dan, Elmer, and Frank over and have one come back, then one of Al or Ben crosses and the other of the original pair comes back. (This is much like the classic Four People at a Bridge puzzle.)
To be explicit one way is: Elmer and Frank cross, Elmer returns, Al crosses, Frank returns. Then repeat with Ben in place of Al. Eight trips so far.
After the two heavyweights cross we can turn to the rest of the group. Starting with Frank taking Cal across and Frank returns. Two more trips, up to 10 trips total.
Finally any pair of Dan, Elmer and Frank cross; one of them returns to pick up the last person. These three trips get us to the final total of 13 trips.
Solution
