Misioneros y caníbales

Tres misioneros y tres caníbales deben cruzar un río con una barca que solo transporta como máximo dos personas. En ninguna orilla puede quedar un grupo donde los caníbales sean más que los misioneros (si hay misioneros presentes), porque entonces los devoran.

¿Cómo cruzan todos de forma segura?

1. En todos los estados intermedios, cuando hay misioneros en una orilla, nunca quedan en minoría frente a los caníbales.
2. Notación: (M, C mid M, C) = (izquierda | derecha).
3. Sí, y se puede hacer en 11 cruces.

**Respuesta:** Sí, y se puede hacer en 11 cruces.

**Notación:** $(M, C \mid M, C)$ = (izquierda | derecha).

Estado inicial: $(3,3 \mid 0,0)$

1. $CC \rightarrow$ $(3,1 \mid 0,2)$
2. $C \leftarrow$ $(3,2 \mid 0,1)$
3. $CC \rightarrow$ $(3,0 \mid 0,3)$
4. $C \leftarrow$ $(3,1 \mid 0,2)$
5. $MM \rightarrow$ $(1,1 \mid 2,2)$
6. $MC \leftarrow$ $(2,2 \mid 1,1)$
7. $MM \rightarrow$ $(0,2 \mid 3,1)$
8. $C \leftarrow$ $(0,3 \mid 3,0)$
9. $CC \rightarrow$ $(0,1 \mid 3,2)$
10. $C \leftarrow$ $(0,2 \mid 3,1)$
11. $CC \rightarrow$ $(0,0 \mid 3,3)$

En todos los estados intermedios, cuando hay misioneros en una orilla, nunca quedan en minoría frente a los caníbales.

---