The Same Six, a Bigger Boat
The puzzle
Three missionaries and three cannibals must cross a river, under the same rule as before: cannibals must never outnumber missionaries on a bank where any missionary stands. This time the boat carries three.
What is the fewest crossings, and how do you know you cannot do better?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
Count the net transfer. A forward trip moves at most three people over; a return trip brings at least one back.
Hint 2
Send the cannibals first - a bank with no missionaries cannot go wrong.
Show the answer Hide the answer
Five crossings, and five is the minimum because four could move at most five people across.
How to get there
All three cannibals cross, leaving the near bank with three missionaries and the far bank with three cannibals and no missionary - safe. One cannibal rows back: near (3,1), far (0,2).
All three missionaries cross: near (0,1), far (3,2), both safe. One cannibal rows back: near (0,2), far (3,1). The last two cannibals cross. Five crossings, and no rule was ever close to breaking.
Five is forced. Crossings alternate forward and back, so an odd number is needed, and with three forward trips and two returns the best possible net transfer is 3 + 3 + 3 - 1 - 1 = 7, which covers six people. Three crossings could manage at most 3 - 1 + 3 = 5 people, one short. So five it is.
The technique worth keeping
Before searching, bound the answer by net flow: forward capacity times forward trips, minus the minimum that must come back. It tells you when to stop looking for something shorter, and it is often the only proof of optimality a crossing puzzle admits.