EGMO 2022 P3

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

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 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
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

EGMO 2022 P3

Mensaje sin leer por Fran5 »

Se dice que una sucesión infinita de enteros positivos $a_1,a_2,\ldots$ es húngara si
  • $a_1$ es un cuadrado perfecto, y
  • para todo entero $n\geq 2$, $a_n$ es el menor entero positivo tal que$$na_1+(n-1)a_2+\cdots +2a_{n-1}+a_n$$es un cuadrado perfecto.
Pruebe que si $a_1,a_2,\ldots$ es una sucesión húngara, entonces existe un entero positivo $k$ tal que $a_n=a_k$ para todo entero $n\geq k$.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Avatar de Usuario
Fran5

OFO - Medalla de Oro-OFO 2015 OFO - Jurado-OFO 2016 OFO - Jurado-OFO 2017 FOFO Pascua 2017 - Jurado-FOFO Pascua 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
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
OFO - Jurado-OFO 2021 FOFO 11 años - Jurado-FOFO 11 años OFO - Medalla de Bronce-OFO 2022 FOFO Pascua 2022 - Jurado-FOFO Pascua 2022 FOFO 12 años - Jurado-FOFO 12 años
FOFO 13 años - Jurado-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 1125
Registrado: Mié 21 Mar, 2012 1:57 pm
Medallas: 22
Nivel: Exolímpico
Ubicación: Santa Fe

Re: EGMO 2022 P3

Mensaje sin leer por Fran5 »

Spoiler: mostrar
Notación horrible, pero lo importante es darle la vuelta la suma...

Notemos que$$na_1+(n-1)a_2+\cdots +a_n=\sum \limits _{i=1}^n(n+1-i)a_i=\sum \limits _{i=1}^n\sum \limits _{j=i}^na_i=\sum \limits _{j=1}^n\sum \limits _{i=1}^ja_i=\sum \limits _{j=1}^ns_j$$donde $s_j=a_1+a_2+\cdots +a_j=\sum a_i$.

Es decir, $a_n$ es el menor entero positivo que hace que la suma "triangular"$$\sum \sum a_i$$sea un cuadrado perfecto. Escribiendo $B_n=\sum s_j$, tenemos que $s_n=B_n-B_{n-1}$ y $a_n=s_n-s_{n-1}=B_n-2B_{n-1}+B_{n-2}$.

En particular $B_n$ es un cuadrado perfecto, y una suma de números naturales... Sabemos que la suma de los impares es siempre un cuadrado perfecto, donde $B_n=n^2$, $s_n=2n-1$ y $a_n=2$ para $n > 1$. Será que $B_n$ es "algo que depende de $n$ al cuadrado"?

Vamos al grano:
  • Si $B_n=n^2$ sabemos que $s_n=2n-1$ y que $a_n=2$, que es constante
  • Si $B_n=(dn)^2$ para algunos enteros positivos $d$ y $n\geq k$, entonces sacamos factor común $d^2$ y resulta $s_n=B_n-B_{n-1}=d^2(2n-1)$ y $a_n=s_n-s_{n-1}=2d^2$, que es constante.
  • Si $B_n=(a+n)^2$ para algún entero positivo $a$, entonces$$s_n=B_n-B_{n-1}=a^2+2an+n^2-a^2-2an-n^2+2a+2n-1=2a+2n-1$$y nuevamente $a_n=1$. Notar que no usamos que $a$ fuera entero para obtener $a_n=2$, que es constante.
  • En el caso que $B_n=(a+dn)^2$ tenemos $B_n=d^2\left (\frac{a}{d}+n\right )^2=d^2\left (\tilde{a}+n\right )^2$, de donde podemos sacar factor común $d^2$ y usar la última observación para tener $a_n=2d^2$, que es constante.
Luego queremos mostrar que $B_n=(a+dn)^2$ para $n\geq k$ suficientemente grande y algunos enteros positivos $a,d$. En ese caso $a_n=2d^2$ para $n\geq k$.

Recordemos que $B_n$ es el menor cuadrado perfecto mayor a $na_1+(n-1)a_2+\cdots +2a_{n-1}$. Esto es, $B_n=B_{n-1}+s_n=B_{n-1}+s_{n-1}+a_n$, de donde $B_n$ es el menor cuadrado perfecto mayor a$$B_{n-1}+s_{n-1}=B_{n-1}+B_{n-1}-B_{n-2}=2B_{n-1}-B_{n-2}.$$Escribamos $B_n=(b_n)^2$, de donde\begin{align*}2B_{n-1}-B_{n-2} & =2b_{n-1}^2-b_{n-2}^2 \\
& =2(b_{n-2}+b_{n-1}-b_{n-2})^2-b_{n-2}^2 \\
& =b_{n-2}^2+4b_{n-2}(b_{n-1}-b_{n-2})+2(b_{n-1}-b_{n-2})^2 \\
& <b_{n-2}^2+4b_{n-2}(b_{n-1}-b_{n-2})+4(b_{n-1}-b_{n-2})^2 \\
& =(b_{n-2}+2(b_{n-1}-b_{n-2}))^2.
\end{align*}Como $B_n=(b_{n-1}+(b_n-b_{n-1}))^2$ tenemos$$b_{n-1}+(b_n-b_{n-1})\leq b_{n-2}+2(b_{n-1}-b_{n-2})$$equivalentemente$$(b_n-b_{n-1})-(b_{n-1}-b_{n-2})\leq (b_{n-1}-b_{n-2})-(b_{n-1}-b_{n-2}).$$Como estas diferencias son necesariamente positivas (pues $B_n>B_{n-1}$), tenemos que $b_n-b_{n-1}=d$ es constante a partir de algún $n\geq k$. De este modo$$B_n=(b_{n-1}+d)^2$$y por tanto por inducción llegamos a que$$B_n=(a+dn)^2$$para algún $a>0$ y $n\geq k$, que es lo que queríamos ver.
Comentario
Spoiler: mostrar
Algunos ya se habrán dado cuenta. Si $f(n)=B_n$ entonces $s_n=f(n)-f(n-1)\approx f'(n)$ y $a_n=(f(n)-f(n-1))-(f(n-1)-f(n-2))\approx f''(n-1)$. Para que $a_n$ sea constante basta ver que $f_n$ es un polinomio cuadrático en $n$. La igualdad$$B_{n+1}=B_n+s_n+a_{n+1}$$podría pensarse en$$f(n+1)\approx f(n)+f'(n)+f''(n)\approx f(n)+f'(n)+\frac{f''(n)}{2}$$por lo que la intuición dice que las siguientes "derivadas" deberían ser nulas.

La condición $B_n$ es el menor cuadrado mayor a $B_{n-1}+s_n$ se traduce en $f(n)>f(n-1)+\Delta f(n-1)$, donde $\Delta f(n)=s_n$. Luego basta acotar $f(n-1)+\Delta f(n-1)$ por otro cuadrado perfecto. Aquí está el paso mágico y difícil de este problema.

Para ver que $f''(n)$ es constante, vemos que $g'(n)$ es constante, donde $g(n)=b_n=\sqrt{B_n}=\sqrt{f(n)}$.
"Al toque Roque // Al pique Quique // Tranca palanca // No pasa nada // Argentina Gana // La tenés adentro //
Responder