Problema 7 de la Fase Local de la LVI OME 2020
Se dirige a una edad de: 16-17 años

Ana y Bernardo juegan al siguiente juego.

Se empieza con una bolsa que contienen n >= 1 piedras.

En turnos sucesivos, y empezando por Ana, cada jugador puede hacer los siguientes movimientos:

Si el número de piedras de la bolsa es par, el jugador puede coger una sola piedra o la mitad de las piedras.

Si el número de piedras de la bolsa es impar, tiene que coger una única piedra.

El objetivo del juego es coger la última piedra.

Determinar para qué valores de n tiene Ana una estrategia ganadora.

Solución:

En este tipo de problemas, hay que estudiar una estrategia hasta tener una conjetura válida, y siempre se empieza por el final.

Si al comienzo hay una única piedra, Ana gana seguro (es una cantidad por tanto ganadora).

Si hay 2, Ana se ve obligada a tomar una y pierde. 2 es por tanto un número perdedor.

Si hay 3, Ana gana automáticamente (3 es ganador).

Si hay 4, Ana puede quedarse con 2 y pasarle un número perdedor a Bernardo. 4 es, por tanto, un número ganador también.

Si hay 5, estamos ante un número perdedor.

Si hay 6, es un número ganador si quitamos uno.

Si hay 7, es perdedor.

Si hay 8, es ganador quitando uno.

Creo que ya tenemos suficiente para hacer una conjetura. Todo número impar mayor que 3 es perdedor, y todo número par mayor que 2 es ganador. El 1 es ganador, 2 es perdedor y 3 es ganador.

Demostremos la veracidad de la conjetura por inducción.

Hemos visto que es cierto si n es menor que 7, supongamos que es cierto hasta un determinado número n (es decir, todos los menores que n, si son pares, te permiten ganar, y si son impares, te hacen perder).

Supongamos que n es impar. Puesto que tenemos que sacar una única piedra, devolveremos un valor par a nuestro adversario, que le permitirá ganar.

Si n es par, estudiaremos si n/2 es impar o no. Si es impar, quitaremos la mitad de piedras, y si no lo es, sólo quitaremos una. En cualquier caso, dejaremos un número impar mayor que 3 (recuerda que hemos estudiado hasta el 6), por lo que será un número perdedor y habremos ganado.

Esto demuestra que si el número de partida es par mayor que 2, o impar menor que 5, ganamos. En caso contrario, no. Y la estrategia es la descrita.

Un ejemplo con el 200, pasaríamos a 199, 198, 99, 98, 49, 48, 47, 46, 23, 22, 11, a 10, a 5, a 4, a 2 a 1 y ganamos.