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
< 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.
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.