There is a river which has to be crossed using a boat that can accommodate only two persons at a time. On one side are three missionaries and three cannibals. All of them must reach the other side. Also in no condition should greater number of cannibals be left with less number of missionaries or they will eat them.
How will they cross the river?
Solution:
Side A = 3 Cannibals, 3 missionaries
Side B = 0 Cannibals, 0 missionaries
1 cannibal and 1 missionary goes in the boat
Side A = 2 Cannibals, 2 missionaries
Side B = 1 Cannibals, 1 missionaries
1 missionary returns back and 2 cannibals go there
Side A = 0 Cannibals, 3 missionaries
Side B = 3 Cannibals, 0 missionaries
1 cannibal returns and 2 missionaries go
Side A = 1 Cannibals, 1 missionaries
Side B = 2 Cannibals, 2 missionaries
1 missionary and 1 cannibal return and 2 missionaries go
Side A = 2 Cannibals, 0 missionaries
Side B = 1 Cannibals, 3 missionaries
One cannibal back, two cannibals go
Side A = 1 Cannibals, 0 missionaries
Side B = 2 Cannibals, 3 missionaries
One cannibal back, two cannibals go
Side A = 0 Cannibals, 0 missionaries
Side B = 3 Cannibals, 3 missionaries
Thus all have crossed successfully