Life by Bits & Numbers

This problem is similar to the missionaries and cannibals problem puzzle. One additional twist to the missionaries and cannibal problem in this problem is the fact that rather than being all the same, men and women have roles and although it appears to complicate the solution, it really does not.

Problem:

Three jealous husbands and their wives need to cross a river. They find a small boat that can contain no more than two persons. Find the simplest schedule of crossings that will permit all six people to cross the river so that none of the women shall be left in company with any of the men, unless her husband is present. It is assumed that all passengers on the boat unboard before the next trip and at least one person has to be in the boat for each crossing.

I’ve encountered some interesting problem which is famous mainly because it has much to do with AI (Artificial Intelligence) development. The problem is called “Missionaries and Cannibals”. The description is:

“Three missionaries and three cannibals come to a river. A rowboat that seats two is available. If the cannibals ever outnumber the missionaries on either bank of the river, the missionaries will be eaten. How shall they cross the river?”

The following statement  – “If the cannibals ever outnumber ” means that cannibals can’t outnumber missionaries while counting anyone in moored boat. (otherwise the problem is simple)

The problem has an elegant and pretty easy solution, yet it is usually hard to humans because humans don’t do a formalization of the problem which leads to many repeated states. This issue is mainly why this problem is popular. Amarel (1971) considered several representations of the problem and discussed criteria whereby the following representation is preferred for purposes of AI and why this problem is hard for humans.

Solution

1. How can we choose one out of 3 christmass presents with equal probabability?  Or in other words how to obtain 1/3 probability by using one unbiased coin ?
2. Solve the previous problem if the coin is biased and the bias is uknown.

Solution