Ibero 2019 - P5

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 1050
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Ibero 2019 - P5

Mensaje sin leer por Gianni De Rico » Lun 16 Sep, 2019 4:01 pm

Don Miguel coloca una ficha en alguno de los $(n+1)^2$ vértices determinados por un tablero de $n\times n$. Una jugada consiste en mover la ficha desde el vértice en que se encuentra a un vértice adyacente en alguna de las ocho posibles direcciones: $\uparrow ,\downarrow ,\rightarrow ,\leftarrow ,\nearrow ,\searrow ,\swarrow ,\nwarrow$ siempre y cuando no se salga del tablero. Un recorrido es una sucesión de jugadas tal que la ficha estuvo en cada uno de los $(n+1)^2$ vértices exactamente una vez. ¿Cuál es la mayor cantidad de jugadas diagonales ($\nearrow ,\searrow ,\swarrow ,\nwarrow$) que en total puede tener un recorrido?
Queda Elegantemente Demostrado

Avatar de Usuario
Brimix

OFO - Medalla de Oro OFO - Medalla de Plata
Mensajes: 87
Registrado: Dom 21 Abr, 2013 10:00 am
Medallas: 3
Nivel: Exolímpico
Ubicación: Rosario♥
Contactar:

Re: Ibero 2019 - P5

Mensaje sin leer por Brimix » Sab 21 Sep, 2019 2:58 pm

El problema más lindo de la prueba :)
Spoiler: mostrar
La solución al problema se reparte en dos casos, $n$ par y $n$ impar.
Primero vamos a comentar un par de cosas que vamos a tener en cuenta en ambos casos...

Prólogo:
Spoiler: mostrar
Un paso es un movimiento de un vértice a un vértice vecino.
Decimos que en cada paso participan los dos vertices entre los que se hace el paso.
Un paso feo es un paso que no es en diagonal.
Un camino recubridor es una secuencia de pasos que pasa por todos los vértices del tablero.
Un extremo de un camino recubridor es cualquiera de los vértices inicial y final del camino. Cada camino recubridor tiene exactamente 2 extremos.

Lo que queremos
En un tablero de $n\times n$ hay exactamente $(n+1)^2$ vertices, si quiero trazar un camino recubridor debo hacer exactamente $n^2+2n$ pasos.
Queremos que la mayor cantidad posible de los pasos sea en diagonal.
Es decir, queremos que la cantidad de pasos feos sea la menor posible.

Datazo para el ejemplo
Si estoy en el borde superior del tablero y no en el extremo derecho, puedo trazar un secuencia de pasos que me lleve al vértice a mi derecha habiendo pasado por todos los vértices en ambas columnas y habiendo hecho un solo paso feo.
Los dibujo de esta forma:
Trenza.png
Para los dos casos del problema vamos a usar las mismas ideas para la cota y para el ejemplo.
Caso $n$ par:
Spoiler: mostrar
Pintamos los vertices como un tablero de ajedrez (blanco y negro) con la esquina superior izquierda negra, de la siguiente forma:
Tablero B-W par.PNG
Repintamos los vértices negros de rojo y azul, de forma que en los bordes izquierdo e inferior del tablero queden solo vertifces rojos y en cada diagonal $\nearrow$ (hacia la derecha hacia arriba) los colores se alternen:
Tablero RGB par.PNG
Llamamos $R$ a la cantidad de vértices rojos y $A$ a la cantidad de vértices azules.
Observamos que en cada diagonal $\nearrow$ de "vértices negros" la cantidad de vértices rojos es uno más que los azules (ya que estas diagonales tienen tamaño impar) y que hay exactamente $n+1$ diagonales, por lo que:
$R - A = n+1$

Pensemos ahora en un camino recubridor y analicemos:
No pueden haber dos vértices rojos consecutivos. Por lo tanto la cantidad de pasos en los que participa exactamente un vértice rojo es al menos $2R-2$
Esta cuenta sale de ver que hay 2 vecinos por cada vértice rojo. Excepto por los casos en que los extremos del camino sean rojos, en esos casos el vértice rojo tiene un solo vecino, la cantidad de extremos es a lo sumo 2.

La cantidad de pasos en los que participa un vértice azul es a lo sumo $2A$

Vemos que de los al menos $2R-2$ pasos de los que participa exactamente un vértice rojo, en a lo sumo $2A$ participa también un azul.
Por eso la cantidad de pasos entre un vértice rojo y uno blanco es al menos $2R-2-2A = 2n$

También destacamos que los pasos entre un vértice rojo y uno blanco son siempre feos.
Por lo tanto hay al menos $2n$ pasos feos.

Con el método que contamos en el prólogo, construimos ejemplos de caminos en tableros con $n$ par:
Ejemplos Par.png
Podemos hacer lo mismo para cualquier $n$ par.
Podemos calcular que la cantidad de pasos feos en cada uno de esos ejemplos es, respectivamente, $2n$.

En este caso hemos demostrado que la menor cantidad posible de pasos feos que haremos será $2n$
La cantidad máxima total de "pasos diagonales" (o lindos) en estos casos es $n^2$
Caso $n$ impar:
Spoiler: mostrar
Pintamos nuevamente de blanco y negro:
Tablero B-W impar.PNG
El primer detalle especial en este caso es que ahora las casillas negras son simétricas axialmente respecto de las blancas y por lo tanto, podemos elegir indistintamente cualquiera de los 2 grupos iniciales (el negro o el blanco) y voltear el tablero.

Para cualquier camino recubridor lo que haremos será elegir el grupo que tenga la menor cantidad de extremos de ese camino y lo repintamos igual que en el caso anterior. Este grupo tendra a lo sumo 1 extremo.
Sin perdida de generalidad repintamos el grupo negro. Nos queda algo así:
Tablero RGB impar.PNG
En este caso se conserva que por cada diagonal $\nearrow$ la cantidad de rojos es una más que de azules y que hay $n+1$ diagonales, por lo tanto otra vez tenemos: $R - A = n+1$

El segundo detalle especial en este caso es que sí puede haber un paso entre dos vértices rojos.
En las dos diagonales centrales hay $\frac{n+1}{2}$ parejas de vértices rojos que pueden ser vecinos en el camino.

Analicemos:
La cantidad de participaciones de un vértice rojo en un paso es al menos $2R - 1$, por lo mismo que el caso anterior, solo que ahora tenemos a lo sumo 1 extremo.
La cantidad de pasos en los que hay 2 rojos es a lo sumo $\frac{n+1}{2}$
Descontamos 2 participaciones por cada uno y nos queda la cantidad de pasos en los que participa exactamente un vértice rojo, son al menos $2R - 1 - 2\frac{n+1}{2} = 2R - n - 2$.

Y la cantidad de pasos en los que participa exactamente un vértice azul sigue siendo a lo sumo $2A$.

Ahora, la cantidad de pasos "feos" entre un vértice rojo y uno blanco son al menos:
$2R-n-2-2A = 2(R-A) - n - 2 = n$

Construimos el ejemplo de la misma forma que en el caso anterior:
Ejemplos Impar.png
Pero en este caso, genialmente, la cantidad de feos en cada caso me da $n$.
En este caso hemos demostrado que la menor cantidad posible de pasos feos que haremos será $n$
La cantidad máxima total de "pasos diagonales" (o lindos) en estos casos es $n^2+n$
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
2  
♪♫Nuestro ARG2 es nuestro ejemplo. 'Efe de equis mas one!'♫♪

Responder