Traslados 2

La información solo aparece en los extremos

Imagina que tienes una jarra sin graduar. Puedes llenarla hasta el borde y sabrás que contiene exactamente su capacidad. También puedes vaciarla por completo y sabrás que contiene $0$. Pero si echas “un poco” de agua, no puedes saber si son $2$, $3$ o $4$ litros, salvo que esa cantidad haya sido producida por operaciones anteriores.

De aquí sale la regla más importante de todo el tema:

Todo trasvase útil debe terminar con al menos uno de los recipientes involucrados lleno o vacío.

No significa que todos los recipientes deban estar llenos o vacíos al final de cada paso. Pueden quedar cantidades intermedias, pero esas cantidades aparecen como residuo de un trasvase que llenó o vació otro recipiente.

Cómo registrar un trasvase

Para no perderse, conviene escribir el estado como una terna ordenada:

$$(\text{depósito principal},\ \text{recipiente A},\ \text{recipiente B})$$

Por ejemplo:

$$(12,5,0)$$

significa que el depósito principal tiene $12$ litros, el recipiente A tiene $5$ litros y el recipiente B está vacío.

Cada trasvase se registra indicando:

• recipiente de origen;
• recipiente de destino;
• cantidad trasvasada.

La cantidad trasvasada será la menor de estas dos:

• lo que tiene el recipiente de origen;
• lo que le falta al recipiente de destino para llenarse.

En la situación de la figura, si llenamos la jarra de $5$ L desde el depósito, el estado pasa de

$$(12,0,0)$$

a

$$(7,5,0).$$

Luego, si vertemos la jarra de $5$ L en la jarra de $7$ L, como la jarra de $7$ estaba vacía, recibe los $5$ litros:

$$(7,0,5).$$

Así se va construyendo la secuencia.

Planteamiento general

Supongamos que tenemos:

• un depósito principal con $N$ litros;
• dos recipientes auxiliares vacíos de capacidades $a$ y $b$ litros;
• un objetivo: obtener exactamente $x$ litros en alguno de los recipientes.

Hay dos rutas básicas, que conviene ensayar y comparar.

Método A: llenar el recipiente de capacidad $a$ y verterlo en el de $b$

Pasos:

1. Llenar el recipiente $a$ desde el depósito.
2. Verter $a$ en $b$.
3. Si $b$ se llena, vaciar $b$ de regreso al depósito principal.
4. Repetir.

Con este procedimiento se van generando cantidades que son los restos de $ka$ al dividir entre $b$.

Método B: llenar el recipiente de capacidad $b$ y verterlo en el de $a$

Es el proceso simétrico:

1. Llenar $b$ desde el depósito.
2. Verter $b$ en $a$.
3. Si $a$ se llena, vaciar $a$ de regreso al depósito.
4. Repetir.

Aquí se generan los restos de $kb$ al dividir entre $a$.

Ejemplo comparativo

Depósito de $10$ L, jarras de $3$ L y $7$ L. Objetivo: obtener $5$ L.

Método A (llenar la jarra de 3 L):

El objetivo se logra en 10 trasvases.

Método B (llenar la jarra de 7 L):

Aquí el objetivo se logra en 8 trasvases. Por tanto, el método B es más corto en este caso.

Este ejemplo muestra por qué no conviene aferrarse a un solo método: a veces conviene llenar el recipiente pequeño y a veces el grande.

Condición de posibilidad

Con dos recipientes auxiliares de capacidades $a$ y $b$, las cantidades que se pueden aislar como residuos son múltiplos del máximo común divisor de $a$ y $b$.

Es decir, si

$$d = \operatorname{mcd}(a,b),$$

entonces solo se pueden obtener cantidades que sean múltiplos de $d$.

Ejemplo: con jarras de $4$ L y $6$ L, el MCD es $2$. Por lo tanto, solo se pueden obtener cantidades pares: $2$, $4$, $6$, etc. Obtener $3$ L con jarras de $4$ y $6$ es imposible, aunque se tenga un depósito grande.

Esto se relaciona con la ecuación diofántica:

$$ma + nb = x,$$

donde $m$ y $n$ pueden ser enteros positivos o negativos. Los valores negativos representan devoluciones al depósito o vaciados.

El procedimiento general en un problema de trasvases es el siguiente:

1. Escribir el estado inicial.
2. Definir el estado objetivo.
3. Elegir un par de recipientes y aplicar el método A o el método B.
4. Contar cada vertido como un trasvase, incluso los parciales.
5. Detenerse apenas aparezca la cantidad pedida en algún recipiente permitido.
6. Comparar el número de trasvases de las rutas ensayadas.

Para no perderse:

• No repetir estados. Si un trasvase lleva a un estado ya visitado, se entró en un ciclo.
• Evitar trasvases que no llenen ni vacíen ningún recipiente.
• Verificar que no se desperdicie líquido. Todo lo que se vacía debe ir a otro recipiente, normalmente al depósito principal.

Cuando el número de trasvases es pequeño, el método de tabla es suficiente. Si el número crece, conviene buscar atajos del tipo

$$ka - b = x \quad \text{o} \quad kb - a = x.$$

Por ejemplo, si se tienen jarras de $8$ L y $11$ L y se quiere $5$ L, es útil notar que

$$2\times 8 - 11 = 5.$$

Eso sugiere llenar dos veces la jarra de $8$ L y verterla en la de $11$ L.

Cuando hay más de dos recipientes auxiliares, la lógica no cambia: se sigue trabajando con estados y trasvases que llenen o vacíen recipientes.

El depósito principal, que suele estar lleno al inicio, actúa como reservorio: de él se llena y a él se devuelve el líquido sobrante.

Pasos recomendados:

• Elegir dos recipientes cuyas capacidades sean convenientes para generar la cantidad deseada.
• Usar el tercer recipiente solo si permite un atajo.
• Registrar el estado con una tupla más larga, por ejemplo

$$(P,A,B,C).$$

• Aplicar siempre la regla de que todo trasvase útil termina con al menos un recipiente lleno o vacío.

Ejemplo breve: depósito de $30$ L, jarras de $8$ L y $11$ L, obtener $5$ L.

$$(30,0,0) \xrightarrow{\text{llenar 8}} (22,8,0) \xrightarrow{8 \to 11} (22,0,8)$$

$$\xrightarrow{\text{llenar 8}} (14,8,8) \xrightarrow{8 \to 11} (14,5,11)$$

En solo 4 trasvases se obtuvieron $5$ L en la jarra de $8$ L. La clave fue notar que $2\times 8 - 11 = 5$.

En problemas con tres jarras auxiliares, como por ejemplo un depósito de $40$ L y jarras de $7$, $10$ y $16$ L, conviene revisar si dos de esas jarras bastan para generar la cantidad pedida. Si dos de ellas no permiten un camino corto, entonces se usa la tercera como almacén temporal, pero la idea de fondo es la misma: construir la cantidad mediante llenados y vaciados.

Algunos problemas de trasvases no piden una sola cantidad, sino atender dos pedidos a la vez.

Por ejemplo, un comerciante tiene un depósito lleno y dos clientes desean $x$ y $y$ litros en recipientes propios. Además, puede ocurrir que uno de los recipientes del cliente quede como parte de pago.

En estos casos hay que tener en cuenta lo siguiente:

• El total a entregar es $x+y$, y debe ser menor o igual que $N$.
• Cada recipiente del cliente debe quedar con la cantidad exacta pedida.
• Una vez que un cliente recibe su recipiente, ese recipiente ya no puede usarse para seguir midiendo.
• El depósito principal puede conservar el resto.

La resolución es una búsqueda de un estado objetivo más exigente. Por ejemplo, si un depósito tiene $10$ L y hay jarras de $3$ L y $7$ L, y se piden $2$ L y $5$ L, el objetivo sería un estado como

$$(3,2,5),$$

porque $3+2+5=10$. No basta con que aparezca una de las cantidades; ambas deben estar en los recipientes correctos.

Para resolver estos casos conviene:

1. Deducir cuánto debe quedar en el depósito al final.
2. Buscar una secuencia que construya primero una de las cantidades sin bloquear la otra.
3. Verificar que ningún recipiente entregado se use después.

En la práctica de este tema también aparecen problemas de traslados con restricciones de peso o tiempo. No son trasvases, pero comparten la lógica de minimizar viajes o tiempo.

Canoa con límite de peso

Se tiene una canoa que soporta como máximo $C$ kilogramos y varias personas con diferentes pesos. Todos saben remar. Se debe pasar a todos de una orilla a otra con el menor número de viajes.

Ideas clave:

• Calcular quiénes pueden ir juntos: la suma de sus pesos no debe exceder $C$.
• Recordar que el bote debe regresar. Si todos parten de la misma orilla, el número de viajes suele ser de la forma $2n-1$, donde $n$ es el número de viajes de ida.
• Para minimizar viajes, conviene que la mayoría de viajes de ida lleve la máxima cantidad permitida de pasajeros, pero la restricción de peso puede obligar a que algunos viajes lleven una sola persona.

Este tipo de problemas se resuelve simulando viajes y regresos. La trampa está en elegir mal quién regresa, lo que puede alargar la secuencia o bloquear el traslado.

Botes con tiempos

Hay botes que demoran distintos tiempos en cruzar un río, y se pueden atar de a dos. Si dos botes van juntos, el tiempo del viaje es el del más lento. Un solo marinero debe llevar todos los botes a la otra orilla.

Este problema es del mismo tipo que “cuatro personas con una linterna”. La estrategia general es:

• Hacer que los dos más lentos crucen juntos, para que su tiempo se pague una sola vez.
• Usar a los más rápidos para devolver el bote.

Ejemplo nuevo: botes con tiempos $1$, $2$, $6$ y $10$ minutos.

El tiempo mínimo es $17$ minutos.

Si en lugar de esta estrategia se usara siempre al bote más rápido para escoltar a los demás, el tiempo sería mayor:

$$10+1+6+1+2 = 20.$$

Por eso conviene pagar algunos regresos con un bote rápido alternativo.