Los acertijos de vertido de agua (también llamados problemas de jarras de agua , problemas de decantación , [1] [2] acertijos de medición o acertijos de Duro de matar con venganza ) son una clase de acertijos que involucran 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 para verter agua de una jarra a otra (hasta que una jarra se vacía o la otra se llena) se necesitan 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 , tales acertijos tienen solución si y solo si el volumen deseado es múltiplo del máximo común divisor de todas las capacidades de volumen entero de las jarras.
Es una suposición común, expuesta como parte de estos acertijos, que las jarras del rompecabezas tienen formas irregulares y no están marcadas, por lo que es imposible medir con precisión cualquier cantidad de agua que no llene completamente una jarra. Otras suposiciones de estos problemas pueden incluir que no se puede derramar agua y que cada paso de vertido de agua desde una jarra de origen a una jarra de destino se detiene cuando la jarra de origen está vacía o la jarra 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 se llenan con 8, 0 y 0 litros. En estado objetivo se deben llenar con 4, 4 y 0 litros. El rompecabezas se puede resolver en siete pasos, pasando por la siguiente secuencia de estados (indicada como un triple entre corchetes de los tres volúmenes de agua en las tres jarras):
Cowley (1926) escribe que este enigma 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 sólo permiten detener/girar en los límites de la cuadrícula cartesiana (es decir, en la capacidad máxima de cada jarra), las únicas acciones reversibles (reversibles en un solo paso) son:
Las únicas acciones irreversibles que no se pueden revertir en un solo paso son:
Al limitarnos únicamente a acciones reversibles, podemos construir la solución al problema a partir del resultado deseado. Desde el punto [4,4,0], sólo hay dos acciones reversibles: Pasar 3 litros de la jarra de 8 litros a la jarra vacía de 3 litros [1,4,3], o pasar 3 litros de la jarra de 5 litros a la jarra de 3 litros vacía [4,1,3]. Por tanto, sólo existen dos soluciones a este problema:
Las reglas a veces se formulan añadiendo un grifo (una fuente "jarra" con agua infinita) y un fregadero (una "jarra" de drenaje 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 con venganza . [4] Esta variante tiene una solución óptima que se puede obtener utilizando un gráfico baricéntrico en forma de billar (o un billar matemático). [5]
La gráfica muestra dos formas de obtener 4 litros usando garrafas de 3 y 5 litros, y una fuente de agua y un fregadero en una cuadrícula cartesiana con líneas diagonales de pendiente −1 (de modo que en estas líneas diagonales, que representan el vertido de agua de una jarra a la otra jarra). Los ejes x e y representan las cantidades en las jarras de 5 y 3 L, respectivamente. A partir 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 denota 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 de puntos indican el vaciado de una jarra.
Al concatenar cualquiera de las soluciones, el recorrido de la línea 4 L y el reverso de la otra solución regresa a (0, 0), lo que produce un gráfico de ciclo . Si y sólo 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 en el grifo son ambos reversibles). Para obtener 4 litros utilizando garrafas de 3 y 5 litros queremos llegar al punto (4, 0). Desde el punto (4, 0), sólo existen dos acciones reversibles: llenar hasta el tope la jarra de 3 litros vacía del grifo (4,3), o pasar 1 litro de agua de la jarra de 5 litros a la de 3 litros. jarra de litro (1,3). Por tanto, sólo existen dos soluciones al problema:
El gráfico del ciclo se puede representar mediante pares ordenados conectados por acciones reversibles:
que contiene todos los estados posibles alcanzables 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 (1, 2) tiene ambas jarras parcialmente llenas y no es posible ninguna acción reversible desde este estado.
_Problem_in_Cartesian_coordinates.jpg/1280px-Decanting_(water_jugs)_Problem_in_Cartesian_coordinates.jpg)
Otra variante [6] es cuando una de las jarras tiene para empezar un volumen de agua conocido; En ese caso, los volúmenes alcanzables son un múltiplo del máximo común divisor entre los dos contenedores, alejado 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 para empezar, 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 sencilla para 5 litros es (9,0) → (9,8) → (12,5); La solución más sencilla 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 en estas líneas diagonales) espaciadas 4 litros, tanto horizontal como verticalmente.
De nuevo, si nos limitamos únicamente a acciones reversibles, desde el punto deseado (5,0), sólo hay dos acciones reversibles: pasar 5 litros de agua de la jarra de 12 litros a la de 8 litros (0,5) , o llenando al máximo la jarra vacía de 8 litros desde el grifo (5,8). Por tanto, sólo existen dos soluciones al problema:
Para la cuestión de los 4 litros, desde , es necesaria una acción irreversible al inicio de la solución; Podría ser simplemente echar los 9 litros de agua completos de la jarra de 12 litros al fregadero (0,0), o llenarla hasta los 12 litros del grifo (12,0). Entonces, podemos construir nuestras soluciones al revés como antes:
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 , porque la suma de los tres números enteros permanece igual en todos los pasos. [7] En consecuencia, los pasos se pueden visualizar como movimientos de billar en el sistema de coordenadas (recortado) en una red triangular.
El gráfico baricéntrico de la derecha ofrece dos soluciones al rompecabezas de 8, 5 y 3 L. La zona amarilla indica las combinaciones que se pueden realizar con las jarras. Comenzando en el cuadrado, los caminos de color rojo sólido y azul discontinuo muestran transiciones que se pueden verter. Cuando un vértice aterriza en el triángulo negro punteado, se han medido 4 L. Otro vertido al diamante produce 4 litros en jarras de 8 y 5 litros.
El camino azul es un paso más corto que el camino del puzzle de dos jarras con grifo y desagüe, ya que en la jarra de 8 L podemos acumular 4 L, ausente en la variante de dos jarras.
