IMO 2018 - P4

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 753
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

IMO 2018 - P4

Mensaje sin leer por Gianni De Rico » Mar 10 Jul, 2018 9:40 am

Un lugar es un punto $(x,y)$ en el plano tal que $x$, $y$ son ambos enteros positivos menores o iguales que $20$.
Al comienzo, cada uno de los $400$ lugares está vacío. Ana y Beto colocan piedras alternadamente, comenzando con Ana. En su turno, Ana coloca una nueva piedra roja en un lugar vacío tal que la distancia entre cualesquiera dos lugares ocupados por piedras rojas es distinta de $\sqrt{5}$. En su turno, Beto coloca una nueva piedra azul en cualquier lugar vacío. (Un lugar ocupado por una piedra azul puede estar a cualquier distancia de cualquier otro lugar ocupado.) Ellos paran cuando alguno de los dos no pueda colocar una piedra.
Hallar el mayor $K$ tal que Ana pueda asegurarse de colocar $K$ piedras rojas, sin importar cómo Beto coloque sus piedras azules.
[math]

Avatar de Usuario
ésta

Colaborador OFO - Jurado
Mensajes: 293
Registrado: Sab 16 Oct, 2010 4:55 pm
Medallas: 4
Nivel: Ñandú

Re: IMO 2018 - P4

Mensaje sin leer por ésta » Mar 10 Jul, 2018 6:40 pm

Spoiler: mostrar
Veamos que el mayor $K$ posible es $100$. Para eso tenemos que ver dos cosas, que Ana puede asegurarse colocar $100$ piedras y que Beto puede asegurarse de que Ana no coloque más de $100$ piedras.

Veamos primero que Ana puede asegurarse colocar $100$ piedras. Pintamos los lugares de blanco y negro alternadamente de modo que dos lugares a distancia $1$ tengan distinto color. La estrategia de Ana será jugar siempre en lugares blancos. Como no hay dos lugares blancos a distancia $\sqrt{5}$, Ana siempre podrá jugar en cualquier lugar blanco libre. Como en total hay $200$ lugares blancos, por más que Beto juegue siempre en lugares blancos, Ana se asegura jugar al menos $100$ turnos.

Ahora veamos que Beto se puede asegurar que Ana no juegue más de $100$ piedras. Dividimos los $20 \times 20$ lugares en $5 \times 5$ subregiones de $4 \times 4$ lugares. Pintamos los lugares de cada subregión de $4$ colores de esta manera:
Imo2018P4.png
La estrategia de Beto es la siguiente, cada vez que juega Ana, mira la subregión donde jugo y juega en el único lugar del mismo color que podría volver a jugar Ana (notar que no importa en donde juegue Ana siempre bloquea dos de los otros lugares del mismo color). De esta manera se asegura que Ana solo pueda ocupar un lugar de cada color por subregión. Como hay $25$ subregiones y $4$ colores por subregión esto asegura que Ana juega a lo sumo $100$ veces.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Imagen

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial
Mensajes: 753
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 1
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IMO 2018 - P4

Mensaje sin leer por Gianni De Rico » Mar 10 Jul, 2018 6:42 pm

Hermoso problema, el mejor de la prueba
Spoiler: mostrar
Empezamos transformando el enunciado en algo más lindo y manejable, y de paso lo generalizamos un poquito:
"Sea $n$ un entero positivo. Ana y Beto juegan por turnos en un tablero cuadriculado de $4n\times 4n$. Comienza Ana, en su turno, coloca un caballo de ajedrez en una casilla vacía que no esté siendo atacada por un caballo. Beto, en su turno, coloca una moneda en una casilla vacía. El juego termina cuando alguno de los dos no puede jugar.
Hallar la máxima cantidad de caballos que puede colocar Ana en el tablero."

Veamos que el problema sigue siendo el mismo:
Spoiler: mostrar
Como los puntos tienen coordenadas enteras, la única forma de que dos puntos $(x_1,y_1),(x_2,y_2)$ estén a una distancia de exactamente $\sqrt{5}$ es que ocurra $|x_2-x_1|=1\wedge |y_2-y_1|=2$ o $|x_2-x_1|=2\wedge |y_2-y_1|=1$, ya que si la diferencia de alguna de sus coordenadas es $0$, la distancia será entera, pero $\sqrt{5}$ no lo es. Si las dos diferencias son $1$, por Pitágoras la distancia será $\sqrt{2}$. Y si al menos una diferencia es mayor o igual a $3$, nuevamente por Pitágoras la distancia será de al menos $\sqrt{9}>\sqrt{5}$. Si pensamos los lugares como casillas de un tablero de $20\times 20$, vemos que la diferencia entre sus coordenadas se traduce en "dos casillas en una dirección y una casilla en la dirección perpendicular", es decir, exactamente como ataca el caballo de ajedrez. Como las piedras azules de Beto pueden estar a cualquier distancia de otra piedra y solamente nos importa que ocupan un lugar, las reemplazamos por monedas.
Afirmo que el mayor valor posible es $K=4n^2$
Veamos primero que Ana siempre puede colocar $n^2$ caballos en el tablero:
Usamos la coloración de ajedrez, como es un tablero de $4n\times 4n$, hay exactamente $8n^2$ casillas de cada color. Ahora, notemos que un caballo nunca ataca a casillas del mismo color, luego, Ana puede jugar siempre en un mismo color sin temor de quedarse sin espacio.
Supongamos sin pérdida de generalidad que juega en las blancas. Luego, por cada casilla que ocupe Ana, Beto puede ocupar otra casilla blanca, y como la cantidad de casillas blancas es par, resulta que los dos ocupan la misma cantidad de casillas. Por lo tanto, Ana puede colocar al menos $\frac{8n^2}{2}=4n^2$ caballos en el tablero.

Veamos ahora que Beto puede asegurarse de que Ana no coloque más de $4n^2$ caballos en el tablero:
Dividimos el tablero en $\frac{4n}{4}\cdot \frac{4n}{4}=n^2$ subtableros disjuntos de $4\times 4$. Cuando Ana juega en una casilla de alguno de esos subtableros, Beto juega en la casilla simétrica respecto del centro del subtablero (como es de $4\times 4$ puede hacerlo siempre, ya que no hay una casilla que esté en el centro), con esto se ve que Ana puede ocupar como mucho $4$ casillas de ese subtablero:
$\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\
\hline
3 & 4 & 1 & 2 \\
\hline
2 & 1 & 4 & 3 \\
\hline
4 & 3 & 2 & 1 \\
\hline
\end{array}$
Cada casilla y su simétrica tienen el mismo número, cada casilla bloquea a las otras dos que tienen su número y no son su simétrica respecto del centro del subtablero. Entonces Ana puede poner a lo sumo un caballo por número, se sigue que puede poner a lo sumo $4$ caballos en cada subtablero. Como hay $n^2$ subtableros, Ana puede poner a lo sumo $4n^2$ caballos en el tablero.

Entonces vimos que Ana siempre puede asegurarse de poner $4n^2$ caballos y Beto siempre puede evitar que Ana ponga más de $4n^2$ caballos en el tablero. Por lo tanto $4n^2$ efectivamente es el máximo.

En el caso de un tablero de $20\times 20$ tenemos $n=5$ y por lo tanto el máximo es $4\cdot 5^2=100$ caballos.
[math]

Avatar de Usuario
Joacoini

OFO - Medalla de Plata
Mensajes: 104
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 1
Nivel: 2
Ubicación: Ciudad Gotica

Re: IMO 2018 - P4

Mensaje sin leer por Joacoini » Mié 11 Jul, 2018 6:01 pm

Gianni De Rico escribió:
Mar 10 Jul, 2018 6:42 pm
Hermoso problema, el mejor de la prueba
Spoiler: mostrar
Empezamos transformando el enunciado en algo más lindo y manejable, y de paso lo generalizamos un poquito:
"Sea $n$ un entero positivo. Ana y Beto juegan por turnos en un tablero cuadriculado de $4n\times 4n$. Comienza Ana, en su turno, coloca un caballo de ajedrez en una casilla vacía que no esté siendo atacada por un caballo. Beto, en su turno, coloca una moneda en una casilla vacía. El juego termina cuando alguno de los dos no puede jugar.
Hallar la máxima cantidad de caballos que puede colocar Ana en el tablero."

Veamos que el problema sigue siendo el mismo:
Spoiler: mostrar
Como los puntos tienen coordenadas enteras, la única forma de que dos puntos $(x_1,y_1),(x_2,y_2)$ estén a una distancia de exactamente $\sqrt{5}$ es que ocurra $|x_2-x_1|=1\wedge |y_2-y_1|=2$ o $|x_2-x_1|=2\wedge |y_2-y_1|=1$, ya que si la diferencia de alguna de sus coordenadas es $0$, la distancia será entera, pero $\sqrt{5}$ no lo es. Si las dos diferencias son $1$, por Pitágoras la distancia será $\sqrt{2}$. Y si al menos una diferencia es mayor o igual a $3$, nuevamente por Pitágoras la distancia será de al menos $\sqrt{9}>\sqrt{5}$. Si pensamos los lugares como casillas de un tablero de $20\times 20$, vemos que la diferencia entre sus coordenadas se traduce en "dos casillas en una dirección y una casilla en la dirección perpendicular", es decir, exactamente como ataca el caballo de ajedrez. Como las piedras azules de Beto pueden estar a cualquier distancia de otra piedra y solamente nos importa que ocupan un lugar, las reemplazamos por monedas.
Afirmo que el mayor valor posible es $K=4n^2$
Veamos primero que Ana siempre puede colocar $n^2$ caballos en el tablero:
Usamos la coloración de ajedrez, como es un tablero de $4n\times 4n$, hay exactamente $8n^2$ casillas de cada color. Ahora, notemos que un caballo nunca ataca a casillas del mismo color, luego, Ana puede jugar siempre en un mismo color sin temor de quedarse sin espacio.
Supongamos sin pérdida de generalidad que juega en las blancas. Luego, por cada casilla que ocupe Ana, Beto puede ocupar otra casilla blanca, y como la cantidad de casillas blancas es par, resulta que los dos ocupan la misma cantidad de casillas. Por lo tanto, Ana puede colocar al menos $\frac{8n^2}{2}=4n^2$ caballos en el tablero.

Veamos ahora que Beto puede asegurarse de que Ana no coloque más de $4n^2$ caballos en el tablero:
Dividimos el tablero en $\frac{4n}{4}\cdot \frac{4n}{4}=n^2$ subtableros disjuntos de $4\times 4$. Cuando Ana juega en una casilla de alguno de esos subtableros, Beto juega en la casilla simétrica respecto del centro del subtablero (como es de $4\times 4$ puede hacerlo siempre, ya que no hay una casilla que esté en el centro), con esto se ve que Ana puede ocupar como mucho $4$ casillas de ese subtablero:
$\begin{array}{|c|c|c|c|}
\hline
1 & 2 & 3 & 4 \\
\hline
3 & 4 & 1 & 2 \\
\hline
2 & 1 & 4 & 3 \\
\hline
4 & 3 & 2 & 1 \\
\hline
\end{array}$
Cada casilla y su simétrica tienen el mismo número, cada casilla bloquea a las otras dos que tienen su número y no son su simétrica respecto del centro del subtablero. Entonces Ana puede poner a lo sumo un caballo por número, se sigue que puede poner a lo sumo $4$ caballos en cada subtablero. Como hay $n^2$ subtableros, Ana puede poner a lo sumo $4n^2$ caballos en el tablero.

Entonces vimos que Ana siempre puede asegurarse de poner $4n^2$ caballos y Beto siempre puede evitar que Ana ponga más de $4n^2$ caballos en el tablero. Por lo tanto $4n^2$ efectivamente es el máximo.

En el caso de un tablero de $20\times 20$ tenemos $n=5$ y por lo tanto el máximo es $4\cdot 5^2=100$ caballos.
Spoiler: mostrar
La misma solución, tan solo agregó de que sirve para tableros de $4m×4n$ donde $K=4mn$
NO HAY ANÁLISIS.

Responder