15
$\begingroup$

In the Missionaries and Cannibals problem:

Three missionaries and three cannibals must cross a river using a boat which can carry at most two people, under the constraint that, for both banks and the boat, if there are missionaries present on the bank (or the boat), they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries). The boat cannot cross the river by itself with no people on board.

The shortest solution for this puzzle has 11 one-way trips.

What should be the strategy to solve this puzzle for M missionaries and C cannibals, given that M is not less than C, or else the puzzle wouldn't be solvable.

$\endgroup$
  • $\begingroup$ Is it even possible to do with more than three of each? I've never heard a solution to the problem for four missionaries and four cannibals. $\endgroup$ – Joe Z. May 15 '14 at 18:22
  • $\begingroup$ There is a good discussion of a tree approach in the Wikipedia article you link to. The first reference is to an article that probably answers the question very nicely, but it is behind a paywall. $\endgroup$ – Ross Millikan May 15 '14 at 18:23
11
$\begingroup$

Let's define a b * c d to represent the state of the river at any given time: a missionaries and b cannibals on the left, c missionaries and d cannibals on the right, and * being < if the boat is on the left and > if the boat is on the right.

The problem starts out in the state M C < 0 0, and we want to get 0 0 > M C.

For the case of M being more than C, here's an algorithm to transfer 1 missionary and 1 cannibal at a time:

  • Bring 1 missionary and 1 cannibal over. (M-1 C-1 > 1 1)
  • Bring the cannibal back. (M-1 C < 1 0; since M > C, M-1 >= C, as required.)
  • Bring 1 missionary and 1 cannibal over again. (M-2 C-1 > 2 1)
  • Bring a missionary back. (M-1 C-1 < 1 1).

And then you're left with the case of M-1 missionaries and C-1 cannibals on one side of the river. Just keep repeating this procedure (it works by induction) until you have only missionaries on the left side of the river. Then you're home free.

For M equal to C, I don't think you'll have a solution for M > 3, because the solution for M = 3 already depends on the fact that you can have only cannibals on one side and they won't be able to do anything to the missionaries no matter how many there are on one side.

The part of the solution where this applies looks something like this:

  • 3 1 < 0 2
  • 1 1 > 2 2
  • 2 2 < 1 1
  • 0 2 > 3 1

There's no way to get a similar arrangement for anything greater than three, because you can't send enough missionaries at once to balance out the rest of the cannibals.

$\endgroup$
2
$\begingroup$

For the case of more M than C it becomes trivial as a canibal can run the ferry after some initial setup. It starts with 1 M and 1C in the boat with C+1 M on the original shore. The M takes the boat back and gets another M, leaving C Ms on the original shore, The Ms get to the other side and send the C back with the boat. The C can now ferry alternating C's and Ms without issue. The Ms will always outnumber the number left on either shore.

If M is 2 or more higher than C, then M can actually run the boat as well since they can start with 2 Ms in the boat and keep a higher number on both shores simultaneously while also operating the boat.

$\endgroup$
  • $\begingroup$ You misspelled "ferry", just so you know. $\endgroup$ – Joe Z. May 15 '14 at 20:06
  • $\begingroup$ I'm sorry. I still don't understand :D. Are you suggesting that 3 people leave (2M + 1C) and 1M returns? A boat can carry at most two people. $\endgroup$ – John Bupit May 15 '14 at 20:07
  • $\begingroup$ In a more roundabout way than that, to be sure. $\endgroup$ – Joe Z. May 15 '14 at 20:09
  • $\begingroup$ A missionary can't just ferry people there and back. There's a bit of subtlety there that you missed. $\endgroup$ – Joe Z. May 15 '14 at 20:11
  • $\begingroup$ @JoeZ. - ok, think I accounted for that. How does it look now for M>C. $\endgroup$ – AJ Henderson May 15 '14 at 20:21
0
$\begingroup$

Here's a foolproof solution:

One missionary and one cannibal cross to the other side,
The cannibal gets out and the missionary comes back
Missionary gets out of the boat, two cannibals get in and cross
One cannibals gets out and the other cannibal goes back
The cannibal gets out and two missionaries get in and cross
One missionary gets out, the other missionary stays in the boat and one cannibal gets in and goes back.
The cannibal gets out and two missionaries get in and cross
The two missionaries get down and the cannibal gets in the boat and goes back
One cannibal gets in and they both cross but only one cannibal gets out
The other cannibal in the boat goes back, collects the other cannibal, they cross and they get out.

And you should have won

$\endgroup$
  • 1
    $\begingroup$ This only solves the case where C=M=3. The question asks for a general solution. $\endgroup$ – f'' May 12 '16 at 16:16
-2
$\begingroup$
  1. Two cannibals go across (leaving one cannibal and three missionaries on home side)
  2. One cannibal stays and one returns (leaving one cannibal on other side)
  3. Cannibal and Missionary go across.
  4. Missionary stays and cannibal returns (leaving one missionary and one cannibal on other side)
  5. Both two remaining Missionaries go across (leaving two cannibals at home)
  6. The one cannibal on other side returns to home (leaving three missionaries on other side)
  7. Two cannibals go across to other side. One stays.
  8. One returns. (leaving three missionaries and one cannibal on other side)
  9. The remaining two cannibals go across to other side.
$\endgroup$
  • 3
    $\begingroup$ Hi Charley, welcome to Puzzling Stack Exchange. The question you have posted an answer on wasn't looking for the solution where there are 3 cannibals and 3 missionaries. It did, in fact, contain a link to the optimal solutions for that case. It was actually looking for a solution to the general case of M missionaries and C cannibals. $\endgroup$ – Gordon K Nov 6 '15 at 0:50
  • $\begingroup$ Also, in move 3 you're assuming that not getting off the boat is equivalent to not being on the shore. Otherwise, there'd be 2 cannibals and 1 missionary on the other bank after move 3. $\endgroup$ – John Bupit Nov 8 '15 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.