FOFO 9+1 Años - Problema 9

Problemas que aparecen en el Archivo de Enunciados.
Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 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 FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 149
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

FOFO 9+1 Años - Problema 9

Mensaje sin leer por AgusBarreto »

En un tablero de $m\times n$ los vértices de los bordes izquierdo y derecho del tablero están pintados de color rojo, mientras que los vértices de los bordes superior e inferior del tablero están pintados de color azul, los vértices de las esquinas tienen ambos colores. En cada casilla del tablero se dibuja una de las diagonales, que se usarán como "puentes" entre los vértices. Mateo quiere llevar su autito del Fofopoly de un lado al otro del tablero, usando los puentes existentes. Demostrar que Mateo puede elegir un color y un vértice sobre alguno de los bordes del tablero, de manera que sea posible cruzar el tablero usando los puentes y llegar un vértice del mismo color del lado opuesto del tablero.

Avatar de Usuario
AgusBarreto

OFO - Medalla de Bronce-OFO 2015 OFO - Medalla de Bronce-OFO 2016 OFO - Jurado-OFO 2017 FOFO 7 años - Jurado-FOFO 7 años OFO - Jurado-OFO 2018
FOFO 8 años - Jurado-FOFO 8 años OFO - Jurado-OFO 2019 FOFO Pascua 2019 - Jurado-FOFO Pascua 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 FOFO 10 años - Jurado-FOFO 10 años
Mensajes: 149
Registrado: Sab 15 Sep, 2012 6:28 pm
Medallas: 15
Nivel: Exolímpico
Ubicación: San Martín, Buenos Aires

Re: FOFO 9+1 Años - Problema 9

Mensaje sin leer por AgusBarreto »

Aquí vamos a publicar la solución oficial.

joa.fernandez

FOFO 8 años - Mención Especial-FOFO 8 años OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020
FOFO Pascua 2020 - Copa-FOFO Pascua 2020 FOFO 10 años - Copa-FOFO 10 años
Mensajes: 68
Registrado: Jue 20 Sep, 2018 9:40 pm
Medallas: 7
Nivel: 3

Re: FOFO 9+1 Años - Problema 9

Mensaje sin leer por joa.fernandez »

Está media desprolija pero la idea es linda:)

Solución:
Spoiler: mostrar
Vamos a definir algunas cosas.
Un camino será un conjunto de vértices tales que se pueda ir desde cualquier vértice a cualquier otro perteneciente al camino, solo recorriendo puentes que están "unidos" entre sí.
Un camino maximizador es aquel que contiene a todos los vértices posibles del mismo. Es decir, no existe vértice fuera del camino tal que, desde dentro del camino se pueda llegar a este utilizando los puentes.
Esta defición es la más rara (o más díficil de expresar sin que sea gráfica). Llamaremos camino encubridor al conjunto de vértices que "encierra" a un camino maximizador (funcionaría como el contorno de un camino maximizador). Para esto dejo unos ejemplos gráficos que ayudan a comprender al mismo (los puentes naranjas son parte del camino maximizador, mientras que los puentes celestes son del camino encubridor):
IMG_20201208_222828.jpg
Usando la misma notación del enunciado, $m$ será la dimensión del borde izquierdo y derecho, mientras que $n$ será la del borde inferior y superior.
Vamos a dejar $m$ fijo. Veremos por inducción en $n$ que siempre puede Mateo llegar con su auto del Fofopoly de un borde del tablero al borde opuesto.
Con $n = 1$ es trivialmente cierto, ya que en un tablero de $m\times 1$ cualquiera de los puentes del borde izquierdo están conectados con los del borde derecho.
Supongamos como hipótesis inductiva que vale para $n-1$.
Ahora, con $n$:
Primero que nada, vamos a usar coordenadas para identificar a los vértices. El vértice del extremo superior izquierdo será $(0,0)$, y el vértice del extremo inferior derecho será $(n,m)$. Por la hipótesis inductiva, sabemos que existe algún camino que va desde $(0,x)$ hasta $(n-1,y)$ con $0\leq x,y\leq m$; o $(x,0)$ hasta $(y,m)$ con $0\leq x,y\leq n$.
Si se diera el segundo caso, ya estaríamos, por lo que vamos a analizar qué sucede con el primero.
Tomemos el camino maximizador al que pertenece el vértice $(0,x)$, donde claramente el vértice $(n-1,y)$ también pertenece.
Ahora, sea $(0,t)$ tal que $t$ es lo menor posible ($t$ puede ser $x$) y además, ese vértice pertenece a nuestro camino maximizador (ubicamos al vértice que "más arriba" esté en el tablero y que pertenezca al camino maximizador). Ahora tenemos dos casos: $(1,t-1)$ pertenece al camino maximizador, o no pertenece. Si perteneciera, notemos que $(0,t-1)$ y $(1,t-2)$ es un puente, ya que en caso contrario $(0,t-2)$ pertenecería al camino maximizador, pero sería una contradicción de la minimalidad de $t$. Si no perteneciera, entonces $(1,t+1)$ sí pertenece, por lo que $(0,t-1)$ y $(1,t)$ es un puente, ya que en caso contrario $(0,t-1)$ pertenecería al camino maximizador, pero sería una contradicción.
Ahora, es clave notar que todo camino encubridor está conectado por puentes en nuestra configuración. Supongamos a modo de contradicción que esto no sucede. Situemonos en la casilla donde el camino encubridor no tiene el puente necesario para ser parte del camino encubridor. Entonces, está unido el vértice parte del camino maximizador con el vértice opuesto. Absurdo, ya que contradice la maximalidad de nuestro camino maximizador.
En síntesis, todo puente perteneciente al camino encubridor está, y es el paso fundamental de la solución.
Ahora, sea $(n-1,q)$ tal que $q$ es lo menor posible ($t$ puede ser $y$). Supongamos que no hay una secuencia de puentes que van desde $(0,t-1)$ hasta $(n-1,q-1)$ (notar que ambos vértices son parte del camino encubridor), luego necesariamente se tiene que dar que existe un vértice $(0,l)$, con $0<l<n$ tal que ese vértice pertenece al camino maximizador (ya que sino el camino encubridor debería tener una secuencia de puentes para llegar desde $(0,t-1)$ hasta $(n-1,q-1)$). La magia acá es que podemos recorrer el camino encubridor que está en la parte inferior del tablero. A lo que me refiero con esto es que, como existía un $t$ tal que $(0,t)$ pertenece al camino maximizador y un $q$ tal que $(n-1,q)$ pertenece al camino maximizador, podemos tomar al vértice $(0,t')$ tal que $t'$ es lo mayor posible ($t'$ puede ser $x$) tal que $t'$ pertenece al camino maximizador, y a su vez, tomamos el vértice $(n-1,q')$ tal que $q'$ es lo mayor posible ($q'$ puede ser $y$) tal que $q'$ pertenece al camino maximizador.
Ahora, de forma análoga a como hicimos con $t$ y $q$, sabemos que existe una sucesión de puentes que pertenecen al camino encubridor de nuestro camino maximizador selecto que comienzan en el vértice $(0,t'+1)$ y llegan hasta el vértice $(n-1,q'-1)$. Ahora, si volviera a pasar que no existe esta sucesión de puentes, es porque existe un vértice $(m,l')$ que pertenece al camino maximizador. Pero, si sucediera esto, habría una sucesión de puentes que pertenecen al camino maximizador que van desde $(0,l)$ hasta $(m,l')$. Por lo que, supongamos que no se dan estos casos al mismo tiempo. Luego, es claro que como $(n-1,q-1)$ (o análogamente con $(n-1,q'-1)$) pertenecen al camino encubridor, necesariamente alguno de los vértices $(n,q-2)$ o $(n,q)$ pertenecen al camino encubridor (dependiendo de si $(n,q-1)$ o $(n,q+1)$ son parte o no del camino maximizador).
A fin de cuentas, acabamos de demostrar que, en este caso, el camino encubridor va desde el borde izquierdo al borde derecho. Por lo tanto, no importa cómo sea la configuración de los puentes, Mateo siempre podrá ir alegremente desde uno de los bordes del tablero hacia el opuesto con su fogoso e inigualable autito del Fofopoly.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.

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
Mensajes: 1571
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 10
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: FOFO 9+1 Años - Problema 9

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Notemos que más que los cuadraditos, lo importante acá son los vértices. Con eso en mente, vamos a pintarlos con la coloración de ajedrez, de blanco y negro, lo bueno de esto es que cada diagonal va entre vértices de un mismo color. Para terminar de "cerrar" la figura, agregamos $4$ vértices más, $N,S,E,O$, arriba, abajo, a la derecha y a la izquierda del tablero, respectivamente, y unimos a cada uno con todos los vértices de su lado correspondiente, además, pintamos a $N$ y $S$ de blanco y a $E$ y $O$ de negro. Entonces la condición del enunciado se traduce en demostrar que podemos llegar a $S$ desde $N$ pasando únicamente por vértices blancos o únicamente por vértices negros, o que podemos llegar a $E$ desde $O$ pasando únicamente por vértices negros o únicamente por vértices blancos.
Ahora, le ponemos un $1$ a cada vértice blanco tal que podemos llegar a él desde $N$ pasando únicamente por vértices blancos (en particular, $N$ tiene un $1$), le ponemos un $2$ a cada vértice negro tal que podemos llegar a él desde $O$ pasando únicamente por vértices negros (en particular, $O$ tiene un $2$), y le ponemos un $3$ a los demás vértices. Supongamos que no hay ningún camino que usa únicamente vértices blancos que va de $N$ a $S$, y que no hay ningún camino que usa únicamente vértices blancos que va de $O$ a $E$, entonces $S$ y $E$ tienen un $3$. Notamos además que el vértice de la esquina superior izquierda ($NO$) del tablero no puede tener un $3$ (tiene un $1$ si es blanco y un $2$ si es negro), el vértice de la esquina inferior izquierda ($SO$) no puede tener un $1$ (ya que en ese caso es blanco y hay un camino blanco desde $N$ hasta ese vértice, por lo que hay un camino blanco desde $N$ hasta $S$, lo que contradice nuestra suposición), el vértice de la esquina superior derecha ($NE$) no puede tener un $2$ (ya que en ese caso es negro y hay un camino negro desde $O$ hasta ese vértice, por lo que hay un camino negro desde $O$ hasta $E$, lo que contradice nuestra suposición), y el vértice de la esquina inferior derecha ($SE$) tiene un $3$ (no puede tener un $1$ ni un $2$ por los mismos motivos de antes).
Con todo esto dicho, vamos a demostrar un lema que nos va a dejar el problema prácticamente resuelto. Antes de eso, notemos que el tablero junto con los vértices extras $N,S,O,E$ nos quedó dividido en muchos triangulitos, afirmamos entonces que

Lema:
Existe al menos un triangulito que tiene los vértices con tres números distintos.

Dem:
Spoiler: mostrar
Armamos el grafo donde los nodos son los triangulitos determinados por las diagonales, los bordes de las casillas del tablero, y los nuevos lados que trazamos (los que unen $N$ con el lado superior, $O$ con el lado izquierdo, etc.), y un nodo es la región exterior que determina toda la figura. Además, trazamos una arista entre dos nodos si y sólo si las secciones correspondientes en el dibujo comparten un lado que tiene un vértice con un $1$ y uno con un $2$. Miremos el nodo de la región infinita, por lo que dijimos antes, estará conectado solamente con el triangulito que tiene a $\overline{N,NO}$ como lado o el que tiene a $\overline{NO,O}$ como lado, dependiendo de qué número tenga $NO$, luego, tiene grado impar, pero hay una propiedad muy linda y simple de los grafos que nos dice que la suma de los grados de todos los nodos es el doble de la cantidad de aristas del grafo (pensar por qué), en particular, es un número par, de modo que la cantidad de nodos de grado impar debe ser par, entonces tiene que existir algún otro nodo que tenga grado impar. Ahora, es claro que un nodo que proviene de un triangulito solamente puede tener grado $0,1,2$, de modo que el otro nodo de grado impar tiene que tener grado $1$, de nuevo, es claro que el único caso en el que pasa esto es si su triangulito tiene los tres vértices con números distintos, entonces ya estamos.
Ahora, tomemos un triangulito que tenga sus tres vértices con números distintos, notemos que por definición, el vértice que tiene un $1$ es blanco, y el vértice que tiene un $2$ es negro, entonces si el vértice que tiene un $3$ fuera blanco, debería tener un $1$ (ya que podemos llegar hasta el que tiene un $1$ usando vértices blancos, y extender el camino hasta el que tiene un $3$ en el siguiente paso), y si fuera negro, debería tener un $2$ (por los mismos motivos que antes). Entonces el vértice no puede estar pintado de negro ni de blanco, lo que es absurdo pues todos los vértices están pintados.

El absurdo proviene de suponer que no hay ningún camino blanco de $N$ a $S$ y no hay ningún camino negro de $O$ a $E$, entonces hay al menos uno de los dos, tomando ese camino pero sin sus extremos obtenemos lo pedido.
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850

Responder