Provincial 2018 - Nivel 2 - Problema 2

[Monazo]

Ana y Beto juegan en un tablero de $6\times 6$. En cada casilla del tablero Ana debe escribir una potencia de $2$, desde $2^0$ hasta $2^{35}$, sin repeticiones.
Beto dibuja en el tablero un camino cerrado y sin entrecruzamientos, que pasa sucesivamente de una casilla a otra vecina. No hay restricciones acerca de la longitud del camino. Luego Beto suma los números de las casillas por las que pasó el camino dibujado. Beto gana si esta suma tiene resto $1$ o resto $2$ en la división por $3$. Determinar si Ana puede ubicar las $36$ potencias de $2$ en el tablero para que Beto no pueda ganar.

Nota. Dos casillas son vecinas si comparten un lado.

[Turko Arias]

Spoiler: mostrar

Veamos que Ana puede lograr su objetivo. La idea se podría formalizar usando la noción de congruencias, pero la idea de fondo es bastante intuitiva y válida así que no es necesario hacerlo... A base de observación de los primeros casos uno puede deducir que si $k$ es par entonces $2^k$ va a tener resto $1$ en la división por $3$ y si $k$ es impar entonces $2^k$ va a tener resto $2$ en la división por $3$. Ahora bien, notamos que el si el número $a$ tiene resto $x$ en la división por un entero $m$ y el número $b$ tiene resto $y$ en la división por $m$, entonces el resto de dividir $a+b$ por $m$ va a ser el mismo que el de dividir $x+y$ por $m$. Luego, podemos pensar nuestro problema como distribuir $16$ números $1$ y $16$ números $2$ en el tablero de manera tal que si sumo las casillas de cualquier camino cerrado sin entrecruzamientos la suma siempre sea múltiplo de $3$. La idea ahora es pintar el tablero de $6 \times 6$ como si fuera un tablero de ajedrez. Notamos que cualquier camino cerrado sin entrecruzamientos empieza en una casilla de un color y termina en una casilla del color opuesto, es decir, por ejemplo, si empieza en una casilla blanca, para ser cerrado tiene que terminar en una casilla vecina, que va a ser si o si negra, por lo que pasa por la misma cantidad de casillas de color negro que de color blanco al final del recorrido. Luego, como $1+2=3$, podemos ubicar los $1$ (es decir las potencias pares de $2$) en las casillas blancas y los $2$ (es decir las potencias impares de $2$) en las casillas negras, y cualquier camino cerrado va a sumar la misma cantidad de unos que de dos, por lo que la suma siempre será un múltiplo de $3$ y Ana gana $\blacksquare$

[EduBottcha]

Una pregunta. La cosigna discuta que el camino puede tener cualquier longitud, pero utilizando esta misma lógica de respuesta, si el camino tiene un número impar de cuadrados recorridos, Beto terminaría ganando de cualquier manera. ¿Hay algo incorrecto en mí lógica?

Espero agradecido la respuesta

[Vakrank]

Una pregunta. La cosigna discuta que el camino puede tener cualquier longitud, pero utilizando esta misma lógica de respuesta, si el camino tiene un número impar de cuadrados recorridos, Beto terminaría ganando de cualquier manera. ¿Hay algo incorrecto en mí lógica?

Espero agradecido la respuesta

Fijate que dice que el camino es cerrado, es decir que terminará en la misma casilla que comenzó. Esto significa que se deberá mover la misma cantidad de casillas a la izquierda que a la derecha. Digamos que la cantidad de casillas que se mueve hacia la derecha es "n". En total, sus movimientos horizontales serán iguales a 2n. Lo mismo sucede con el movimiento vertical; por cada casilla que baje o suba, deberá subir o bajar la misma cantidad de casillas. Digamos que la cantidad de casillas que se mueve hacia arriba es "m"

En total la cantidad de casilleros recorridos es 2n + 2m que es par.