Rompecabezas de vertido de agua

Los rompecabezas de vertido de agua (también llamados problemas de jarras de agua , problemas de decantación , ^{[ 1 ] [ 2 ]} rompecabezas de medición o rompecabezas de Duro de Matar con Venganza ) son una clase de rompecabezas que involucra una colección finita de jarras de agua de capacidades enteras conocidas (en términos de una medida de líquido como litros o galones ). Inicialmente, cada jarra contiene un volumen entero conocido de líquido, no necesariamente igual a su capacidad.

Los acertijos de este tipo preguntan cuántos pasos de verter agua de una jarra a otra (hasta que una jarra se vacíe o la otra se llene) son necesarios para alcanzar un estado objetivo, especificado en términos del volumen de líquido que debe estar presente en alguna jarra o jarras. ^{[ 3 ]}

Según la identidad de Bézout , estos rompecabezas tienen solución si y solo si el volumen deseado es un múltiplo del máximo común divisor de todas las capacidades de volumen enteras de las jarras.

Es una suposición común, incluida en estos acertijos, que las jarras tienen formas irregulares y no están marcadas, por lo que resulta imposible medir con precisión cualquier cantidad de agua que no las llene por completo. Otras suposiciones comunes incluyen que no se puede derramar agua y que cada paso del proceso de verter agua de una jarra de origen a una de destino se detiene cuando la jarra de origen está vacía o la de destino está llena, lo que ocurra primero.

El rompecabezas estándar de este tipo funciona con tres jarras de 8, 5 y 3 litros de capacidad. Inicialmente, estas se llenan con 8, 0 y 0 litros, respectivamente. En el estado final, deben llenarse con 4, 4 y 0 litros. El rompecabezas se puede resolver en siete pasos, pasando por la siguiente secuencia de estados (denotada como una terna entre paréntesis de los tres volúmenes de agua en las tres jarras):

[8,0,0] → [3,5,0] → [3,2,3] → [6,2,0] → [6,0,2] → [1,5,2] → [1,4,3] → [4,4,0].

Cowley (1926) escribe que este rompecabezas en particular "se remonta a la época medieval" y señala su aparición en el libro de texto de matemáticas de Bachet del siglo XVII.

Dado que las reglas solo permiten detenerse/girar en los límites de la cuadrícula cartesiana (es decir, cuando cada jarra está a su máxima capacidad), las únicas acciones reversibles (reversibles en un paso) son:

• Transferir agua de una jarra llena a cualquier jarra.
• Transferir agua de cualquier jarra a una jarra vacía.

Las únicas acciones irreversibles que no se pueden revertir en un solo paso son:

• Transferir agua de una jarra parcialmente llena a otra jarra parcialmente llena.

Al limitarnos únicamente a acciones reversibles, podemos construir la solución al problema a partir del resultado deseado. Desde el punto [4,4,0], solo hay dos acciones reversibles: transferir 3 litros de la jarra de 8 litros a la jarra vacía de 3 litros [1,4,3] y transferir 3 litros de la jarra de 5 litros a la jarra vacía de 3 litros [4,1,3]. Por lo tanto, solo hay dos soluciones a este problema:

[4,4,0] ↔ [1,4,3] ↔ [1,5,2] ↔ [6,0,2] ↔ [6,2,0] ↔ [3,2,3] ↔ [3,5,0] ↔ [8,0,0]

[4,4,0] ↔ [4,1,3] ↔ [7,1,0] ↔ [7,0,1] ↔ [2,5,1] ↔ [2,3,3] ↔ [5,3,0] ↔ [5,0,3] ↔ [8,0,0]

Las reglas a veces se formulan añadiendo un grifo (una "jarra" de origen con agua infinita) y un fregadero (una "jarra" de desagüe que acepta cualquier cantidad de agua sin límite). Llenar una jarra hasta el borde desde el grifo o verter todo el contenido de la jarra en el desagüe cuenta como un paso para resolver el problema. Esta versión del rompecabezas apareció en una escena de la película de 1995 Duro de Matar 3: La Venganza . ^{[ 4 ]} Esta variante tiene una solución óptima que se puede obtener utilizando un diagrama baricéntrico con forma de billar (o un billar matemático). ^{[ 5 ]}

El gráfico muestra dos maneras de obtener 4 litros usando jarras de 3 litros y 5 litros, y una fuente de agua y un sumidero en una cuadrícula cartesiana con líneas diagonales de pendiente − 1 (de tal manera que${\displaystyle x+y=const.}$En estas líneas diagonales, que representan el vertido de agua de una jarra a otra, los ejes x e y representan las cantidades en las jarras de 5 y 3 L, respectivamente. Partiendo de (0, 0), recorremos la cuadrícula a lo largo de los segmentos de línea, girando solo en sus límites, hasta llegar a la línea negra que indica 4 L en la jarra de 5 L. Las líneas continuas indican el vertido entre jarras, las líneas discontinuas indican el llenado de una jarra y las líneas punteadas indican el vaciado de una jarra.

Al concatenar cualquiera de las soluciones, recorrer la línea 4L y realizar la operación inversa de la otra solución, se regresa a (0, 0), lo que genera un grafo cíclico . Si y solo si los volúmenes de las jarras son coprimos , se visita cada punto límite, lo que proporciona un algoritmo para medir cualquier cantidad entera hasta la suma de los volúmenes.

Como se muestra en la sección anterior, podemos construir la solución al problema a partir del resultado deseado utilizando únicamente acciones reversibles (vaciar una jarra llena en el fregadero y llenar una jarra vacía del grifo son acciones reversibles). Para obtener 4 litros utilizando jarras de 3 y 5 litros, queremos llegar al punto (4, 0). Desde el punto (4, 0), solo hay dos acciones reversibles: llenar la jarra vacía de 3 litros del grifo (4,3) o transferir 3 litros de agua de la jarra de 5 litros a la de 3 litros (1,3). Por lo tanto, solo hay dos soluciones al problema:

(4, 0) ↔ (4, 3) ↔ (5, 2) ↔ (0, 2) ↔ (2, 0) ↔ (2, 3) ↔ (5, 0) ↔ (0, 0)

(4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

El grafo cíclico puede representarse mediante pares ordenados conectados por acciones reversibles:

(0, 0) ↔ (5, 0) ↔ (2, 3) ↔ (2, 0) ↔ (0, 2) ↔ (5, 2) ↔ (4, 3) ↔ (4, 0) ↔ (1, 3) ↔ (1, 0) ↔ (0, 1) ↔ (5, 1) ↔ (3, 3) ↔ (3, 0) ↔ (0, 3) ↔ (0, 0)

que contiene todos los estados posibles que se pueden alcanzar con una jarra de 3 litros y una jarra de 5 litros. El estado (1, 2), por ejemplo, es imposible de alcanzar desde un estado inicial de (0, 0), ya que en (1, 2) ambas jarras están parcialmente llenas y no es posible realizar ninguna acción reversible desde este estado.

Jarra con agua inicial

Otra variante ^{[ 6 ]} es cuando una de las jarras tiene un volumen de agua conocido al principio; en ese caso, los volúmenes alcanzables son un múltiplo del máximo común divisor entre los dos recipientes, alejados del volumen conocido existente, o de cero. Por ejemplo, si una jarra que contiene 8 litros está vacía y la otra jarra que contiene 12 litros tiene 9 litros de agua al principio, entonces con una fuente (grifo) y un desagüe (fregadero), estas dos jarras pueden medir volúmenes de 9 litros, 5 litros, 1 litro, así como 12 litros, 8 litros, 4 litros y 0 litros. La solución más simple para 5 litros es (9,0) → (9,8) → (12,5); la solución más simple para 4 litros es (9,0) → (12,0) → (4,8). Estas soluciones se pueden visualizar mediante flechas rojas y azules en una cuadrícula cartesiana con líneas diagonales (de pendiente -1 tal que${\displaystyle x+y=const.}$en estas líneas diagonales) espaciadas 4 litros entre sí, tanto horizontal como verticalmente.

Nuevamente, si nos restringimos solo a acciones reversibles, desde el punto deseado (5,0), solo hay dos acciones reversibles: transferir 5 litros de agua de la jarra de 12 litros a la jarra de 8 litros (0,5), o llenar la jarra vacía de 8 litros por completo desde el grifo (5,8). Por lo tanto, solo hay dos soluciones al problema:

(5, 0) ↔ (0, 5) ↔ (12, 5) ↔ (9, 8) ↔ (9, 0)

(5, 0) ↔ (5, 8) ↔ (12, 1) ↔ (0, 1) ↔ (1, 0) ↔ (1, 8) ↔ (9, 0)

Para la pregunta de 4 litros, dado que${\displaystyle 4\equiv 0\!\mod \!4}$Es necesaria una acción irreversible al inicio de la solución; podría ser simplemente verter los 9 litros de agua de la jarra de 12 litros en el fregadero (0,0), o llenarla completamente hasta 12 litros desde el grifo (12,0). Luego, podemos construir nuestras soluciones hacia atrás como antes:

(4, 0) ↔ (4, 8) ↔ (12, 0) ← (9, 0)

(4, 0) ↔ (0, 4) ↔ (12, 4) ↔ (8, 8) ↔ (8, 0) ↔ (0, 8) ↔ (0, 0) ← (9, 0)

Si el número de jarras es tres, el estado de llenado después de cada paso se puede describir en un diagrama de coordenadas baricéntricas , ya que la suma de los tres números enteros permanece constante en todos los pasos. ^{[ 7 ]} En consecuencia, los pasos se pueden visualizar como movimientos de billar en el sistema de coordenadas (recortado) sobre una red triangular.

El diagrama baricéntrico de la derecha ofrece dos soluciones para el rompecabezas de 8, 5 y 3 litros. El área amarilla indica las combinaciones posibles con las jarras. Partiendo del cuadrado, las trayectorias rojas continuas y azules discontinuas muestran las transiciones de vertido. Cuando un vértice cae sobre el triángulo negro punteado, se han medido 4 litros. Otro vertido hasta el rombo produce 4 litros en cada una de las jarras de 8 y 5 litros.

El camino azul es un paso más corto que el camino del rompecabezas de dos jarras con grifo y desagüe, ya que podemos acumular 4 L en la jarra de 8 L, algo que no ocurre en la variante de dos jarras.

• Rompecabezas de cuerda quemada , otra clase de rompecabezas que implican la combinación de medidas.
• Efecto de ajuste

• Cowley, Elizabeth B. (1926). " Nota sobre una ecuación diofántica lineal". Preguntas y debates. American Mathematical Monthly . 33 (7): 379– 381. doi : 10.2307/2298647 . JSTOR 2298647. MR 1520987 .  
• Tweedie, MCK (1939). "Un método gráfico para resolver problemas de medición tartaglianos". The Mathematical Gazette . Vol.  23, n.º  255, págs. 278–282 . JSTOR 3606420 .  
• Saksena, JP (1968). "Enrutamiento óptimo estocástico". Unternehmensforschung . 12 (1): 173– 177. doi : 10.1007/BF01918326 . S2CID 10064660 . 
• Atwood, Michael E.; Polson, Peter G. (1976). "Un modelo de proceso para problemas con jarras de agua". Psicología Cognitiva . 8 (2): 191– 216. doi : 10.1016/0010-0285(76)90023-2 . ​​S2CID 54388726 . 
• Rem, Martin; Choo, Young il (1982). "Un programa de espacio fijo con complejidad de salida lineal para el problema de los tres buques" . Science of Computer Programming . 2 (2): 133– 141. doi : 10.1016/0167-6423(82)90011-9 .
• Thomas, Glanffrwd P. (1995). "El problema de las jarras de agua: soluciones desde la perspectiva de la inteligencia artificial y las matemáticas". Matemáticas en la escuela . Vol.  24, n.º  2, págs. 34–37 . JSTOR 30215221 .  
• Murray-Lasso, MA (2003). "Acertijos matemáticos, ideas poderosas, algoritmos y computadoras en la enseñanza de la resolución de problemas" . Journal of Applied Research and Technology . Vol.  1, n.°  3, págs. 215-234 . 
• Lalchev, Zdravko Voutov; Varbanova, Margarita Génova; Voutova, Irirna Zdravkova (2009). "Método geométrico de Perlman para resolver problemas de vertido de líquidos" .
• Goetschalckx, Marc (2011). "Enrutamiento de flujo único a través de una red". Ingeniería de la cadena de suministro . Serie internacional en investigación operativa y ciencias de la gestión. Vol.  161. pp. 155–180 . doi : 10.1007/978-1-4419-6512-7_6 . ISBN  978-1-4419-6511-0.