Traslados 1

Todos los problemas de traslados, aunque parezcan distintos, comparten una estructura.

1. Estado inicial: dónde están las personas, fichas o litros al comienzo.
2. Estado objetivo: qué se desea obtener al final.
3. Operaciones permitidas: qué movimientos se pueden hacer, con sus restricciones.
4. Costo: cuántas operaciones se han realizado.
5. Pregunta: hallar el costo mínimo.

Por ejemplo, en un cruce de río:

• Estado inicial: todas las personas están en la orilla $A$.
• Estado objetivo: todas están en la orilla $B$.
• Operación permitida: cruzar en canoa, respetando la capacidad.
• Costo: número de viajes de ida o de vuelta.

En un trasvase:

• Estado inicial: $(12,0,0)$, si el recipiente de $12\ L$ está lleno y los otros dos vacíos.
• Estado objetivo: $(10,2,0)$, si se desea obtener $2\ L$ en el segundo recipiente.
• Operación permitida: verter de un recipiente a otro hasta llenar el que recibe o vaciar el que vierte.
• Costo: número de trasvases.

Dominar el tema no es memorizar respuestas. Es construir una tabla o sucesión de estados en la que cada paso sea legal y no repita innecesariamente una situación anterior.

2.1. La situación básica

En estos problemas tenemos una canoa, bote o lancha que debe trasladar personas de una orilla de un río a la otra. Debemos tener presente:

• La canoa debe tener al menos una persona que reme, salvo que el problema diga otra cosa.
• Un viaje es cualquier cambio de orilla: tanto de ida como de regreso.
• La canoa no regresa sola.
• Si la canoa soporta un peso máximo, cualquier pareja o grupo no puede exceder ese peso.
• La pregunta pide, casi siempre, el mínimo número de viajes.

La estrategia general es:

1. Identificar quiénes pueden viajar juntos.
2. Procurar que en cada viaje de ida la canoa vaya lo más cargada posible, sin violar la capacidad.
3. Programar los regresos con la persona más ligera o más conveniente.
4. No repetir un estado anterior; repetir significa que dimos una vuelta innecesaria.

### 2.2. El caso clásico: dos niños y un adulto

Un caso frecuente es aquel en el que la lancha puede llevar **a dos niños o a un adulto**, pero no a un niño y un adulto juntos.

Para pasar a **un adulto** de la orilla $A$ a la orilla $B$, usando dos niños como ayudantes, se realiza esta secuencia:

1. Viajan los dos niños de $A$ a $B$.
2. Regresa un niño de $B$ a $A$.
3. Viaja el adulto de $A$ a $B$.
4. Regresa el otro niño de $B$ a $A$.

Después de estos 4 viajes, el adulto quedó en la orilla $B$ y los dos niños están nuevamente en la orilla $A$, listos para repetir el proceso con otro adulto.

Si hay $n$ adultos, y solo interesa que los adultos pasen, el proceso se repite para los primeros $n-1$ adultos. El último adulto ya no necesita devolver la canoa, así que pasa en un viaje final. Por lo tanto:

$$\text{mínimo de viajes}=4(n-1)+1=4n-3.$$

Para $n=3$ adultos, por ejemplo, se obtienen $4(3)-3=9$ viajes.

2.3. Casos con capacidad medida en kilogramos

En otros problemas, la canoa soporta un peso máximo. Allí conviene escribir los pesos y analizar qué parejas son legalmente posibles.

Idea clave: si una persona muy ligera está disponible, suele ser la mejor candidata para realizar los viajes de retorno, porque no «desperdicia» mucha capacidad.

Ejemplo. Una canoa soporta $100\ kg$. Cuatro personas pesan $60\ kg$, $60\ kg$, $40\ kg$ y $30\ kg$. Todas saben remar. ¿Cuántos viajes como mínimo se necesitan para que todas crucen?

Una secuencia posible sería:

Se necesitan 5 viajes como mínimo.

El secreto aquí es que la persona de $30\ kg$ regresa dos veces para permitir que las dos personas de $60\ kg$ crucen sin exceder el límite.

2.4. Restricciones de incompatibilidad

Algunos traslados de personas u objetos incluyen restricciones del tipo «si A y B quedan solos, A ataca a B».

Un ejemplo clásico es el del lobo, la oveja y un atado de pasto: el lobo no puede quedar solo con la oveja, y la oveja no puede quedar sola con el pasto. La estrategia es colocar al elemento que puede chocar con dos distintos —en este caso, la oveja— en el centro de la lógica: en cada estado intermedio debe quedar vigilado por la persona o acompañado por un elemento que no genere peligro.

Este tipo de problema exige revisar los estados intermedios después de cada viaje, no solo el estado final.

3.1. ¿Qué significa «mover una ficha»?

Aquí la palabra ficha es amplia: puede ser una ficha numerada, una carta, un vaso, una bola numerada, una pieza de ajedrez, etc.

Los problemas piden, en general:

• Mover la menor cantidad de fichas para lograr un nuevo orden.
• Intercambiar fichas para modificar una expresión.
• Voltear cartas o piezas bajo reglas restringidas.
• Sacar e insertar bolas en un recipiente.

La idea común es: no mover lo que ya está correctamente ubicado.

3.2. Fichas numeradas dentro de una expresión

En este tipo de problemas se tiene una expresión aritmética combinada. Los signos están fijos; solo se pueden mover las fichas con números.

La pregunta puede ser:

• ¿Cuál es el máximo valor entero de $E$ moviendo solo las fichas?
• ¿Cuántas fichas, como mínimo, deben cambiarse de lugar?

Método general:

1. Analizar la estructura de la expresión.
2. Ubicar los números grandes en las operaciones que aumentan el resultado.
3. Ubicar los números pequeños en las restas o divisiones.
4. Si una ficha puede rotares, considerar que $6$ puede volverse $9$.
5. Contar cuántas fichas se movieron respecto de la disposición inicial.

Ejemplo breve. Si una plantilla es

$$E=(a+b-c)\times d \div e,$$

y se dispone de los números $2,3,4,5,6$, conviene colocar:

• $d=6$, porque multiplica;
• $e=2$, porque divide poco;
• $a+b-c$ grande, es decir, $a=5$, $b=4$, $c=3$.

Así,

$$E=(5+4-3)\times 6 \div 2 = 6 \times 6 \div 2 = 18.$$

3.3. Mover fichas para transformar una figura

Cuando se pide pasar de una figura formada por fichas circulares a otra, conviene superponer mentalmente ambas figuras.

Las fichas que coinciden en ambas figuras no se tocan. Las que no coinciden deben moverse. Por lo tanto:

$$\text{mínimo de fichas movidas} = \text{número de posiciones que no coinciden}.$$

En muchos casos de simetría, la respuesta se obtiene moviendo solo una fracción de las fichas, porque las posiciones coincidentes son más de las que se cree.

3.4. Vasos llenos y vacíos

Un caso especial es el de vasos intercalados: algunos llenos y otros vacíos. Se pide dejarlos todos los llenos de un lado y todos los vacíos del otro.

La respuesta cambia según lo que se permita:

• Si solo se pueden mover vasos completos, se deben reubicar ciertos vasos.
• Si se permite vaciar el contenido de un vaso en otro, a veces se pueden mover menos vasos.

Ejemplo. Con 10 vasos alternados: lleno, vacío, lleno, vacío, …, la menor cantidad de vasos que deben manipularse es menor si se permite trasvasar contenido. Esto muestra por qué es importante leer si «mover un vaso» incluye o no verter su contenido.

3.5. Voltear cartas contiguas

En este tipo de problemas, hay cartas con una cara de un color y la otra de otro. Un movimiento permite escoger un par de cartas contiguas y voltearlas.

Método:

1. Comparar la disposición inicial y la final.
2. Marcar las posiciones donde la carta cambia de cara.
3. Un movimiento cambia exactamente dos posiciones contiguas.
4. Si las posiciones marcadas pueden agruparse en pares contiguos disjuntos, el mínimo es la mitad del número de posiciones marcadas.

Por ejemplo, si las 4 primeras cartas deben cambiar, se puede voltear el par 1-2 y luego el par 3-4; son 2 movimientos.

Pero si las posiciones marcadas no están contiguas, habrá que voltear también cartas temporales, lo que aumenta el número de movimientos.

3.6. Bolas numeradas en un recipiente con aberturas

Algunas preguntas recientes presentan un recipiente vertical con aberturas en $P$, $Q$, $R$ y $S$. En el interior hay bolas numeradas. Una operación consiste en sacar una bola por una abertura lateral e introducirla por la abertura superior $P$.

Aquí las bolas se comportan casi como una pila: no se puede sacar cualquier bola en cualquier momento, sino solo la que está al nivel de una abertura. Al volver a introducirla por arriba, cambia el orden.

La estrategia es:

1. Observar el orden objetivo.
2. Identificar qué bolas están bloqueando el orden correcto.
3. Sacar la bola que, al reinsertarse por $P$, quede en su posición final.
4. Evitar sacar dos veces la misma bola.

El número de operaciones depende de cuántas bolas sea indispensable extraer.

3.7. Traslados en un tablero

También existen problemas en los que una ficha se mueve sobre un tablero con reglas especiales. Por ejemplo, la ficha puede avanzar $3$ casillas en una dirección y $1$ en otra.

Para hallar el mínimo número de movimientos:

1. Escribir la diferencia horizontal y vertical entre la casilla inicial y la final.
2. Cada movimiento genera combinaciones de cambios $(\pm 3,\pm 1)$ o $(\pm 1,\pm 3)$.
3. Probar primero con 1 movimiento, luego con 2, luego con 3, etc., y verificar si se alcanza exactamente la casilla final.
4. Como los movimientos son reversibles, también se puede partir del final hacia el inicio.

Aunque en el plan de estudios este bloque suele intensificarse más adelante, en los exámenes recientes de la UNMSM los trasvases han aparecido con mucha fuerza. Por eso los estudiamos aquí.

4.1. ¿Qué es un trasvase?

Un trasvase es pasar líquido de un recipiente a otro. Los problemas tienen estas reglas casi fijas:

• Los recipientes no tienen marcas ni graduaciones.
• No se puede medir visualmente.
• No se desperdicia líquido.
• Un trasvase termina cuando el recipiente que recibe se llena o el recipiente que vierte se vacía, lo que ocurra primero.
• Si hay varios recipientes, la cantidad total de líquido se conserva.

Cada vez que vertemos de un recipiente a otro, aunque sea parcialmente, se cuenta como un trasvase.

### 4.2. Método de la tabla de estados

La herramienta más útil es representar cada estado como una terna ordenada

$$(\text{volumen en }A,\ \text{volumen en }B,\ \text{volumen en }C).$$

Desde un estado, analizamos qué trasvases son posibles y pasamos a un nuevo estado. El objetivo es llegar al volumen pedido con la menor cantidad de flechas.

**Ejemplo.** Se tiene un recipiente de $12\ L$ lleno, un recipiente de $7\ L$ vacío y otro de $5\ L$ vacío. Se desea obtener $2\ L$ en el recipiente de $7\ L$.

Escribimos las capacidades en orden: $12, 7, 5$. Estado inicial: $(12,0,0)$.

1. Pasar del recipiente de $12$ al de $7$:  
   $$(12,0,0)\to(5,7,0)$$
2. Pasar del recipiente de $7$ al de $5$:  
   $$(5,7,0)\to(5,2,5)$$
3. Pasar del recipiente de $5$ de vuelta al de $12$:  
   $$(5,2,5)\to(10,2,0)$$

Se obtienen $2\ L$ en el recipiente de $7\ L$ con solo **3 trasvases**.

Observa que en el segundo paso, el recipiente de $7$ no se vació, sino que llenó el de $5$. Por lo tanto quedaron $2\ L$ en el de $7$.

### 4.3. ¿Cuándo es posible obtener un volumen?

Si las capacidades son enteras y no se desperdicia líquido, los volúmenes alcanzables son **múltiplos del máximo común divisor** de las capacidades.

Por ejemplo, con recipientes de $10$, $7$ y $5$ litros, el MCD es $1$, así que cualquier volumen entero entre $0$ y $10$ es, en principio, alcanzable. Con capacidades $12$, $10$ y $6$, el MCD es $2$, por lo que solo se pueden obtener volúmenes pares.

Esta observación permite descartar problemas imposibles y orientar la búsqueda.

4.4. Casos con capacidades decimales

Si las capacidades son decimales, conviene amplificarlas para trabajar con enteros.

Ejemplo. Capacidades $7{,}5\ L$ y $4{,}5\ L$. Multiplicando por $2$, se convierten en $15$ y $9$, que son más fáciles de manejar. Después de resolver, los volúmenes se dividen entre $2$.

4.5. Trasvases con tres recipientes: dos rutas principales

Cuando hay un recipiente lleno y dos vacíos, existen básicamente dos caminos:

1. Llenar primero el recipiente vacío de mayor capacidad.
2. Llenar primero el recipiente vacío de menor capacidad.

Conviene explorar ambos. Uno de ellos suele producir el objetivo en menos pasos.

En un examen, no es necesario escribir un árbol gigante: basta con seguir cada ruta con orden y detenerse cuando aparezca un estado repetido o cuando se alcance el volumen pedido.

4.6. Distribuciones exactas en los tres recipientes

Algunas preguntas no piden obtener un volumen en un solo recipiente, sino lograr una distribución exacta en los tres. Por ejemplo, con un recipiente lleno de $15\ L$ y dos recipientes vacíos de $7\ L$ y $4\ L$, se pide tener $3$, $5$ y $7$ litros.

Aquí el estado final es más restrictivo: no basta con que un volumen aparezca, sino que los tres recipientes tengan simultáneamente las cantidades pedidas.

La técnica sigue siendo la misma: buscar una sucesión de estados hasta llegar a la terna final. A veces conviene partir del estado final y retroceder.