There are 3 missionaries and 3 cannibals who need to cross a river. The boat can only hold 2 people at a time. If the cannibals ever outnumber the missionaries on either side of the river, the missionaries will be eaten. How can they all cross safely?
Answer
Two cannibals cross to the right bank (Left: 3M, 1C; Right: 0M, 2C) One cannibal returns to the left bank (Left: 3M, 2C; Right: 0M, 1C) Two cannibals cross to the right bank (Left: 3M, 0C; Right: 0M, 3C) One cannibal returns to the left bank (Left: 3M, 1C; Right: 0M, 2C) Two missionaries cross to the right bank (Left: 1M, 1C; Right: 2M, 2C) One missionary and one cannibal return to the left bank (Left: 2M, 2C; Right: 1M, 1C) Two missionaries cross to the right bank (Left: 0M, 2C; Right: 3M, 1C) One cannibal returns to the left bank (Left: 0M, 3C; Right: 3M, 0C) Two cannibals cross to the right bank (Left: 0M, 1C; Right: 3M, 2C) One cannibal returns to the left bank (Left: 0M, 2C; Right: 3M, 1C) Two cannibals cross to the right bank (Left: 0M, 0C; Right: 3M, 3C) All missionaries and cannibals have safely crossed to the right bank, and at no point did the cannibals outnumber the missionaries on either bank (except when there were 0 missionaries on that bank).