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.

As I’ve mentioned in the problem statement, this problem is quite hard for humans and might be very easy for a machine to solve (with the right formalization of course). The reason is that this problem can contain infinitely many repeated states. If we don’t keep track of states we have been in, we could easily end up going in rounds with the same man in the boat for infinity. Thus, we have to keep track of states we have been in, and do not repeat them, since getting back to them, means that all the “progress” we made has put us back, and therefore was useless.

Another thing to pay attention is that it really doesn’t matter which one of the missionaries will we get into the boat first/second or third. This is also true regarding the cannibals. In fact this small note saves us a lot of states space, making this problem very simple indeed, when treated properly.

Therefore, if you still want to try solve it, try drawing all possible situations while not distinguishing any importance given to the order between different missionaries and cannibals, and keeping track of repeated states as well.

Solution:

MMMCCC  |   |

Missioner and a Cannibal go, Missioner comes back

MMMCC  |   |  MC      MMMCC  |   |  C

Two Cannibals go, one comes back

MMM  |   |  CCC    MMMC |   |  CC

Two missioners go, Missioner and a Cannibal come back

MC  |   |  CCMM     MMCC  |   |  CM

Two missioners go, the cannibal brings the boat back

CC  |   |  CMMM    CCC  |   |  MMM

Now all the cannibals can get to the other shore easily one by one: two go, one comes back.

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

Problem:

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 ?

Solution:

1. The coin is UNbiased: toss the coin twice. Let TH, HT and HH correspond to each of the presents. In case of HH – repeat from the beginning.

2. The coin is biased, then we notice that TH and HT would occur with equal probability but this will only give us 2 possible outcomes with equal probability and we need 3.  Then we would have to use 4 tosses which will give us 16 possible combinations. The question is which ones we should choose to represent the presents (or outcomes). The only condition is that the number of H and T should be the same to ensure equal probability for each outcome and thus selecting each present with the same probability. One option would be to assign HTHT, THTH and HTTH to the three choices, with other  13 possible 4-toss outcomes being rejected.

Discussion:

So the obvious problem is that we need some way to extrapolate tosses of a single coin to (possibly) arbitrary number of outcomes with equal probability to obtain each outcome.  So obviously we will need several tosses to match the number of outcomes we need. However we need to pay careful attention to the fact that the toss sequences we are using have the same combined probability such as HHTT and HTHT

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