Problema 5 de la fase catalana de la 57 Olimpiada Matemática Española (2020/21) Se dirige a una edad de: 16-17 años
Ana y Bernat juegan un juego sobre un tablero ajedrezado de dimensiones 2020×2020.
Decimos que una colección de piezas puestas en ese tablero está arrinconada (en la esquina inferior izquierda) si no hay ninguna casilla vacía de forma que la casilla inmediatamente superior o inmediatamente a la derecha de ella contenga una pieza, como se muestra en la figura.
Inicialmente, hay 2020 piezas colocadas en una posición arrinconada.
En turnos alternos, comenzando por Ana, cada jugador retira dos piezas de casillas adyacentes (con un lado en común), con la condición de que la configuración restante siga siendo arrinconada.
Pierde el jugador que no puede hacer un movimiento.
Determina cuál de los dos jugadores ganará en función de la posición inicial de las 2020 piezas, suponiendo que ambos jueguen de forma óptima.
Solución:
Es un problema mucho más complejo de lo que parece.
Para empezar, tratemos casos más sencillos. Si probamos la combinación con sólo 4 fichas, tenemos que, empecemos en la combinación que empecemos, gana Bernat, ya que siempre que Ana pueda jugar, le deja 2 a Bernat en una posición arrinconada, es decir, que una de ellas debe estar en la esquina y la otra en una de las casillas blancas, así que perfectamente puede jugar su turno y Ana se queda sin poder hacer nada.
La situación para 6 fichas es más variada. Si la posición inicial es una en especial (la que forma un triángulo, la de la esquina, las dos blancas en contacto con ella, y las tres negras en contacto con ellas) pierde Ana, ya que no puede hacer su movimiento sin que dejen de estar arrinconadas. Pensemos que en ese caso, lo que sucede es que cualquier jugada de Ana debe incluir una de las fichas blancas, y una negra, y es evidente que en cualquier caso deja a otra negra con un cuadro vacío bajo o a la izquierda, luego no es arrinconada.
Sin embargo, en cualquier otra circunstancia, Ana puede jugar, y le pasa una situación perdedora a Bermat. Luego pierde Bernat. Vamos a estudiar una de estas situaciones.
Vemos que Ana tiene dos recursos: jugar con la blanca más a la derecha y llevarse una negra de las que le acompañan, de forma que queda una de las posiciones de 4 que ya hemos analizado.
Después de este experimento, sacamos varias conclusiones. Existen jugadas en las que, aunque hay fichas, uno no puede hacer su jugada, y parece ser que en ese caso las fichas forman un triángulo, la persona a la que le toca jugar no puede jugar. El número de fichas debe ser par, así que el triángulo sería de 3 fichas de lado, o de 4, o de 6, o de 7, o de 8. En esos casos, si a lo largo de las partidas se llega a esas construcciones, la persona no va a poder jugar y perderá.
La clave es entender de qué forma se puede predecir, cuando tenemos una gran cantidad de fichas (2020), si estamos en una de las situaciones en las que el juego se para antes de acabar, o llega al final, en cuyo caso la que tendría una situación desfavorable es Ana, ya que coincidiría que después de 1010 pares de movimientos, le toca jugar y no hay piezas.
Por otra parte, si llegamos a una situación con 6 fichas dispuestas de la forma que hemos visto anteriormente (en 3 diagonales) o 10 fichas (4 diagonales) le tocaría jugar a Bernat (quedan 3 o 5 movimientos con fichas, pero no se puede seguir).
Sin embargo, si la situación es con 7 diagonales (28 fichas) u 8 diagonales (36 fichas), quedan 14 o 18 movimientos, de forma que a quien le tocaría jugar es a Ana, que sería la que perdería. ¿Cómo podemos identificar esas situaciones?
Si atendemos a que en cada movimiento se retiran una ficha en una casilla blanca y una ficha en una casilla negra, nos daremos cuenta de que la diferencia entre ambos tipos de fichas se mantiene constante, por lo que si esa diferencia es una característica del número de diagonales que quedan al final, resulta que no tendremos más remedio que llegar a esa situación desde una determinada situación de partida.
Observamos que el caso de 3 diagonales, la diferencia entre blancas y negras ocupadas es 2 a favor de las negras, mientras que para 4 diagonales es 2 a favor de las blancas. Para el caso en que lleguemos a la final de la partida, debería de haber la misma cantidad de negras y blancas. Luego la disposición inicial parece que decide hasta dónde llegaremos.
Otra pista es que en el caso de 7 diagonales, el número de fichas negras sería 1 + 3 + 5 + 7 = 16, y el de blancas 2 + 4 + 6 = 12, luego hay una diferencia de 4 fichas negras. Y en el caso de 8 diagonales, habría una diferencia de 4 hacia las fichas blancas.
Sólo nos queda demostrar que esto es algo general, y que una posición en la que no haya un número entero de diagonales siempre se puede seguir jugando.
En efecto, siempre se puede seguir jugando si no tenemos un número entero de diagonales. Al estar las fichas arrinconadas, las líneas están totalmente rellenas de fichas hasta la última ficha. Si no están completas las diagonales, o bien hay una fila en la que hay al menos dos fichas más que en la anterior, en cuyo caso se pueden quitar las dos últimas, o bien hay dos filas iguales, en cuyo caso, la primera vez que ocurra se pueden quitar las dos últimas fichas de estas dos filas.
Para que exista la posibilidad de que se llegue a una situación en la que hay n diagonales enteras ocupadas, con n impar, el número de fichas negras sería (1 + n)·(1 + n)/4 = (n² + 2n + 1)/4 y el número de fichas blancas sería de (2 + n – 1)·(n – 1)/4 = (n² – 1)/4, usando progresiones aritméticas para sumar las dos progresiones, y la diferencia sería exactamente de (2n+2)/4 = (n + 1)/2 fichas (a favor de las negras). Eso sólo puede suceder, evidentemente, si n es de la forma 4k – 1, ya que no puede haber una diferencia impar entre blancas y negras.
Por otra parte, si n es par y queremos tener n diagonales enteras, entonces el número de fichas negras es de (1 + n – 1)·n/4 = n²/4, y el número de fichas blancas es de (2 + n)·n/4 = (n² + 2n)/4, de forma que la diferencia esta vez será en favor de las blancas, y de 2n/4 = n/2, cosa que sólo podrá ocurrir si n es múltiplo de 4, por similares razones.
De esta forma, según que las fichas arrinconadas en el tablero tengan una u otra diferencia en favor de las blancas o las negras, conociendo esa diferencia podremos deducir a cuántas diagonales enteras vamos a acabar, independientemente de cómo juguemos. Porque si pudiesen quedar al final menos diagonales, la diferencia sería menor que la que es, y eso es imposible.
Por ejemplo, si hay más blancas que negras, pongamos 8 blancas más que negras, llegaremos a un número par de diagonales enteras, exactamente 16, y no podremos continuar, luego ganaría Ana, ya que le tocaría jugar a Bernat cuando llegásemos a esa situación.
Una vez decidido esto, para saber quién gana, debemos ver la paridad de las jugadas que quedan, ya que el número total de diagonales (la n), determina que al final quedarán (1 + n)·n/2 = (n² + n)/2 fichas, y el número (n² + n)/4 será el número de jugadas. Si este número es par, ganará Bernat (como en el caso de que n = 7 o n = 8) mientras que si es impar, ganará Ana (como en el caso en que n = 3 o n = 4).
Así que el invariante que determina la partida, en realidad, no es la posición en sí misma, si no la diferencia entre número de casillas blancas y negras ocupadas.
Esta diferencia debe ser par, ya que inicialmente hay 2020 fichas, y si la cantidad de fichas en posición blanca es par, también lo es la cantidad en posición negra, y viceversa.
Si hay 2k blancas más que negras, quedarán al final 2k diagonales, y (4k² + 2k)/2 = 2k² +k fichas, así que el valor de k par nos dirá que gana Ana y el valor de k impar nos dice que gana Bernat. Si hay 2k negras más que blancas, en ese caso, (n + 1)/2 = 2k, luego n = 4k – 1, y quedarán al final ((4k – 1)² + (4k – 1))/4 jugadas, y eso es (16k² – 4k)/4 = 4k² – k, cuya paridad en realidad depende de nuevo de k, es decir, que si k es par sigue ganando Ana y si k es impar, Bernat.