Dos jarras, una ecuación: del problema 3–5 a Bézout

Dos jarras sin graduar, una fuente de agua y un objetivo preciso: medir una cantidad que no está indicada en ninguno de los recipientes. El problema es concreto, pero conduce de forma natural a los enteros, al máximo común divisor, a la identidad de Bézout y a los algoritmos de grafos.

El criterio aritmético indica si el objetivo supera la prueba de divisibilidad; los límites de capacidad y los estados de las jarras determinan si puede realizarse físicamente y cómo. Son respuestas diferentes y complementarias.

1. Reglas y objetivo

En el modelo abierto clásico disponemos de una fuente de agua ilimitada, un desagüe y dos jarras sin graduar de capacidades enteras. Un movimiento legal es exactamente uno de los siguientes:

• llenar por completo una jarra desde la fuente;
• vaciar por completo una jarra en el desagüe;
• verter de una jarra a la otra hasta que la primera quede vacía o la segunda se llene.

No se puede detener un trasvase a ojo. En el problema principal las capacidades son 3 y 5 litros, y el objetivo estricto es llegar a (1,0): un litro en la jarra de 3 litros y la jarra de 5 vacía. Escribiremos siempre un estado como (u,v), donde u es el contenido de la jarra de 3 litros y v el de la jarra de 5.

2. El caso 3–5, estado por estado

De las jarras vacías a un litro aislado

Paso	Movimiento	Estado	Resultado del movimiento
0	Inicio	(0,0)	Las dos jarras están vacías
1	Llena la jarra de 3	(3,0)	La jarra está llena
2	Vierte de la 3 a la 5	(0,3)	La jarra de 3 se vacía
3	Llena de nuevo la 3	(3,3)	La jarra está llena
4	Vierte de la 3 a la 5	(1,5)	En la jarra de 5 solo caben 2 litros
5	Vacía la jarra de 5	(1,0)	El litro buscado queda aislado

(0,0) → (3,0) → (0,3) → (3,3) → (1,5) → (1,0)

Cada flecha respeta las reglas y cada coordenada permanece entre cero y la capacidad correspondiente. Estas dos comprobaciones sencillas descubren muchas soluciones falsas.

3. Estado, balance e invariante

Conviene llevar dos registros. El estado físico dice dónde está el agua; el balance dice cuánta agua hay en total y cómo entró o salió. En el recorrido anterior:

Estado físico y balance exterior

Estado	Total presente	Balance exterior
(0,0)	0	0
(3,0)	3	3
(0,3)	3	3
(3,3)	6	2 · 3
(1,5)	6	2 · 3
(1,0)	1	2 · 3 − 5

Durante un trasvase, el total u + v es invariante: solo cambia su distribución. Llenar y vaciar intercambian agua con el exterior. En este recorrido entran dos contenidos completos de 3 litros y sale el contenido completo de una jarra de 5, por tanto:

1 = 2 · 3 − 5

También hay un invariante aritmético más general: todo volumen alcanzable es una combinación entera de las capacidades. Al principio solo aparece cero; llenar introduce una capacidad, vaciar introduce cero y un trasvase produce sumas o diferencias con una capacidad cuando una jarra se vacía o la otra se llena. Así, las combinaciones enteras permanecen cerradas bajo todos los movimientos legales.

El par de coeficientes no es el estado físico ni es único. Es una etiqueta algebraica útil para certificar un volumen; el estado (u,v) sigue siendo la descripción física imprescindible.

4. El significado de los coeficientes negativos

El recorrido proporciona una ecuación diofántica, es decir, una ecuación cuyas soluciones buscadas deben ser números enteros:

3x + 5y = 1,
x = 2, y = −1.

El coeficiente −1 no representa una cantidad de agua negativa. En el balance indica que el contenido completo de 5 litros se vertió en el desagüe. Los coeficientes cuentan contribuciones con signo; los contenidos reales siempre se mantienen entre cero y sus capacidades.

Esta interpretación como recuento neto es directa en recorridos canónicos, en los que una jarra se llena solo cuando está vacía y se vacía en el desagüe solo cuando está llena. Si se llena o vacía una jarra parcialmente llena, los coeficientes siguen siendo un certificado algebraico, pero ya no coinciden con un simple número de operaciones.

Esta distinción evita una confusión frecuente: una solución entera de la ecuación es un certificado aritmético, no todavía una lista automática de llenados y trasvases. Para obtener los movimientos hay que construir un camino entre estados legales.

5. Algoritmo de Euclides extendido e identidad de Bézout

El máximo común divisor de dos enteros positivos es el mayor entero positivo que divide a ambos. El algoritmo de Euclides lo encuentra; al recorrer sus divisiones hacia atrás también produce los coeficientes de Bézout:

5 = 1 · 3 + 2
3 = 1 · 2 + 1

1 = 3 − 2
  = 3 − (5 − 3)
  = 2 · 3 − 5

Hemos recuperado exactamente el balance del recorrido. La identidad de Bézout afirma que, para enteros positivos a y b, existen enteros r y s tales que:

a r + b s = MCD(a,b)

Multiplicar la identidad por un entero produce todos los objetivos múltiplos del MCD. Para 3x + 5y = 1, partiendo de la solución (2,−1), todas las soluciones enteras son:

x = 2 + 5t
y = −1 − 3t,  con t entero.

Esta infinitud algebraica no implica infinitos estados físicos: las capacidades son finitas y muchos pares de coeficientes describen el mismo volumen sin sugerir un recorrido cómodo.

6. La regla general y sus límites

Con capacidades a y b y objetivo d, la ecuación asociada es:

a x + b y = d

Sea g = MCD(a,b). La ecuación tiene soluciones enteras si y solo si g divide a d. En el modelo abierto clásico, para dejar exactamente d litros en una sola jarra con la otra vacía también se necesita:

0 ≤ d ≤ max(a,b).

Con los movimientos estándar, ambas condiciones también son suficientes. La divisibilidad descarta los objetivos aritméticamente imposibles; el límite de capacidad descarta cantidades que no caben en ninguna jarra. La ecuación ax + by = d se refiere al total presente: para igualarlo a d, la otra jarra debe estar realmente vacía al final. Si nos detuviéramos con d en una jarra y más agua en la otra, el total no sería d.

7. La comparación 4–6: un litro no, dos litros sí

Para jarras de 4 y 6 litros, MCD(4,6) = 2. Toda combinación 4x + 6y es par, así que un litro es imposible. No hace falta probar al azar: la paridad es un invariante.

Dos litros sí son posibles porque 2 = 6 − 4:

(0,0) → (0,6) → (4,2) → (0,2)

Los estados están ordenados como (jarra de 4, jarra de 6): llenamos la 6, vertemos en la 4 hasta llenarla y por último vaciamos la 4. Quedan 2 litros en la 6 y la otra jarra está vacía.

8. Otros casos comprobados

Jarras 3–5, objetivo 4

El certificado es 4 = 2 · 5 − 2 · 3. Con los estados ordenados como (3,5):

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

Cada trasvase continúa hasta vaciar su origen o llenar su destino; el estado final contiene 4 litros en la jarra de 5.

Jarras 2–7, objetivo 1

Aquí 1 = 7 − 3 · 2. Con los estados ordenados como (2,7):

(0,0) → (0,7) → (2,5) → (0,5)
      → (2,3) → (0,3) → (2,1) → (0,1)

Se restan repetidamente porciones de 2 litros de la jarra de 7.

Jarras 6–10, objetivo 8

MCD(6,10)=2 divide a 8. Un certificado es 8 = 3 · 6 − 10; el recorrido siguiente permite obtener la misma cantidad con otro balance, 8 = 2 · 10 − 2 · 6. Estados ordenados como (6,10):

(0,0) → (0,10) → (6,4) → (0,4)
      → (4,0) → (4,10) → (6,8) → (0,8)

Jarras 6–9, objetivo 4

Es imposible: MCD(6,9)=3 no divide a 4. Todos los volúmenes alcanzables son múltiplos de 3.

9. La variante cerrada 8–5–3

Otro clásico utiliza tres recipientes de 8, 5 y 3 litros. Esta vez cambian las hipótesis: el recipiente de 8 litros empieza lleno, no hay fuente ni desagüe, y solo se permiten trasvases completos hasta que el origen quede vacío o el destino se llene. Hay que repartir los 8 litros en dos partes de 4.

Escribiendo los estados en el orden (8,5,3), una solución es:

(8,0,0) → (3,5,0) → (3,2,3) → (6,2,0)
        → (6,0,2) → (1,5,2) → (1,4,3) → (4,4,0)

El total siempre es 8: aquí la conservación del agua es el invariante dominante. No podemos aplicar sin cambios el criterio de dos jarras con fuente y desagüe; tenemos tres capacidades, un sistema cerrado y un objetivo de reparto. Hay que declarar las hipótesis antes de usar un teorema.

10. Búsqueda del camino mínimo y comprobación final

Un certificado de Bézout verifica la compatibilidad aritmética, pero no sustituye la comprobación de capacidad ni garantiza que sus coeficientes se traduzcan directamente en el recorrido más corto. Para hallarlo podemos construir el grafo dirigido de estados: cada estado es un vértice y cada movimiento legal es un arco dirigido. Con dos jarras hay como máximo (a+1)(b+1) pares, por lo que una búsqueda en anchura, o BFS, siempre termina.

cola ← [(0,0)]
visitados ← {(0,0)}

mientras la cola no esté vacía:
    estado ← extraer el primero
    si estado es (d,0) o (0,d): reconstruir el camino
    generar: llenar A, llenar B, vaciar A, vaciar B,
             verter A→B, verter B→A
    para cada estado generado que no esté en visitados:
        añadirlo a visitados
        encolarlo y guardar su predecesor

La BFS visita primero los recorridos con menos arcos: el primer recorrido que alcanza el objetivo utiliza el número mínimo de movimientos según las reglas declaradas. Para el sistema cerrado 8–5–3 cambian el estado inicial, el número de coordenadas, la prueba del objetivo y el generador: se parte de (8,0,0), se busca (4,4,0) y solo se generan trasvases entre cada pareja de recipientes.

Lista de comprobación

1. Indica el orden de las coordenadas y comprueba los límites de capacidad en cada estado.
2. Verifica que cada trasvase termine con el origen vacío o el destino lleno.
3. Calcula el MCD y comprueba que divida al objetivo.
4. Comprueba d ≤ max(a,b) en el modelo abierto con objetivo en una jarra.
5. No confundas coeficientes negativos con agua negativa.
6. No confundas un certificado de Bézout con la secuencia de movimientos.
7. Si ax+by=d es el balance final, verifica que la otra jarra esté vacía.
8. Si cambia la fuente, el desagüe o el número de recipientes, redefine el espacio de estados.

Tres comprobaciones rápidas

• Con 6 y 10 litros, obtener 5 es imposible porque 2 no divide a 5.
• Con 3 y 5 litros, 7 es una combinación entera, pero no cabe en una sola jarra: no se cumple la condición de capacidad.
• Con 4 y 6 litros, obtener 2 es posible y el recorrido mostrado termina realmente con la otra jarra vacía.

El problema de las jarras separa muy bien los papeles de varias herramientas matemáticas: el invariante evita búsquedas inútiles, Bézout certifica la compatibilidad aritmética y el grafo de estados, junto con las restricciones físicas, convierte ese certificado en un procedimiento concreto, verificable y optimizable.

---

Preparado por Salvatore Mosaico.