Provincial 2018 - Nivel 2 - Problema 2

Avatar de Usuario
Matigelp97

OFO - Medalla de Plata
Mensajes: 34
Registrado: Dom 14 Sep, 2014 2:30 pm
Medallas: 1
Nivel: 1

Provincial 2018 - Nivel 2 - Problema 2

Mensaje sin leer por Matigelp97 » Sab 25 Ago, 2018 9:19 am

Ana y Beto juegan en un tablero de $6$ $X$ $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.

Avatar de Usuario
Turko Arias

Colaborador OFO - Medalla de Plata
Mensajes: 227
Registrado: Lun 28 Nov, 2011 11:39 am
Medallas: 2
Nivel: Ñandú
Ubicación: La Plata, Provincia de Buenos Aires

Re: Provincial 2018 - Nivel 2 - Problema 2

Mensaje sin leer por Turko Arias » Lun 17 Sep, 2018 4:40 am

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 $6X6$ 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$
1  

Responder