Hay procesos que parecen poder alargarse indefinidamente: arreglas una cosa, estropeas otras, y el juego vuelve a empezar. Pero a veces existe una medida escondida que siempre baja, aunque no se vea a simple vista.
Las monedas que no pueden jugar para siempre
Enunciado
Hay varias monedas en fila. Cada una muestra cara o cruz.
Un movimiento consiste en elegir una moneda que esté en cruz, convertirla en cara, y cambiar también el estado de todas las monedas que están a su izquierda: las caras pasan a cruz, y las cruces pasan a cara.
¿Puede existir una secuencia infinita de movimientos?
Ver solución
Solución
No puede haber una secuencia infinita.
La idea es asignar un valor a cada configuración.
Numeramos las monedas de izquierda a derecha y damos a sus posiciones los valores:
Es decir, la moneda más a la izquierda vale 1, la siguiente vale 2, la siguiente vale 4, y así sucesivamente.
Ahora interpretamos:
cara = 0; cruz = 1.
Así, cada fila de monedas representa un número.
Cuando eliges una moneda en cruz, esa moneda pasa de 1 a 0. Supongamos que su valor es $2^k$.
Las monedas a su izquierda tienen valores menores:
Al cambiar todas esas monedas, como mucho pueden aumentar el número en:
Pero la moneda elegida baja el número en:
Así que el número total disminuye al menos en 1.
Cada movimiento hace bajar un número entero no negativo. Por tanto, el proceso no puede continuar para siempre.
Respuesta: no. Toda secuencia de movimientos termina necesariamente.