Acertijo de los misioneros y los caníbales

En el acertijo de los misioneros y los caníbales, tres misioneros y tres caníbales tienen que cruzar un río con una barca que solo puede llevar como máximo dos personas, con la limitación de si existen misioneros presente en tierra, no puede pueden estar con un mayor número de caníbales, porque los caníbales se comerían a los misioneros. La barca no puede cruzar por el río sin personas a bordo. Y, en algunas variaciones, uno de los caníbales o misioneros tiene sólo un brazo y no puede remar.^[1]

En el acertijo de los maridos celosos, hay tres matrimonios, con la limitación que ninguna mujer puede estar en la presencia de otro hombre a no ser que su marido también esté presente. Bajo esta limitación no puede haber más mujeres que hombres en un banco del Río, porque si es así, alguna iría sin su marido. Por tanto, al cambiar de hombres a misioneros y de mujeres a caníbales, cualquier solución al acertijo de los maridos celosos servirá como solución al acertijo de los misioneros y los caníbales.^[1]

Un sistema para solucionar el acertijo de los misioneros y los caníbales para el cual el estado está representado con un vector sencillo ⟨m, c, b⟩. Los elementos del vector representan el número de misioneros, caníbales, y si la barca es en el lado equivocado del río (el objetivo es pasar tanto misioneros como caníbales al lado correcto), respectivamente. Como la barca y todos los misioneros comienzan en el otro lado equivocado del río, el vector está inicializado a ⟨3,3,1⟩. Las acciones usan el vector suma/resta para modificar el vector de estado. Por ejemplo, si un caníbal cruza el río, el vector ⟨0,1,1⟩ sería restado del vector de estado y quedaría ⟨3,2,0⟩. El vector de estado reflejaría que hay todavía quedan tres misioneros y dos caníbales en el lado equivocado del río, y que la barca está ahora en el banco opuesto. Para resolver el problema completamente, un árbol sencillo está formado con el estado inicial como la raíz. Las cinco acciones posibles (⟨1,0,1⟩, ⟨2,0,1⟩, ⟨0,1,1⟩, ⟨0,2,1⟩, y ⟨1,1,1⟩) son restadas del estado inicial, con el resultado formando nodos hijos. Cualquier nodo que tenga más caníbales que misioneros en cualquier banco es en un estado nulo, y no es vuelto a considerar. Los nodos hijos válidos generados sería ⟨3,2,0⟩, ⟨3,1,0⟩, y ⟨2,2,0⟩. Para cada nodo restante, nodos hijos serán generados añadiendo cada uno de los posibles vectores de acción. El algoritmo continúa alterando entre adición y sustracción para cada nivel del árbol hasta que exista un nodo generado con el vector ⟨0,0,0⟩. Este es el estado objetivo, y el camino de la raíz del árbol a este nodo representa una secuencia de acciones que soluciona el problema.

La solución más temprana conocida al problema de los maridos celosos, utiliza 11 viajes, como sigue. Los pares casados están representados como α (hombres) y a (mujeres), β y b, y γ y c., p. ^291[4]

Esta es la solución más corta para el acertijo, pero no es la única.^[4]

Si de otra forma, solo un hombre puede salir del bote a la vez y los maridos deben de estar en la orilla para que cuenten que están con sus esposas en lugar que cuenten desde que está en el bote en la misma orilla: los movimientos del 5 al 6 son imposibles, porque tan pronto como γ salga del vote, b en la orilla no estará con su marido, a pesar de que su marido este en el bote.

Como se mencionó anteriormente, esta solución al problema de maridos celoso serviría como solución al problema de los misioneros y los caníbales reemplazando hombres por misioneros y mujeres por caníbales. En este caso podemos ignorar las identidades individuales del misioneros y caníbales. La solución dada seguiría siendo corta, y es a de las cuatro soluciones más cortas.^[5]

Si una mujer está en la barca en la orilla (pero no en la orilla) cuenta como estar sola (p.e. no en presencia de hombres en la orilla), entonces este rompecabezas puede ser solucionado en sólo 9 viajes de un solo sentido:

Una variación obvia es la del número de parejas celosas (o misioneros y caníbales), la capacidad de la barca, o ambos. Si la barca aguanta 2 personas, entonces 2 pares requieren 5 viajes; con 4 o más pares, el problema no tiene ninguna solución.^[6] Si la barca ^puede aguantar 3 personas, entonces hasta 5 pares pueden cruzar; si la barca puede aguantar 4 personas, cualquier número de pares puede cruzar., p. ³⁰⁰.^[4] Un sencillo graph-aproximación de teoría a analizar y solucionando estas generalizaciones estuvo dada por Fraley, Cooke, y Detrick en 1966.^[7]

Si es añadida una isla en medio del río, entonces cualquier número de pares puede cruzar al utilizar una barca de dos personas. Si cruces de amontonar al banco no es dejado, entonces 8n−6 viajes de una maneras están requeridos a transbordador n pares a través del río;, ^p. ⁷⁶ si están dejados, entonces 4n+1 viajes están requeridos si n supera 4, a pesar de que una solución mínima requiere sólo 16 viajes si n equals 4., p. ⁷⁹.^[1] Si las parejas celosos están reemplazados por misioneros y caníbales, el número de los viajes requeridos no cambia si cruces de amontonar al banco no es dejado; si son aun así el número de disminuciones de viajes a 4n−1, suponiendo que n es al menos 3., p. ⁸¹.