miércoles, 14 de noviembre de 2018

(401) - Dilema del Barquero en Lógica

En el día de hoy traemos un problema muy conocido de lógica, que tiene, como todo en matemáticas, diez mil una maneras de complicarse.

El problema ha aparecido en series tan conocidas como los Simpson, pero con condiciones más laxas y humorísticas.

El enunciado del problema reza así: Un barquero tiene una pequeña barca y quiere llevar consigo a un lobo, una oveja y una caja de lechugas. Sin embargo la barca solo permite un máximo de dos ocupantes: un remero y un acompañante así que si deja el lobo y la oveja solos, el lobo se como la oveja y si deja la oveja y la caja de lechugas solas, la oveja se come las lechugas. ¿Cómo ha de actuar para «salvar» a los tres?

Razonemos como si fuésemos medio tontos (si es que no lo somos del todo):
  • Si se lleva el lobo, deja la oveja con las lechugas y adiós lechugas. Game over.
  • Si se lleva las lechugas, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva la oveja, deja el lobo con las lechugas y dado que los lobos no comen lechugas, el lobo no interactuará con las lechugas  y el juego sigue.


El barquero llega a la otra orilla, deja la oveja, y se vuelve a la orilla de partida. Ahora tiene dos opciones: o bien se lleva al lobo, o bien se lleva las lechugas. Veamos qué pasa con cada una de ellas:


El lobo primero:
  • Si se lleva el lobo, deja las lechugas solas y el juego sigue. 
Sin embargo cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva la oveja o bien la deja (llevarse el lobo sería volver al paso anterior).
  • Si se va solo, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva la oveja, deja el lobo solo en una orilla y las lechugas en la orilla a la que se dirige y el juego sigue.
No obstante cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva las lechugas o bien las deja (llevarse la oveja sería volver al paso anterior).
  • Si se va solo, deja la oveja con las lechugas y adiós lechugas. Game over.
  • Si se lleva las lechugas, deja la oveja sola en una orilla y el lobo, en la orilla a la que se dirigy el juego sigue.


Cuando llega a la otra orilla deja las lechugas y como ya se ha explicado, el lobo no se come las lechugas y puede volver a la orilla de partida despreocupado para recoger la oveja a moverla por tercera vez de orilla. Una vez que llegan con la oveja, tanto el lobo, como la oveja y la caja de lechugas ya están en la otra orilla y el juego ya ha acabado.

Las lechugas primero:
  • Si se lleva las lechugas, deja el lobo solo y el juego sigue. 
Sin embargo cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva la oveja o bien la deja (llevarse las lechugas sería volver al paso anterior).
  • Si se va solo, deja la oveja con las lechugas y adiós oveja. Game over.
  • Si se lleva la oveja, deja las lechugas solas en una orilla y el lobo, en la orilla a la que se dirige y el juego sigue.
No obstante cuando llega a la otra orilla tiene dos opciones otra vez: o bien se lleva el lobo o bien lo deja (llevarse la oveja sería volver al paso anterior).
  • Si se va solo, deja el lobo con la oveja  y adiós oveja. Game over.
  • Si se lleva el lobo, deja la oveja sola en una orilla y las lechugas, en la orilla a la que se dirigy el juego sigue.


Cuando llega a la otra orilla deja sl lobo y como ya se ha explicado, el lobo no se come las lechugas y puede volver a la orilla de partida despreocupado para recoger la oveja a moverla por tercera vez de orilla. Una vez que llegan con la oveja, tanto el lobo, como la oveja y la caja de lechugas ya están en la otra orilla y el juego ya ha acabado.
(Como se puede apreciar el problema tiene cierto punto de repetitividad).
Visualicemos esto un poco: creemos un sistema de coordenadas de tres ejes (x, y, z) en el que cada variable solo puede tomar dos valores, o bien 0 (que indica que está en la orilla de  partida), o bien 1 (que indica que está en la orilla de  llegada). La variable x indica la posición del lobo, la variable y indica la posición de las ovejas, y la variable z indica la posición de la caja de lechugas.
Siguiendo el método anteriormente descrito, el conjunto de puntos que sigue el barquero en orden es:
  • si se toma el lobo primero en la disyunción anterior (0,0,0) → (0,1,0) → (1,1,0) → (1,0,0) → (1,0,1) → (1,1,1).
  • si se toma la caja primero en la disyunción anterior (0,0,0) → (0,1,0) → (0,1,1) → (0,0,1) → (1,0,1) → (1,1,1).
Nótese que los dos únicos puntos que no son los mismos son los dos intermedios.
Los vectores que definen cada pareja de puntos consecutivos describen un cubo de arista 1, como se puede apreciar en la figura.

Los vectores y puntos-posiciones en el cubo

Los vectores y puntos-posiciones en el espacio

Propongamos ahora una pequeña modificación del problema. Supongamos que aparte del remero, en la barca pueden ir otros dos ocupantes y se quiere llegar a la misma solución que antes, pero mucho más deprisa, por lo que el método anteriormente descrito para un solo ocupante no es el más efectivo ni el óptimo.
Antes se ha jugado con el concepto que el lobo no «reacciona» con las lechugas así que vamos a seguir jugando con esa idea, pues todas las demás se han desechado por el camino.


  • Si se lleva el lobo y las lechugas, deja la oveja sola. Tras esto, pone a esperar el lobo y las lechugas en la otra orilla, se va por la oveja y cuando vuelve el juego ya ha acabado.
También hay una subvariante de este método empezando al revés es decir:
  • Si se lleva la oveja, deja el lobo y las lechugas solos. Tras esto, pone a esperar la oveja en la otra orilla, se va por el lobo y por las lechugas y cuando vuelve el juego ya ha acabado.
De un modo similar al sistema de coordenadas descrito con anterioridad si se hace los mismo, se obtiene:
  • si se toma la pareja primero (0,0,0) → (1,0,1) → (1,1,1).
  • si se toma la oveja primero  (0,0,0) → (0,1,0) → (1,1,1).
Nótese que el único punto que no es el mismo es el intermedio y que comparten cada ruta un vector con el apartado anterior.

Una cosa curiosa que ocurre aquí es que hay vectores que describen la diagonal de caras cuadradas, cosa que antes no pasaba.

Los vectores y puntos-posiciones en el cubo

Los vectores y puntos-posiciones en el espacio
Propongamos ahora otra pequeña modificación al problema. Supongamos que aparte del remero, en la barca pueden ir otros tres ocupantes y se quiere llegar a la misma solución que antes, pero mucho más deprisa, por lo cualquier método anteriormente descrito no sería el más efectivo ni el óptimo.
Antes se ha jugado con el concepto que los tres transportados no interactúan entre sí o intentan comerse en la presencia del barquero.


  • Si se lleva el lobo, la oveja y las lechugas, se lleva todo y cuando llega a la otra orilla el juego ya ha acabado.
De un modo similar al sistema de coordenadas descrito con anterioridad si se hace los mismo, se obtiene (0,0,0)  → (1,1,1).
Una cosa curiosa que ocurre aquí es que el único vector que hay describe la diagonal espacial del cubo, cosa que antes no pasaba.
Los vectores y puntos-posiciones en el cubo
Los vectores y puntos-posiciones en el espacio
Teniendo una configuración de este estilo, de tres elementos [lobo, oveja, lechugas] que cada superior erradica a su estrictamente inferior sin supervisión del barquero. Además, no es posible resolverlo si la barca no admite ningún ocupante sin contar el remero y se resolvería de la misma manera [la última descrita] si tiene un número igual o mayor que tres puestos para ocupantes sin contar el remero.

El problema propuesto en los Simpson tiene la misma temática. He aquí un enlace al Dilema del barquero por los Simpson.

Próximamente vendrá otro problema de lógica y barcas, algo más difícil y mucho menos conocido.



AutorĐɑvɪẟ Ƒernández-De la Cruʒ.