17
$\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.

Improve this question
$\endgroup$
2
  • $\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$
    – user88
    May 15, 2014 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, 2014 at 18:23

4 Answers 4

Reset to default
13
$\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.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Re There's no way to get a similar arrangement for anything greater than three - You're gonna need a bigger boat! $\endgroup$
    – Steve
    May 12, 2021 at 14:59
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ You misspelled "ferry", just so you know. $\endgroup$
    – user88
    May 15, 2014 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, 2014 at 20:07
  • $\begingroup$ In a more roundabout way than that, to be sure. $\endgroup$
    – user88
    May 15, 2014 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$
    – user88
    May 15, 2014 at 20:11
  • $\begingroup$ @JoeZ. - ok, think I accounted for that. How does it look now for M>C. $\endgroup$
    – AJ Henderson
    May 15, 2014 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

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ This only solves the case where C=M=3. The question asks for a general solution. $\endgroup$
    – f''
    May 12, 2016 at 16:16
-2
$\begingroup$

Why can't you just send one missionary and one cannibal on each trip? Cannibals can never outnumber missionaries, but they can be equal right?

So send 1 cannibal and missionary and you're done in 3 trips.

Improve this answer
$\endgroup$
1
  • 3
    $\begingroup$ Welcome to PSE! Especially with older puzzles, it's pretty important to review the question and existing answers before adding a new answer. In this case, your solution cannot work, because "The boat cannot cross the river by itself with no people on board." $\endgroup$
    – Jeremy Dover
    Jul 19, 2020 at 20:05

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