Ibero 2019 - P5

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 COFFEE - Jurado-COFFEE Matías Saucedo OFO - Jurado-OFO 2020 FOFO Pascua 2020 - Jurado-FOFO Pascua 2020
COFFEE - Jurado-COFFEE Carolina González
Mensajes: 1257
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 6
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 2015 OFO - Medalla de Oro-OFO 2016 OFO - Medalla de Plata-OFO 2019 OFO - Medalla de Oro-OFO 2020
Mensajes: 90
Registrado: Dom 21 Abr, 2013 10:00 am
Medallas: 4
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!'♫♪

HelcsnewsXD

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Carolina González
Mensajes: 45
Registrado: Jue 13 Sep, 2018 8:59 am
Medallas: 2
Nivel: 3

Re: Ibero 2019 - P5

Mensaje sin leer por HelcsnewsXD » Mié 20 May, 2020 3:17 am

Spoiler: mostrar

Unas consideraciones importantes...
Spoiler: mostrar
Sobre funciones...
Spoiler: mostrar
Definimos $ψ(n): \mathbb{N} \rightarrow \mathbb{N}$, con $n \in \mathbb{N}$ como la función que, dado $n$ como el lado de un tablero cuadrado ($\Rightarrow$ el tablero es $n\times n$), retorna la cantidad máxima de diagonales que un recorrido puede tener.
Sobre nomenclaturas...
Spoiler: mostrar
1) Llamaremos vértices mayores a aquellos que sean los vértices del tablero de $n\times n$. Es decir, a uno de los cuatros vértices que se encuentran en los extremos del tablero.

2) Llamaremos diagonal saliente o entrante a un vértice, a la diagonal que pasa por él.

2) Llamaremos diagonal encerrante a un vértice, a la diagonal que pasa por sus consecutivos / vecinos de modo que este vértice del que se habla no tenga una saliente / entrante.
Lemas que van a usarse
Spoiler: mostrar
1) Dado un vértice, este puede tener, como máximo, dos diagonales
Spoiler: mostrar
Como un recorrido debe pasar exactamente una vez por cada vértice, en cada uno de estos se encuentra un segmento (horizontal, vertical o diagonal) de entrada y otro de salida a este. Esto implica que solo hayan dos segmentos considerados. Como consecuencia, se demuestra el lema.
2) Dada una diagonal encerrante a un vértice, si este vértice es mayor, debe ser el inicio o fin del recorrido
Spoiler: mostrar
Consideremos los dos vértices donde esta diagonal encerrante es entrante / saliente. Aquí, por el lema 1, estos vértices tienen, además de la diagonal, un segmento (horizontal, vertical o diagonal) cada uno para seguir el recorrido. Por definición de recorrido, uno de estos debe conectar con el vértice mayor, pero no los dos a la vez (por lema 1). Por ende, es principio o fin, y se demuestra.
Caso base $n=2$
Spoiler: mostrar
La conjetura es que $ψ(2)=4$.

Demostración de que $ψ(2)\leq 4$
Spoiler: mostrar
Veremos qué sucede si consideramos 5 diagonales en un recorrido. Por el lema 1, tenemos dos tipos de esquemas (cada uno con una casilla con dos diagonales). Estos son:

1) Diagonal entrante al vértice medio en casilla consecutiva a la que contiene dos diagonales
Spoiler: mostrar
Esto implica que, por lema 2, el inicio y fin del recorrido se encuentran en dos casillas consecutivas. Por ende, por lema 1, al haber un vértice con dos diagonales, el recorrido a hacer ya está definido. Por esto, no puede darse esta situación ya que, o nos falta un vértice en el recorrido o nos faltan las dos casillas con diagonales entrantes / salientes al vértice medio.
1) Diagonal entrante al vértice medio en casilla opuesta a la que contiene dos diagonales
Spoiler: mostrar
Aquí, por el lema 2, el inicio y fin del recorrido están en casillas opuestas, y las diagonales encerrantes están unidas por una de las diagonales de la casilla con dos diagonales. Por esto, al igual que en el anterior caso, por lema 1, como tenemos dos vértices con dos diagonales, el recorrido a hacer ya está definido. Por ende, siempre nos faltaría al menos un vértice. Esto implica que esta caso tampoco sea posible
Demostración de que $ψ(2)=4$
Spoiler: mostrar
La forma de demostrarlo es haciendo un diagrama donde esto se cumpla. Uno de estos, el cual consideraremos y llamaremos como Diagrama ψ(2), es poniendo dos diagonales en cada una de dos casillas consecutivas. De este modo, comenzamos con las diagonales completando toda la fila / columna y continuamos con los vértices sin diagonales.
Caso par
Spoiler: mostrar
Al ya tener el valor de $ψ(2)$, podemos dividir todo el tablero en casilleros de $2\times 2$. Por ello, decimos que $ψ(n)=ψ(2)\times \frac{n^2}{4} \Rightarrow ψ(n)=n^2$.
Esto puede diagramarse sencillamente de modo que para todo tablero de $2\times 2$, este cumpla el Diagrama ψ(2).
Caso impar
Spoiler: mostrar
Dividamos el tablero en diferentes sub-tableros: Uno de $(n-3)\times (n-3)$, otro opuesto a él de $3\times 3$ y el resto del espacio ocupado por tableros rectangulares de $2\times 3$. Es un diagrama como el que se muestra en la siguiente figura:
WhatsApp Image 2020-05-20 at 02.47.24.jpeg
Sub-tablero $2\times 3$
Spoiler: mostrar
Dado un tablero rectangular de $2\times 3$, aplicando $ψ(2)$ dos veces, observamos que $ψ(2, 3)=8$ y que el único diagrama factible es teniendo las casillas con dos diagonales de a pares consecutivos y opuestos estos pares (Diagrama ψ(2, 3)).
Sub-tablero $3\times 3$
Spoiler: mostrar
Dado un tablero rectangular de $2\times 3$, aplicando $ψ(2, 3)$ dos veces, observamos que $ψ(3)=12$ y que el único diagrama factible es teniendo un diagrama semejante al Diagrama ψ(2, 3) (Diagrama ψ(3))
Sub-tablero par
Spoiler: mostrar
Dado un tablero con $n$ par y mayor que $4$, aplicando $ψ(2, 3)$ y $ψ(2)$ todas las veces posibles y en la misma dirección, tenemos que el diagrama que presente este tablero es único y semejante a Diagrama ψ(2, 3) (Diagrama par)
Desarrollo
Spoiler: mostrar
Tomando en cuenta todos los $ψ$, es decir, los máximos, vemos que, como estos tienen una disposición única y semejante entre ellos (todas casillas consecutivas con dos diagonales de fila / columna de por medio), todos los sub-tableros $2\times 3$ en una misma dirección / de un mismo lado, entran en conflicto con el $(n-3)\times (n-3)$. Esto puede arreglarse sacando dos diagonales de cada $2\times 3$ que entra en conflicto, sacándose en total $n-3$. Si lo queremos plantear desde la perspectiva de sacar a otro sub-tablero las diagonales para obtener el máximo, vemos que si lo hacemos con los otros $2\times 3$ es prácticamente lo mismo y con $3\times 3$ resulta inútil. Por esto, veremos qué pasa en $(n-3)\times (n-3)$.
Aquí, como tiene un diagrama único (Diagrama par) si o sí debemos sacar una casilla (con sus dos diagonales) por cada $2\times 3$ con el que entra en conflicto, sacándose la misma cantidad en total. Esto sucede ya que si en alguna ocasión se sacara solo una diagonal, aplicando $ψ(2)$, vemos que es imposible hacer un recorrido. Por esta razón, solo queda sacar diagonales de los dos tipos de tableros, pero se termina llegando a la misma situación.
Es por ello que ahora hacemos los siguientes cálculos para obtener el máximo:
$ψ(n)=ψ(n-3)+ψ(2, 3)\times 2\times \frac{n-3}{2}+ψ(3)-(n-3)$
$ψ(n)=(n-3)^2+8\times (n-3)+12-n+3$
$ψ(n)=n^2-6n+9+8n-24+12-n+3$
$ψ(n)=n^2+n$
Por esta razón, obtenemos que la mayor cantidad de diagonales que un recorrido puede tener es de $n^2$ para tableros con cantidad de casillas pares y $n^2+n$ para los impares.
No tienes los permisos requeridos para ver los archivos adjuntos a este mensaje.
Genial :D 8-)

Avatar de Usuario
Joacoini

OFO - Medalla de Plata-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años OFO - Medalla de Oro-OFO 2019 FOFO Pascua 2019 - Medalla-FOFO Pascua 2019 FOFO 9 años - Medalla Especial-FOFO 9 años
OFO - Medalla de Oro-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020
Mensajes: 350
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 7
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: Ibero 2019 - P5

Mensaje sin leer por Joacoini » Mié 20 May, 2020 3:51 am

HelcsnewsXD escribió:
Mié 20 May, 2020 3:17 am
Spoiler: mostrar

Unas consideraciones importantes...
Spoiler: mostrar
Sobre funciones...
Spoiler: mostrar
Definimos $ψ(n): \mathbb{N} \rightarrow \mathbb{N}$, con $n \in \mathbb{N}$ como la función que, dado $n$ como el lado de un tablero cuadrado ($\Rightarrow$ el tablero es $n\times n$), retorna la cantidad máxima de diagonales que un recorrido puede tener.
Sobre nomenclaturas...
Spoiler: mostrar
1) Llamaremos vértices mayores a aquellos que sean los vértices del tablero de $n\times n$. Es decir, a uno de los cuatros vértices que se encuentran en los extremos del tablero.

2) Llamaremos diagonal saliente o entrante a un vértice, a la diagonal que pasa por él.

2) Llamaremos diagonal encerrante a un vértice, a la diagonal que pasa por sus consecutivos / vecinos de modo que este vértice del que se habla no tenga una saliente / entrante.
Lemas que van a usarse
Spoiler: mostrar
1) Dado un vértice, este puede tener, como máximo, dos diagonales
Spoiler: mostrar
Como un recorrido debe pasar exactamente una vez por cada vértice, en cada uno de estos se encuentra un segmento (horizontal, vertical o diagonal) de entrada y otro de salida a este. Esto implica que solo hayan dos segmentos considerados. Como consecuencia, se demuestra el lema.
2) Dada una diagonal encerrante a un vértice, si este vértice es mayor, debe ser el inicio o fin del recorrido
Spoiler: mostrar
Consideremos los dos vértices donde esta diagonal encerrante es entrante / saliente. Aquí, por el lema 1, estos vértices tienen, además de la diagonal, un segmento (horizontal, vertical o diagonal) cada uno para seguir el recorrido. Por definición de recorrido, uno de estos debe conectar con el vértice mayor, pero no los dos a la vez (por lema 1). Por ende, es principio o fin, y se demuestra.
Caso base $n=2$
Spoiler: mostrar
La conjetura es que $ψ(2)=4$.

Demostración de que $ψ(2)\leq 4$
Spoiler: mostrar
Veremos qué sucede si consideramos 5 diagonales en un recorrido. Por el lema 1, tenemos dos tipos de esquemas (cada uno con una casilla con dos diagonales). Estos son:

1) Diagonal entrante al vértice medio en casilla consecutiva a la que contiene dos diagonales
Spoiler: mostrar
Esto implica que, por lema 2, el inicio y fin del recorrido se encuentran en dos casillas consecutivas. Por ende, por lema 1, al haber un vértice con dos diagonales, el recorrido a hacer ya está definido. Por esto, no puede darse esta situación ya que, o nos falta un vértice en el recorrido o nos faltan las dos casillas con diagonales entrantes / salientes al vértice medio.
1) Diagonal entrante al vértice medio en casilla opuesta a la que contiene dos diagonales
Spoiler: mostrar
Aquí, por el lema 2, el inicio y fin del recorrido están en casillas opuestas, y las diagonales encerrantes están unidas por una de las diagonales de la casilla con dos diagonales. Por esto, al igual que en el anterior caso, por lema 1, como tenemos dos vértices con dos diagonales, el recorrido a hacer ya está definido. Por ende, siempre nos faltaría al menos un vértice. Esto implica que esta caso tampoco sea posible
Demostración de que $ψ(2)=4$
Spoiler: mostrar
La forma de demostrarlo es haciendo un diagrama donde esto se cumpla. Uno de estos, el cual consideraremos y llamaremos como Diagrama ψ(2), es poniendo dos diagonales en cada una de dos casillas consecutivas. De este modo, comenzamos con las diagonales completando toda la fila / columna y continuamos con los vértices sin diagonales.
Caso par
Spoiler: mostrar
Al ya tener el valor de $ψ(2)$, podemos dividir todo el tablero en casilleros de $2\times 2$. Por ello, decimos que $ψ(n)=ψ(2)\times \frac{n^2}{4} \Rightarrow ψ(n)=n^2$.
Esto puede diagramarse sencillamente de modo que para todo tablero de $2\times 2$, este cumpla el Diagrama ψ(2).
Caso impar
Spoiler: mostrar
Dividamos el tablero en diferentes sub-tableros: Uno de $(n-3)\times (n-3)$, otro opuesto a él de $3\times 3$ y el resto del espacio ocupado por tableros rectangulares de $2\times 3$. Es un diagrama como el que se muestra en la siguiente figura:
WhatsApp Image 2020-05-20 at 02.47.24.jpeg

Sub-tablero $2\times 3$
Spoiler: mostrar
Dado un tablero rectangular de $2\times 3$, aplicando $ψ(2)$ dos veces, observamos que $ψ(2, 3)=8$ y que el único diagrama factible es teniendo las casillas con dos diagonales de a pares consecutivos y opuestos estos pares (Diagrama ψ(2, 3)).
Sub-tablero $3\times 3$
Spoiler: mostrar
Dado un tablero rectangular de $2\times 3$, aplicando $ψ(2, 3)$ dos veces, observamos que $ψ(3)=12$ y que el único diagrama factible es teniendo un diagrama semejante al Diagrama ψ(2, 3) (Diagrama ψ(3))
Sub-tablero par
Spoiler: mostrar
Dado un tablero con $n$ par y mayor que $4$, aplicando $ψ(2, 3)$ y $ψ(2)$ todas las veces posibles y en la misma dirección, tenemos que el diagrama que presente este tablero es único y semejante a Diagrama ψ(2, 3) (Diagrama par)
Desarrollo
Spoiler: mostrar
Tomando en cuenta todos los $ψ$, es decir, los máximos, vemos que, como estos tienen una disposición única y semejante entre ellos (todas casillas consecutivas con dos diagonales de fila / columna de por medio), todos los sub-tableros $2\times 3$ en una misma dirección / de un mismo lado, entran en conflicto con el $(n-3)\times (n-3)$. Esto puede arreglarse sacando dos diagonales de cada $2\times 3$ que entra en conflicto, sacándose en total $n-3$. Si lo queremos plantear desde la perspectiva de sacar a otro sub-tablero las diagonales para obtener el máximo, vemos que si lo hacemos con los otros $2\times 3$ es prácticamente lo mismo y con $3\times 3$ resulta inútil. Por esto, veremos qué pasa en $(n-3)\times (n-3)$.
Aquí, como tiene un diagrama único (Diagrama par) si o sí debemos sacar una casilla (con sus dos diagonales) por cada $2\times 3$ con el que entra en conflicto, sacándose la misma cantidad en total. Esto sucede ya que si en alguna ocasión se sacara solo una diagonal, aplicando $ψ(2)$, vemos que es imposible hacer un recorrido. Por esta razón, solo queda sacar diagonales de los dos tipos de tableros, pero se termina llegando a la misma situación.
Es por ello que ahora hacemos los siguientes cálculos para obtener el máximo:
$ψ(n)=ψ(n-3)+ψ(2, 3)\times 2\times \frac{n-3}{2}+ψ(3)-(n-3)$
$ψ(n)=(n-3)^2+8\times (n-3)+12-n+3$
$ψ(n)=n^2-6n+9+8n-24+12-n+3$
$ψ(n)=n^2+n$
Por esta razón, obtenemos que la mayor cantidad de diagonales que un recorrido puede tener es de $n^2$ para tableros con cantidad de casillas pares y $n^2+n$ para los impares.
Tu demostración está mal.
Dividir un tablero en varios subtableros no quiere decir que la máxima cantidad de diagonales que puede tener el tablero es la suma de los subtableros, imaginate que haya un recorrido que tenga más diagonales y que en uno de tus subtableros no se cumpla que el recorrido pase por todos los vértices uno seguido del otro (o sea el recorrido entra al subtableros, sale de este y más tarde vuelve a entrar).
Por ejemplo si un problema te pide cuántos tromino L entran en un tablero, vos podés ver qué en un 2×2 entra uno solo pero en un 4×4 a pesar de dividirlo en cuatro 2×2 entran 5 trominos en vez de solo 4.
NO HAY ANÁLISIS.

Responder