Crossing a River: Cannibals and Missionaries

Date: 10/15/2001 at 21:40:32
From: A.J.
Subject: Extended Word Prblem

Three missionaries and three cannibals wish to cross a river using a 
single boat that will hold only two people. If at any time the 
cannibals outnumber the missionaries, those missionaries will be 
eaten. How can the crossing be safely made?

I tried to solve this problem by drawing pictures and trying to make 
the cross, but couldn't come up with an answer. I keep getting stuck 
with the fact that the person in the boat counts too. It is obvious 
that two people go over and one has to bring the boat back. If a 
missionary and a cannibal go first and the missionary goes back and 
picks up a cannibal and takes him over (remember there is already one 
cannibal already there), then there will be two cannibals and one 
missionary.  

No matter what I try missionaries always get eaten.  

Please help!

Date: 10/16/2001 at 13:06:54
From: Doctor Rob
Subject: Re: Extended Word Prblem

I like to draw a diagram like those below. 

There are two ways to start, either with a missionary and a cannibal 
in the boat, or with two cannibals in the boat. At each step after the 
first, without undoing what you have just done, there are either just 
one or just two possible things that can happen without any eating, so 
you can work your way through the process. Once you have two 
cannibals, two missionaries, and the boat on the far side, send one 
missionary and one cannibal back, then reverse the order of the 
previous steps.

Here is one way to start:

    CCCMMM          --
              CM->
    CCMM            CM
            <-M
    CCMMM           C
              CC->
    MMM             CCC
            <-...
    ...             ...


- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/