Ranas, hormigas, camaleones...

Después de escribir el post sobre paridad estuve navegando la Web con el tema invariantes, otro tipo de razonamiento en el problem solving de olimpiada que generalmente acompaña al de paridad.

Y me encontré con el problema de las ranas en la escalera varias veces --de lo cual concluyo que debe ser clásico... Lo que llama la atención del problema de las ranas en la escalera es que, a pesar de que la pregunta es extremadamente simple, no es fácil encontrar la puerta de entrada hacia su respuesta --a menos que se esté acostumbrado a resolver acertijos olímpicos...

Porque, en ese caso, uno lee el enunciado con otros ojos --con ojos de aficionado a los acertijos. Otro detalle desconcertante es que cuando uno lee las soluciones publicadas, el argumento presentado deja la sensación de haber sido sacado de la manga (o del sombrero) y su autor lo plantea como si fuera el argumento más natural del mundo. Permítaseme presentarles entonces

El problema de las ranas en la escalera

En cada uno de los 10 peldaños de una escalera hay una rana. Cada rana puede, de un salto, colocarse en otro escalón. Pero cuando una rana hace eso, al mismo tiempo, alguna otra rana saltará la misma cantidad de peldaños en sentido opuesto: una sube, la otra baja. ¿Pueden las ranas colocarse todas juntas en un mismo peldaño?

Análisis del problema (y modelación)

Parece natural modelar el problema en el contexto de un juego: hay un estado inicial, uno final y una operación permitida. (Y esta decisión es ya el resultado de una mirada de aficionado a los acertijos olímpicos --y un modelo mental adquirido gracias a esa afición.)

Pues muchos problemas de olimpiada de matemáticas son tipo juego en el sentido antedicho.  Así pues, tenemos:

• Estado inicial: una rana en cada peldaño.
• Estado final: todas las ranas en un solo peldaño.
• Jugada permitida: la rana $i$ salta al peldaño $i+k$ y la rana $j$ al $j-k$

Ahora bien, la situación descrita en el enunciado es ridícula y ociosamente atractiva (bueno, eso creo). Pero una vez que se acepta, hay que buscar la clave. Y esa búsqueda hay que hacerla --de nuevo-- en el contexto de los acertijos olímpicos, un contexto que le da saliencia a la pregunta ¿se puede? o ¿es posible?.

Y una vez que uno sospecha que el estado final es imposible, entonces inevitablemente llega a nuestra mente la regla de oro para este tipo de problemas: busca la propiedad invariate bajo la operación permitida.

Una vez que se plantea esa meta, la propiedad invariante queda sugerida por la misma operación: una sube, la otra baja... se hace evidente que la propiedad invariante está relacionada con operación permitida y la suma $i+j=i+k+j-k$

Interpretación económica de la situación

Buscando una representación de los estados, podemos imaginar que cada rana tiene un valor que corresponde al peldaño que ocupa (una rana en el peldaño 5 vale 5): aumenta su valor si sube en la escalera, disminuye si baja.

Con esta interpretación la solución se hace evidente: lo que es invariante es el valor conjunto (o total) de todas las ranas: inicialmente es 55 y ahí se mantiene (gracias a la operación permitida).

Dentro de este marco interpretativo (el cual no se menciona en las soluciones publicadas en la Web), el argumento de la solución sí es el más natural: si todas las rana estuviesen en el peldaño $y$, entonces su valor total sería $10y$. Pero su valor total es invariante.

Por tanto $10y=55$. Y hemos logrado una contradicción o, mejor dicho una imposibilidad (a partir de la suposición de que se puede lograr el estado final) --pues un par no puede ser igual a un impar. Luego, el estado en que todas las ranas están en un mismo peldaño es imposible de lograr a partir del inicial y con la operación permitida.

Otros problemas

En un artículo de Patricia Fauring y Flora Gutiérrez --dos entusiastas argentinas del problem solving--, encontré los siguientes dos problemas con un contexto fantástico (as usual):

Problema camaleón

En una isla hay camaleones de tres colores: azul, gris, verde. Tienen la increible propiedad de cambiar de color de acuerdo a una regla: si se encuentran dos de diferente color, ambos cambian al tercer color, y cambian de color sólo en esa circunstancia. Si inicialmente hay 18 verdes, 19 grises y 20 azules ¿es posible que eventualmente todos sean del mismo color?

Solución

Caractericemos el estado camaleón de la isla por el número de camaleones de cada color. Inicialmente el estado es $(V,G,A)=(18,19,20)$. Se pregunta si eventualmente, bajo la operación permitida, el estado camaleón podría ser uno de los estados $(57,0,0),(0,57,0),(0,0,57)$.

Observemos que la operación permitida cambia el estado $(v,g,a)$ en un estado en que dos tipos de camaleón disminuyen su número en una unidad, mientras que el tercer tipo aumenta en dos unidades. Por ejemplo, si se encuentran uno verde y uno gris, el estado camaleón cambia a $(v-1,g-1,a+2)$.

El problema ahora es descubrir qué es lo que permanece invariante de un estado a otro bajo la operación permitida. Para empezar, podemos observar que una de las componentes del estado no cambia su paridad, mientras que las otras dos sí. Pero esta propiedad no nos sirve, puesto que el estado final (dos pares y un impar) es compatible con ella. Debemos pues buscar otra. ¿Qué es lo que no cambia en tres números cuando dos se disminuyen en la unidad y el otro aumenta en dos?

Tratando de responder esa pregunta podemos dejar transcurrir la tarde sin que la respuesta llegue. Pero, si se ha tenido un buen entrenamiento en el problem solving de olimpiada, es posible que la respuesta llegue pronto. Para ello puede ayudar cambiar la pregunta a ¿qué propiedad tienen los números -1,-1,2? La respuesta útil en este caso es que ¡son equivalentes respecto al módulo 3!

Y ya está. Porque, respecto al módulo 3, el estado inicial es equivalente a $(0,1,2)$. Así que el estado camaleón va a mantener la propiedad de que sus componentes son equivalentes a 0,1,2 respecto al módulo 3 --en algún orden. (Porque la operación permitida equivale a sumarle un 2 a cada una de ellas --respecto al módulo 3.)

Así que la respuesta es que no es posible lograr el estado final en que todos los 57 camaleones sean todos del mismo color. (Pues $(57,0,0)$ es equivalente a $(0,0,0)$--respecto al módulo 3.)

Problema de las hormigas en un rectángulo

En tres de los vértices de un rectángulo dibujado en el plano hay tres hormigas. Cada hormiga, en su turno, camina a lo largo de la línea recta que es paralela a la recta determinada por las otras dos hormigas. ¿Es posible que, eventualmente, las hormigas se coloquen en los puntos medios de tres lados del rectángulo?

Solución

Sea $ABCD$ el rectángulo y suponga que las hormigas están colocadas en los vértices $A,B,C$. Si la hormiga en $C$ se mueve, entonces se mueve a un punto $D'$ sobre el lado $CD$ (porque se mueve en la recta paralela a $AB$).

Ahora, después de experimentar quizá un poco, es relativamente fácil ver que la propiedad invariante ante las transformaciones es el área del triángulo formado por la posición de las hormigas. ($ABC$ y $ABD'$ son dos triángulos con la misma base $AB$ y la misma altura --dado que $D'$ está en la paralela por $C$ al lado $AB$.) Se deja al lector completar el argumento. (Bajo la hipótesis de que sabe la fórmula del área de un triángulo.)

Comentarios finales

Los ejemplos presentados deberían conducir al aprendiz (eso espero) a una comprensión del concepto de invariantes (propiedad invariante bajo una transformación). En el primer ejemplo se presentó una discusión sobre la posible génesis o descubrimiento de la propiedad invariante. Pero, como dice Engel, "no hay métodos sistemáticos para encontrar invariantes, sólo heurísticas." Enseguida tres ejercicios para ejercitar el descubrimiento de la invariante.

• Al sumar los dígitos de un número de manera repetida para formar nuevos números ¿cuál es la propiedad invariante?
• Un círculo se divide en 6 sectores y se colocan los números 1,0,1,0,0,0 uno en cada sector en el sentido de las manecillas del reloj. Si la operación permitida es aumentar en una unidad dos números adyacentes ¿cuál es la propiedad invariante? --la que nos puede resolver la incógnita de si es posible eventualmente igualar todos los números.
• Empezando con los números $1,2,\ldots,4n-1$, se aplica de manera repetida la operación de reemplazar dos de los números por su diferencia. Demostrar que, después de $4n-2$ movidas queda un par.

Los saluda
jmd