When do missionaries and cannibals problems have solutions?

Question

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, if there are missionaries present on the bank, they cannot be outnumbered by cannibals (if they were, the cannibals would eat the missionaries).

Is there are way to know when a missionaries or cannibals problem has a solution or not (that is assuming that a solution means that no missionaries can be eaten and that boats can only carry two people)?

I have written a program that uses bfs to find possible solutions, and cannot seem to find a solution for 5 missionaries and 5 cannibals. It has worked for other missionaries and cannibals problems, so I'm not sure if my program is flawed or if there is just no solution. Its pretty obvious that in some situations (i.e. 1 missionary, 10 cannibals) there is no solution.

As a follow-up, would it be possible to shed some light on the situations in which missionaries must be eaten. Is there a way to find the minimum number of missionaries that can be eaten in a certain missionaries or cannibals problem?

Answer 1

I think there is a solution to the Missionaries and Cannibals problem when there are five of each, illustrated below, where everyone starts on the left bank, and the center spaces represent the boat and the right represents the opposite bank.

MMMMMCCCCC __ __________  
MMMMMCCC   CC __________  
MMMMMCCC   C_ C  
MMMMCCC    CM C  
MMMMCCC    C_ MC  
MMMCCC     CM MC  
MMMCCC     C_ MMC  
MMMCC      CC MMC  
MMMCC      C_ MMCC  
MMCC       CM MMCC  
MMCC       C_ MMMCC  
MMC        CC MMMCC  
MMC        C_ MMMCCC  
MC         CM MMMCCC  
MC         C_ MMMMCCC  
C          CM MMMMCCC  
C          C_ MMMMMCCC  
__________ CC MMMMMCCC  
__________ __ MMMMMCCCCC

If you want to go through and check my logic, you can, but I think the trick is to always have a cannibal in the boat, that way, on both banks there is either an equal number of cannibals and missionaries, or there is one more missionary than cannibal. (Except in the first few steps to set this up, where there is one cannibal by themselves).

That's kind of the reason for the (outdated and kinda racist) choice of Missionaries and Cannibals as the things going back and forth. Both are capable of piloting the boat on their own.

Other versions of river crossing puzzles have different constraints on how the boat can be moved. For example, this one reminded me of a setup with a farmer trying to move sheep and wolves, where the wolves cannot outnumber the sheep. The difference there is that the farmer steers the boat, and this allows 'empty' crossings, where the boat is on the other side of the river despite not carrying a sheep or a wolf there. Similarly, you could do people and wolves, which is again slightly different from the Cannibal problem, because a wolf cannot cross the river on its own.

Answer 2

The real idea behind the missionaries (Ms) and cannibals (Cs) is actually taking all missionaries to the other side first then the cannibals. Here is a small diagram to show how more than 3 on both side makes the problem impossible:

To do that you first attempt taking two Cs to the other side (let's call it side B), and go back take another C as you see in the first two lines. after getting 2 Cs on side B, the only way taking any M to the side B taking two Ms. so lastly we do that. Actually there is also one more possibility which requires moving M and C at the beginning, but the actual idea (putting two Cs to the other side) does not change.

As a result there is a little equilibrium where you can only take M and C to the beginning side:

so After going back with M and C, the only possible way to move back to the side B is with two Ms. Any other combination will kill an M at least. And at the same time, you will have no Ms left on the side A and the rest is just taking all Cs one by one.

So adding even one M and C to the team will make the game impossible. Because in the second figure, you see the equilibrium and put one M and C to the first side. So you will never take the last M whatever you do actually. Let's see why with figure:

This is where you cannot do anything. You cannot move alone C, you cannot move alone M, the only possible movement becomes M and C to the sides.

As a result:

It is impossible to solve this problem with more than $3$ Ms and Cs and the maximum amount of M you can take to the side B is $3$ whatever setup you have where there are of course the same amount of Ms and Cs.

Answer 3

A sufficient condition to have a solution is when

There are 2 more missionaries than cannibals.

This is how:

One missionary enters the boat, then he ferries one missionary, one cannibal, one missionary, one cannibal, etc, finishing with one missionary.

I believe with only one more missionary than cannibals you cannot have arbitrarily large groups.

But GoblinGuide did even better:

In fact with just one extra missionary there still is a solution.

The following diagram demonstrates his trick:

    MCMCMCM
            >CM>
    MCMCM            CM
            <C<
    MCMCMC            M
            >MC>
    MCMC            MCM
            <M<
    MCMCM            CM
            >CM>
    MCM            CMCM
            <C<
    MCMC            MCM
            >MC>
    MC            MCMCM
            <M<
    MCM            CMCM
            >CM>
    M            CMCMCM
             <C
    MC            MCMCM
            MC>
                MCMCMCM