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?
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$.
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.