This one is know as the ‘missionaries and cannibals’ or ‘jealous husbands’ problem. There are three missionaries and three cannibals who need to cross a river. Their boat can carry two people at a time, and cannot be sent across the river without someone to row it. If cannibals outnumber missionaries on either of the banks of the river, then those missionaries will be eaten. How does everyone get across the river?
In the ‘jealous husbands’ version of the problem, it’s three women and their three husbands, and no woman may be in the presence of a man without her husband there. You might like to think about why solving this problem would also solve the ‘missionaries and cannibals’ version. Show answer
For the first step, we can’t take two missionaries across because then the remaining missionary would be outnumbered by the cannibals. We can’t take a single person because then they’d have to come straight back to get the boat over. We can either take a missionary and a cannibal, or two cannibals. Either way is fine; I’m going to draw the first one: Now if we leave the missionary there and bring the cannibal back, then the missionaries on the left bank will be outnumbered, so we have to take the missionary back. (If we had chosen to take two cannibals across for the first step, one would have to come back and it’d have the same result as this choice.) Now we can’t take two missionaries across, because the third would be outnumbered on the left bank. And we can’t take one missionary and one cannibal, because the missionary would be outnumbered on the right bank. Taking a single person across would take us back to where we were last move. The only remaining option is to take two cannibals across. And then take one cannibal back. We need to take two missionaries across so that they’re not outnumbered on the right bank. Then we need to take a missionary and a cannibal back so no missionaries get eaten. The only option is to take two missionaries across. And take the cannibal back. The rest is easy.
In the jealous husbands problem, it’s impossible for the women to outnumber the men, because if there were more women than men on a bank of the river then one of the women would be in the presence of a man without her husband there. So if we change the women to cannibals and the men to missionaries, then any solution to the jealous husbands problem is also a solution to the missionaries and cannibals problem. It’s very common in mathematics that two problems that seem unrelated on the surface are actually the same underneath.