Three missionaries and three cannibals wish to cross a river.
There is a boat that can carry up to three people,
and both the missionaries
and the cannibals can row the boat.
However, the cannibals can never outnumber the missionaries (either in the boat
or on shore) or the cannibals will feast upon the missionaries.
What is the smallest number of trips needed to make the crossing?
Here is the answer:
Five crossings are needed.
(1) Send 3 cannibals across.
(2) Then 1 cannibal comes back.
(3) Then 3 missionaries row across.
(4) Then 1 missionary comes back.
(5) The missionary and cannibal row across.