Problema 4 de la fase nacional de 2017 de la Olimpiada Matemática Española Se dirige a una edad de: 16 - 17 años
Se dispone de una fila de 2018 casillas, numeradas consecutivamente de 0 a 2017.
Inicialmente, hay una ficha colocada en la casilla 0.
Dos jugadores A y B juegan alternativamente, empezando A, de la siguiente manera:
En su turno, cada jugador puede, o bien hacer avanzar la ficha 53 casillas, o bien hacer retroceder la ficha 2 casillas, sin que en ningún caso se sobrepasen las casillas 0 ó 2017.
Gana el jugador que coloque la ficha en la casilla 2017.
¿Cuál de ellos dispone de una estrategia ganadora, y cómo tendría que jugar para asegurarse ganar?
Solución:
Empezamos pensando en el principio del juego, y en el final. Sobre todo en el final.
Al primer jugador que mueva le llamamos A y al segundo B.
La idea es que al principio A no tiene opciones: sólo puede mover 53 hacia delante, y situarse en la casilla 53. A partir de ahí, B tiene la posibilidad de mover a 106, o bien retroceder a 51.
Y por tanto es el que puede empezar a pensar que puede elegir.
Veamos el final.
Llamemos G a una posición ganadora antes de jugar y P a una posición perdedora. Veremos si G se puede lograr que sea B o que sea A.
El ultimo movimiento para ganar es mover 53 hacia delante, así que tiene que venir del 2017 – 53 = 1964, que es de tipo G.
Un jugador debería evitar mover a esa casilla, así que debe venir de 1966 sin remedio.
Para llegar ahí, puede haber movido desde 1968 o bien desde 1966 – 53 = 1913, así que son posiciones G, que debe evitar darle el rival a toda costa, así que si mueve ahí no puede evitarlo.
Quiero decir, si está en 1970 es inevitable, porque no puede mover hacia delante (es una posición P), pero si está en 1915 no tiene sentido que mueva hacia 1913, debería mover hacia adelante, aunque 1915 + 53 = 1968 y le daría al otro jugador una posición ganadora. Pero eso lo podemos estudiar luego.
Ya podemos tener por tanto una serie de posiciones perdedoras y ganadoras mayores que 1964:
Perdedoras: 1966, 1970, 1974, ….
Ganadoras: 1964, 1968, 1972, ..
Fijémonos ahora en el número 1963. Si estás ahí y avanzas, vas al 2016, que es una ganadora, y le estarías dando la partida a tu rival.
Pero si retrocedes 2, vas al 1961, y tu rival te manda a 2014, que es de las perdedoras…
Por lo tanto, 1963 es perdedora. En cualquier caso, tu rival te manda al 2014.
La diferencia entre 1963 y 2014 es exactamente 51. En este caso, se puede trabajar un poco más el razonamiento, pero la clave es que uno siempre puede hacer que el rival se encuentre 51 más arriba que antes.
Porque si el rival avanza 53, puede retroceder 2, y si retrocede 2, avanzas 53. Llamaremos a este método “jugar el contrario”. Descubrir esto es vital para resolver el problema.
Ahora, vamos a ver qué diferencia hay entre 53 (la posición en la que empieza B) y 1964, y cuántas veces puedes hacer avanzar al rival 51 hasta llegar a la zona que hemos estudiado parcialmente:
Resulta que 1964 – 53 = 1911, y 1911/51 da algo más de 37. Luego 53 + 38*51 = 1991, desde donde podríamos forzar el juego, pero el problema es que es impar…
Y si hacemos un primer movimiento con B hacia el 106, y sumamos 37*51 también llegamos a un impar…
Eso significa que hay que estudiar los impares también.
Veamos entonces los impares…
Si caemos en el 1965, no hay más remedio que ir al 1963, que es perdedora. Luego 1965 es ganadora.
En cambio, 1967 es perdedora, porque no tienes más opción que bajar al 1965…
Luego tenemos la cosa fácil:
1965, 1969, 1973, … (en general los que son uno más que un múltiplo de 4) ganadora
1963, 1967, 1971, … (en general los que son uno menos que un múltiplo de 4), perdedora.
Es decir, que empezamos en el 0, A pasa al 53. Y, efectivamente, uno de los dos tiene posibilidad de ganar, pero es el A. Veámoslo:
A partir de ese momento, A lleva al B, jugando de forma contraria a él, de 51 en 51, durante 38 jugadas. En ese momento, le toca a B y estaría en el 1991.
Desde ahí, B no tiene más remedio que bajar 2 y A también, así que B va bajando de 4 en 4 hasta el 1963.
Ahora, el B puede elegir, pero A juega a la contra y le lleva al 2014.
De nuevo el B baja de 2 y A también, así que B se va encontrando 4 más abajo hasta el 1966.
La última vez que baja 2, B lleva a A al 1964, desde donde sumando 53 llega a al 2017 y por tanto A gana la partida sin remedio, aunque se vea obligado a mover de forma única en la primera jugada.
