Cono 2022 P4

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Cono 2022 P4

Mensaje sin leer por Gianni De Rico »

Ana y Beto juegan en un tablero cuadriculado de $2022\times 2022$ casillas. Ana colorea de rojo los lados de algunas casillas en el tablero, de modo que ninguna casilla tenga dos lados rojos que comparten un vértice. A continuación, Beto debe colorear un camino azul que una dos de las cuatro esquinas del tablero, siguiendo los lados de las casillas y sin usar ningún segmento rojo. Si Beto lo logra es el ganador, en caso contrario gana Ana. ¿Quién tiene estrategia ganadora?
♪♫ do re mi función lineal ♪♫
Fedex

COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi
FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021 OFO - Jurado-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 269
Registrado: Mar 31 Dic, 2019 2:26 am
Medallas: 11
Nivel: 3
Ubicación: Rosario, Santa Fe
Contactar:

Re: Cono 2022 P4

Mensaje sin leer por Fedex »

Spoiler: mostrar
Supongamos que en vez de pintar los segmentos de rojo, los borramos. Sean $A$, $B$, $C$, $D$ los vértices del cuadrado. Decimos que un vértice de casilla es $A$-alcanzable si existe un camino que lleve desde este vértice hasta $A$ pasando por lados de las casillas. Igualmente definimos esto para $B, C, D$.

Lema: Dado un vértice del cuadrado $X$ existe un punto $X$-alcanzable en uno de los lados del cuadrado que no contienen a $X$.
Demostración: Rotamos el tablero para que $X$ quede abajo a la izquierda y a todos los vértices de casillas del tablero les asignamos coordenadas enteras (a $X$ le corresponde el $(0,0)$) sea $v(x,y)$ el vértice $X$-alcanzable que satisface que $x+y$ es máximo, afirmo que este punto satisface lo que queremos.
Supongamos que no, luego existe un vértice sobre él y otro a su derecha con los que $v$ no está conectado (por la maximalidad de $x+y$). Pero esto es absurdo porque deberían haberse borrado $2$ lados de un cuadrado que forman una $L$. Absurdo!

Supongamos que Beto no puede alcanzar lo pedido, entonces cada vértice es $X$-alcanzable para lo sumo un $X$.
Consideramos un camino $l$ que lleva desde $A$ a un vértice $A$-alcanzable que $WLOG$ está en el interior de $BC$, ahora, por nuestra suposición todos los puntos $B$-alcanzables están sobre la región que delimita $l$ y contiene a $B$ llamémosla $r(l)$. También consideramos el camino $L$ formado por los lados $AD$ y $DC$ que va desde $A$ hasta $C$ y definimos igualmente $r(L)$. Como $r(l)$ está claramente contenido en $r(L)$ la región de puntos $B$-alcanzables está contenida sobre el cuadrado de $2021\times 2021$ que delimita el interior de $r(L)$.
Pero esto es un absurdo, porque por el lema debería haber un punto $B$-alcanzable sobre $AD$ o $DC$.

Luego Beto siempre puede formar este camino.
1  
This homie really did 1 at P6 and dipped.
Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Oro-OFO 2019 FOFO 9 años - Jurado-FOFO 9 años COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020
FOFO Pascua 2020 - Jurado-FOFO Pascua 2020 COFFEE - Jurado-COFFEE Carolina González COFFEE - Jurado-COFFEE Ariel Zylber COFFEE - Jurado-COFFEE Iván Sadofschi FOFO 10 años - Jurado-FOFO 10 años
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Jurado-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: Cono 2022 P4

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Por comodidad, supongamos que todos los segmentos que Ana no pinta de rojo se pintan automáticamente de azul, después Beto elige un camino y listo (o los despinta, como prefieran pensarlo).
Vamos a demostrar que Beto gana para cualquier tablero de $m\times n$, con $m,n\in \mathbb{N}$. Lo vamos a hacer por inducción en $m+n$. El caso base $m=n=1$ es cierto, porque el tablero es una casilla, así que tiene al menos un lado azul, que une dos esquinas del tablero. Supongamos entonces que Beto gana para todos los tableros de $m\times n$, con $m+n=k$ para cierto $k\in \mathbb{N}$. Vamos a ver que Beto gana en los tableros de $m\times n$ que cumplen $m+n=k+1$.
Usamos este dibujo:
Cono 2022 P4 (1).png
Miremos la casilla de la esquina superior izquierda del tablero, no puede ocurrir que tanto su lado izquierdo como su lado superior sean rojos, de modo que alguno de ellos es azul, supongamos sin pérdida de generalidad que su lado izquierdo es azul (el otro caso sale de la misma forma), entonces $AB$ es azul.
El dibujo nos queda así:
Cono 2022 P4 (2).png
Si $m=1$, entonces $AB$ ya es un camino que une dos esquinas, de modo que Beto ganó. Supongamos entonces que $m>1$. La forma en la que Ana pinte los lados de las casillas de la fila superior del tablero como mucho imponen restricciones a la forma en la que pinta las casillas del subtablero $BCDE$ de $(m-1)\times n$ que se obtiene al quitar la fila superior del tablero, como $m+n=k+1$, entonces $m-1+n=k$, de modo que por hipótesis inductiva tenemos que Beto puede ganar en este subtablero. Si $EF$ es azul, entonces cualquier camino azul entre dos esquinas en $BCDE$ se puede extender a un camino azul entre dos esquinas de $ACDF$ (por ejemplo, un camino azul que une $C$ con $E$ se extiende a un camino azul que une $C$ con $F$ agregando $EF$):
Cono 2022 P4 (3).png
Supongamos entonces que $EF$ es rojo.
El dibujo nos queda así:
Cono 2022 P4 (4).png
Miremos los lados verticales de la fila superior del tablero, empezando desde $EF$. Sea $PQ$ el primer lado vertical azul (puede pasar que $PQ=AB$), entonces todos los lados verticales entre $PQ$ y $EF$ son rojos, de modo que todo el segmento $PF$ es azul y todo el segmento $QE$ es azul, porque no puede haber una casilla con dos lados rojos adyacentes. Entonces el camino $E-Q-P-F$ es un camino azul que une $E$ con $F$, y de la misma forma que antes tenemos que camino azul entre dos esquinas en $BCDE$ se puede extender a un camino azul entre dos esquinas de $ACDF$.
Cono 2022 P4 (5).png
Esto completa la inducción.

Entonces Beto gana para cualquier tablero de $m\times n$, con $m,n\in \mathbb{N}$. En particular, gana para un tablero de $2022\times 2022$.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
♪♫ do re mi función lineal ♪♫
Responder