Regional 2022 N3 P1

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

Re: Regional 2022 N3 P1

Mensaje sin leer por Gianni De Rico »

Empecé a escribir esto tratando de completar la demo de la primera observación que había hecho y de demostrar el dato gracioso que mágicamente había visto Brian, de alguna manera terminé con una solución que se siente como una mezcla de las de Fede y el Turko, pero vamos allá.
Spoiler: mostrar
Vamos a construir las sucesiones impar-par con términos menores o iguales a $n$ a partir de las sucesiones impar-par con términos menores o iguales a $n-1$. Sean $T(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$, $I(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$ de longitud impar y $P(n)$ la cantidad de sucesiones impar-par con términos menores o iguales a $n$ de longitud par. Entonces tenemos que $T(n)=I(n)+P(n)$.

Notemos que $I(2n+1)=I(2n)+P(2n)+1$, pues tenemos todas las sucesiones de longitud impar para $2n$, todas las sucesiones de longitud par para $2n$ a las que les agregamos al final el término $2n+1$ y una sucesión "extra" que es la que está formada únicamente por $2n+1$ (y todas las sucesiones se construyen de esta manera). Notemos también que $I(2n+2)=I(2n+1)$, porque las sucesiones de longitud impar tienen que terminar con un impar, así que podemos formar exactamente las mismas sucesiones teniendo a $2n+2$ como el mayor término que puede aparecer en una sucesión que teniendo a $2n+1$ como el mayor término que puede aparecer en una sucesión (y todas las sucesiones se construyen de esta manera).
Notemos que $P(2n+1)=P(2n)$ por el mismo argumento de recién. Notemos también que $P(2n+2)=I(2n)+P(2n)$, pues tenemos a todas las sucesiones de longitud impar para $2n$ a las que les agregamos al final el término $2n+2$ y todas las sucesiones de longitud par para $2n$ (y todas las sucesiones se construyen de esta manera).

De acá podemos demostrar por inducción que $I(2n)=F_{2n}$ y que $P(2n)=F_{2n+1}-1$, resultando así\begin{align*}T(2n) & =I(2n)+P(2n) \\
& =F_{2n}+F_{2n+1}-1 \\
& =F_{2n+2}-1
\end{align*}y\begin{align*}T(2n+1) & =I(2n+1)+P(2n+1) \\
& =I(2n+2)+P(2n) \\
& =F_{2n+2}+F_{2n+1}-1 \\
& =F_{2n+3}-1,
\end{align*}de modo que en general $T(n)=F_{n+2}-1$ para todo $n\in \mathbb{N}$, donde $F_n$ es el $n$-ésimo número de Fibonacci (la primera observación había sido que $T(n+2)=T(n)+T(n+1)+1$, que se puede demostrar directamente teniendo la formulita general de $T$). En particular tenemos que $T(10)=F_{12}-1=143$.
1  
Esto es trivial por el teorema de Bolshonikov demostrado en un bar de Bielorrusia en 1850
Responder