IBERI 2018 - P5

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

OFO - Mención-OFO 2017 FOFO 7 años - Medalla Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Mención Especial-FOFO 8 años OFO - Medalla de Plata-OFO 2019
Mensajes: 405
Registrado: Sab 04 Jun, 2016 11:50 pm
Medallas: 5
Ubicación: Puerto Rico

IBERI 2018 - P5

Mensaje sin leer por Violeta »

Decimos que una permutación $a_1,a_2,\ldots ,a_n$ es guadiana si la sucesión $b_1,b_2,\ldots ,b_n$ definida por$$b_i=\min _{1\leq k\leq i}a_k+\max _{1\leq k\leq i}a_k$$no tiene dos términos consecutivos iguales.

Hallar la cantidad de permutaciones guadianas de $n$ términos.
Para todo [math], existen [math] primos en sucesión aritmética.
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: 2210
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IBERI 2018 - P5

Mensaje sin leer por Gianni De Rico »

Falta aclarar que los $a_i$ son una permutación de $1,2,\ldots ,n$. Donde $n$ es un entero positivo.
1  
♪♫ do re mi función lineal ♪♫
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: 2210
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: IBERI 2018 - P5

Mensaje sin leer por Gianni De Rico »

Spoiler: mostrar
Si $\min \limits_{1\le k\le i}a_k<a_{i+1}<\max \limits _{1\le k\le i}a_k$ entonces $b_i=b_{i+1}$ y la sucesión no es guadiana, luego, si la sucesión es guadiana entonces $a_{i+1}<\min \limits _{1\le k\le i}a_k$ o $\max \limits _{1\le k\le i}<a_{i+1}$ (*). Además toda sucesión que cumpla eso será guadiana, es decir, si tanto $1$ como $n$ aparecen en $\{a_j\}_{j<n}$, la sucesión no será guadiana.

Veamos que tenemos al menos $2^{n-1}$ sucesiones guadianas. Lo haremos por inducción en $n$. El caso base $n=1$ es cierto pues el único elemento es $b_1=2$. Supongamos como hipótesis inductiva que es cierto para $n=k$. Veamos que es cierto para $k+1$. En efecto, para cada sucesión guadiana de $k$ términos nos construimos dos sucesiones guadianas nuevas, si la sucesión $a_1,a_2,\ldots ,a_k$ es guadiana, entonces las sucesiones $a_1,a_2,\ldots ,a_k,k+1$ y $a_1+1,a_2+1,\ldots ,a_k+1,1$ son guadianas, pues ambas cumplen con (*), tienen todos sus términos distintos y entre $1$ y $k+1$, por lo tanto, la cantidad de sucesiones guadianas de $k+1$ términos es al menos $2\cdot 2^{k-1}=2^{(k+1)-1}$. La inducción está completa.

Veamos que no podemos tener más de $2^{n-1}$ sucesiones guadianas. Lo haremos por inducción en $n$. El caso base $n=1$ es cierto pues la única sucesión es $b_1=2$. Supongamos como hipótesis inductiva que es cierto para $n=k$. Veamos que es cierto para $k+1$. En efecto, por (*) tenemos que el último término de una sucesión guadiana solamente puede ser $a_{k+1}=1$ o $a_{k+1}=k+1$, notemos además que toda subsucesión de los $b_i$ de una sucesión guadiana no tiene dos términos consecutivos iguales. Si $a_{k+1}=1$, entonces $a_1,a_2,\ldots ,a_k$ es una permutación de $2,3,\ldots ,k+1$, de donde $a_1-1,a_2-1,\ldots ,a_k-1$ es una permutación de $1,2,\ldots ,k$, por lo que la sucesión de los $a_i-1$ es guadiana, y por hipótesis inductiva hay a lo sumo $2^{k-1}$ sucesiones guadianas de $k$ términos, entonces hay a lo sumo $2^{k-1}$ sucesiones guadianas de la forma $a_1,a_2,\ldots ,a_k,1$. Si $a_{k+1}=k+1$, entonces $a_1,a_2,\ldots ,a_k$ es una permutación de $1,2,\ldots ,k$, por lo que es guadiana, y por hipótesis inductiva hay a lo sumo $2^{k-1}$ sucesiones guadianas de $k$ términos, entonces hay a los sumo $2^{k-1}$ sucesiones guadianas de la forma $a_1,a_2,\ldots ,a_k,k+1$.
En total, la cantidad de sucesiones guadianas de $k+1$ términos es a lo sumo $2^{k-1}+2^{k-1}=2\cdot 2^{k-1}=2^{(k+1)-1}$. La inducción está completa.

Por lo tanto, si $G$ es la cantidad de sucesiones guadianas, tenemos $2^{n-1}\le G\le 2^{n-1}$. Queda demostrado que $G=2^{n-1}$.
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
Fran2001

FOFO 7 años - Mención Especial-FOFO 7 años OFO - Medalla de Bronce-OFO 2018 FOFO 8 años - Medalla Especial-FOFO 8 años FOFO 9 años - Medalla Especial-FOFO 9 años
Mensajes: 67
Registrado: Mié 29 Mar, 2017 11:09 am
Medallas: 4
Nivel: Exolímpico
Ubicación: Rosario

Re: IBERO 2018 - P5

Mensaje sin leer por Fran2001 »

Distinta a todas las que vi:
Spoiler: mostrar
Notemos que si en algún paso no cambiamos el máximo o el mínimo de la sucesión $a$ entonces la sucesión $b$ tendrá $2$ términos consecutivos iguales, y que el hecho de cambiar alguno en todos los pasos es suficiente para asegurar que $a$ es guadiana.
Por lo tanto queremos que en cada paso cambie el máximo o el mínimo de la sucesión.
Vamos a denotar con $\max(i)$ al máximo $a_j$ con $1\leq j\leq i$, es decir, $\displaystyle\max(i)=\max _{1\leq j\leq i}a_j$.
Análogamente, $\displaystyle\min(i)=\min _{1\leq j\leq i}a_j$.

Lema: Supongamos que en algún paso "subimos el máximo (o bajamos el mínimo) más de $1$", es decir, existe un $i$ tal que $\max(i+1)-\max(i)\geq 2$. Entonces la sucesión no es guadiana.

Demostración:
Spoiler: mostrar
Vamos a ver qué ocurre para el máximo, el caso del mínimo es análogo.
Sea $j$ el primer índice en el que esto ocurre.
Notemos entonces que existe un entero $m$ que todavía no está en la sucesión $a$ tal que $\max(j)<m<\max(j+1)$.
Por lo tanto vamos a tener algún índice $l>j$ tal que $a_l=m$.
Ahora, como $\max(j)<a_l$, en el turno $l$ no cambiamos el mínimo de la sucesión.
Y como $a_l<\max(j+1)$, en el turno $l$ tampoco cambiamos el máximo de la sucesión.
Por lo tanto la sucesión no es guadiana.
Es decir que en una sucesión guadiana tenemos que $\max(i+1)-\max(i)\leq 1$ para todo $i$.
Análogamente, $\min(i)-\min(i+1)\leq 1$ para todo $i$.
Por lo tanto tenemos que $a_{i+1}=\max(i)+1$ o $a_{i+1}=\min(i)-1$ para todo $i$.
Notemos además que esto asegura que la sucesión sea guadiana.
Es decir que en cada paso podemos únicamente subir (poner $\max(i)+1$) o bajar (poner $\min(i)-1$), y esto podemos hacerlo en cualquier orden. Por lo tanto, dado un $a_1$, todas nuestras sucesiones posibles son las que suben $n-a_1$ veces y bajan $a_1-1$ veces.
Estas son en total $\binom{n-a_1+a_1-1}{a_1-1}=\binom{n-1}{a_1-1}$.
Como $a_1$ varía entre $1$ y $n$, tenemos que $a_1-1$ varía entre $0$ y $n-1$, y por lo tanto la cantidad de sucesiones guadianas es $$\binom{n-1}{0}+\binom{n-1}{1}+\dots +\binom{n-1}{n-1}=2^{n-1}.$$
Ya le rimo la respuesta // que de la duda nos saca // el animal que usted dice // tiene por nombre la vaca
https://www.youtube.com/watch?v=7ydlVCj94x4
Responder