Christmas Streak 14/88: Safely Cross The River

That $k=11$ is a well-known result. If $(c,m)$ represents the state where there are $c$ cannibals and $m$ missionaries on the starting bank, we need to move from state $(3,3)$ to state $(0,0)$ . If the cannibals and missionaries are indistinguishable (except, of course, as being cannibals or not), there are exactly $4$ ways of making the trip in $k=11$ moves, shown in the diagram below:

Since the cannibals and missionaries are distinguishable, each leg of the journey can be achieved in a number of ways, and these are indicated by the red weights on each leg. For example, to move from $(3,3)$ to $(2,2)$ , one cannibal and one missionary need to be chosen out of a choice of three of each, and this can be done in $9$ ways. Thus $n \; = \; (9 \times 1 + 3 \times2)\times1\times3\times3\times4\times1\times1\times3\times(3\times1 + 2\times1) \; = \; 8100$ making the answer $11 \times 8100 = \boxed{89100}$ .

Consider the grid above. C represents the cannibals, and M represents the missionaries.

The grid shows how many cannibals and missionaries are on the starting riverside.

Since there shouldn't be more cannibals than missionaries, $(2,~1),~(3,~1),$ and $(3,~2)$ should be removed.

And since there shouldn't be more cannibals than missionaries on the other side too, $(1,~2),~(1,~3),$ and $(2,~3)$ should be removed.

---

When the boat is going away from the starting riverside, only the moves depicted above is possible.

And when the boat is returning to the starting riverside, only the moves depicted above is possible.

When crossing to the other side, we can easily find out that the dotted line and the normal line should be used alternatively.

---

Knowing that, and after trying some moves, we notice that the above moves are compulsory to move from the right area to the left area.

Let's draw this to calculate the number of cases.

$\begin{aligned} \color{#D61F06}CC\color{#333333}MMM & | C\\\\ MMM & | CC\color{#D61F06}C & \small \color{#3D99F6}\text{3 ways to select one C}\\\\ CM\color{#D61F06}MM &| CC & \small \color{#3D99F6}\text{3 ways to select two M's}\\\\ CM &| C\color{#D61F06}C\color{#333333}M\color{#D61F06}M & \small \color{#3D99F6} \text{4 ways to select one C and one M}\\\\ CC\color{#D61F06}MM &| CM \\\\ CC &| \color{#D61F06}C\color{#333333}MMM \\\\ C\color{#D61F06}CC &| MMM & \small \color{#3D99F6} \text{3 ways to select two C's}\\\\ C &| CCMMM \end{aligned}$

So the compulsory path has $3\times 3\times 4\times 3=108$ cases.

---

Then all we have to do is start from $(3,~3)$ and arrive to $(2,~3)$ using dotted line in the end.

Then we see that there are two possible cases.

$\begin{aligned} CC\color{#D61F06}C\color{#333333}MM\color{#D61F06}M & | &\small \color{#3D99F6}\text{9 ways to select one C and one M}\\\\ CCMM &| C\color{#D61F06}M \\\\ CCMMM &| C \end{aligned}$

9 cases possible.

---

$\begin{aligned} C\color{#D61F06}CC\color{#333333}MMM &| &\small \color{#3D99F6} \text{3 ways to select two C's}\\\\ CMMM &| C\color{#D61F06}C &\small \color{#3D99F6} \text{2 ways to select one C}\\\\ CCMMM &| C \end{aligned}$

6 cases possible.

---

So there are 15 ways to go from $(3,~3)$ to $(2,~3).$

Using the same method, there are 5 ways to go from $(1,~0)$ to $(0,~0).$ (Note that it's not symmetrical!)

Therefore, there are a total of $5\times 108\times 15=8100$ ways to cross the river, and it takes $11$ moves.

$\therefore~nk=11\times8100=\boxed{89100}.$