OFO 2020 Problema 8

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

OFO 2020 Problema 8

Mensaje sin leer por Gianni De Rico »

Sea $a_1 < a_2 < a_3 < \ldots$ una sucesión infinita de números enteros positivos, estrictamente creciente, que cumple la siguiente propiedad: para todo $n \geq 10$, $a_n$ divide a la suma de todos los términos anteriores. Demostrar que existe $m \in \mathbb N$ tal que para todo $n \geq m$ se cumple que $a_n$ es igual a la suma de todos los términos anteriores.
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: 2212
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 18
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

Re: OFO 2020 Problema 8

Mensaje sin leer por Gianni De Rico »

Solución Oficial:
Spoiler: mostrar
Para cada $n\in \mathbb{N}$, definimos $$s_n=a_1+a_2+\cdots +a_{n-1}$$ Consideremos $n\geqslant 10$, entonces tenemos que $a_n\mid s_n$, y como ambos son positivos, existe un entero positivo $d_n$ tal que $a_nd_n=s_n$, es decir, $a_n=\frac{s_n}{d_n}$. Vamos a ver que eventualmente $d_n=1$.

Veamos primero que la sucesión de los $d_i$ es no creciente (esto es, $d_{n+1}\leqslant d_n$). Notemos que $$s_{n+1}=a_1+a_2+\cdots +a_{n-1}+a_n=s_n+a_n=s_n+\frac{s_n}{d_n}=\frac{d_n+1}{d_n}s_n$$ entonces $$a_{n+1}=\frac{s_{n+1}}{d_{n+1}}=\frac{d_n+1}{d_{n+1}}\frac{s_n}{d_n}=\frac{d_n+1}{d_{n+1}}a_n$$ por lo que $d_{n+1}=(d_n+1)\frac{a_n}{a_{n+1}}$, pero como $a_n<a_{n+1}$, tenemos que $d_{n+1}<d_n+1$, y al ser enteros se sigue que $d_{n+1}\leqslant d_n$.

Veamos ahora que la sucesión de los $d_i$ en algún punto llega a $1$.
Como es una sucesión de enteros positivos, no puede decrecer infinitamente, por lo que en algún momento se vuelve constante, es decir, existe $m\in \mathbb{N}$ tal que $d_n=t$ para $n\geqslant m$. Tenemos entonces que $s_{n+1}=\frac{t+1}{t}s_n$, por lo que $$s_{n+k}=\left (\frac{t+1}{t}\right )^ks_n=\frac{(t+1)^ks_n}{t^k}$$ para todo $k\in \mathbb{N}$. Luego, $t^k\mid (t+1)^ks_n$, pero $t$ y $t+1$ son coprimos, por lo que $t^k$ y $(t+1)^k$ son coprimos, entonces $t^k\mid s_n$. Pero como $s_n>0$ pues los $a_i$ son positivos, tenemos que $t=1$, es decir, $d_n=1$. Luego, $a_n=\frac{s_n}{d_n}=s_n$
De esta forma, tenemos que existe $m\in \mathbb{N}$ tal que $a_n=s_n=a_1+a_2+\cdots +a_{n-1}$ para $n\geqslant m$, y con eso estamos.
2  
♪♫ do re mi función lineal ♪♫
Avatar de Usuario
NPCPepe

FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020 COFFEE - Mención-COFFEE Carolina González
COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años
Mensajes: 81
Registrado: Lun 17 Jun, 2019 9:22 pm
Medallas: 8
Nivel: 3
Ubicación: Argentina

Re: OFO 2020 Problema 8

Mensaje sin leer por NPCPepe »

Spoiler: mostrar
Si la serie es $a_0$ $a_1$ $a_2$ ....
$a_{10}=(a_0+a_1+...+a_9)/n_0$
$a_{11}=(a_0+a_1+...+a_9+a_{10})/n_1$
y asi sucesivamente

Lema 1: Si $a_n<=a_{n+1}$, la serie no cumple las condiciones ya que un numero de la serie sería mayor o igual a su siguiente.

Dicho esto para comprobar que la serie tiene que terminar con una serie tal que el numero siguiente es igual a la suma de los anteriores hay que demostrar que el unico $n$ que se puede usar infinitas veces es el $1$ ya que si se usaría otro $n$ y la division en algun momento dejaría de ser entera habría que continuar con un $n$ menor debido al lema y eventualmente se llegaría al 1.

Para demostrar esto se denomina $S$ a la suma de los terminos anteriores a $a_k$, entonces $a_k=S/n$,
$a_{k+1}=(S/n+S)/n=S/n+S/n^2$, $a_{k+2}=S/n+2S/n^2+S/n^3$.
En resumen S tiene que ser divisible por una potencia cada vez mas grande de $n$ lo cual es imposible excepto si $n$ es 1.

Demostración del Lema 1.
Teniendo la misma definición de $S$ que en la demostración anterior, $a_k=S/n$, $a_{k+1}=(S+S/n)/(n+1)=S/(n+1)+S/(n^2+n)=(nS+S)/(n^2+n)=((n+1)S)/(n^2+n)=S/n$.
entonces si al dividir el término por n+1, el término es igual al anterior, si es que este se divide por un numero mayor que n+1 este va a ser menor que el anterior. De las dos formas la serie no va a ser válida.
$3=569936821221962380720^3+(-569936821113563493509)^3+(-472715493453327032)^3$: esta es la tercer menor solucion descubierta para la ecuación $a^3+b^3+c^3=3$ , las otras dos son $1^3+1^3+1^3=3$ y $4^3+4^3+(-5)^3=3$
Avatar de Usuario
Sandy

OFO - Medalla de Bronce-OFO 2019 OFO - Medalla de Plata-OFO 2020 FOFO Pascua 2020 - Copa-FOFO Pascua 2020 COFFEE - Mención-COFFEE Ariel Zylber FOFO 10 años - Copa-FOFO 10 años
OFO - Medalla de Oro-OFO 2021 FOFO 11 años - Medalla-FOFO 11 años OFO - Medalla de Plata-OFO 2022 OFO - Jurado-OFO 2023 FOFO 13 años - Jurado-FOFO 13 años
OFO - Jurado-OFO 2024
Mensajes: 280
Registrado: Lun 27 Nov, 2017 1:59 am
Medallas: 11
Nivel: 3

Re: OFO 2020 Problema 8

Mensaje sin leer por Sandy »

Gianni De Rico escribió: Mié 22 Ene, 2020 12:00 am Sea $a_1 < a_2 < a_3 < \ldots$ una sucesión infinita de números enteros positivos, estrictamente creciente, que cumple la siguiente propiedad: para todo $n \geq 10$, $a_n$ divide a la suma de todos los términos anteriores. Demostrar que existe $m \in \mathbb N$ tal que para todo $n \geq m$ se cumple que $a_n$ es igual a la suma de todos los términos anteriores.
Spoiler: mostrar
Lema $1$: $\sum_{i=0}^{b} x^i=\frac{x^{b+1}-1}{x-1}$
Demostración:
Sea $Y=\sum_{i=0}^{b} x^i$
$x\times Y=\sum_{i=0}^{b} x^{i+1}=\sum_{i=1}^{b+1} x^{i}=x^{b+1}-1+\sum_{i=0}^{b} x^i= x^{b+1}-1+Y$
$\Rightarrow Y\times (x-1)=x^{b+1}-1\Rightarrow Y=\frac{x^{b+1}-1}{x-1}$


Sean:
$S_n=\sum_{i=1}^{n-1} a_i$
$f_n=\frac{S_n}{a_n}$

$f_{n+1}=\frac{S_{n+1}}{a_{n+1}}=\frac{S_n+a_n}{a_{n+1}}<\frac{S_n+a_n}{a_n}=f_n+1$
Pero, como queremos que $f_n$ sea siempre entero, $f_{n+1}<f_n+1$ implica que $f_{n+1}\leq f_n$.
Por un lado, sabemos que, de decrecer, $f_n$ no estaría acotada por abajo, ya que es una sucesión de enteros positivos, por lo que decrece en al menos $1$ cada vez que decrece. Por lo tanto, en algún momento obtendríamos $f_k=1$, y como $f_n\geq f_{n+1}$, $f_n$ sería igual a $1$ para todo $n\geq k$.
Por lo tanto, debe existir un número $m$ tal que, para todo $n\geq m$, $f_n$ es constante, digamos $f_n=r$.
Sea $S_m=k$
Afirmo que, entonces, $a_n=\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{n-m}$ para todo $n\geq m$.
Supongamos que $a_n=\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{n-m}$ para todo $n$ tal que $t\geq n\geq m$.
Veremos que entonces $a_{t+1}=\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{t+1-m}$.

$a_{t+1}=\frac{S_{t+1}}{f_{t+1}}=\frac{\sum_{i=1}^{t} a_i}{r}=\frac{\sum_{i=1}^{m-1} a_i + \sum_{i=m}^{t} a_i}{r}=\frac{k+\sum_{i=m}^{t}\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{i-m}}{r}=\frac{k}{r}\times \left(1+\frac{\sum_{i=m}^{t} \left(1+\frac{1}{r}\right)^{i-m}}{r}\right)=\frac{k}{r}\times \left(1+\frac{\sum_{i=0}^{t-m} \left(1+\frac{1}{r}\right)^{i}}{r}\right)$
Usando el Lema 1, queda lo siguiente:
$ a_{t+1}=\frac{k}{r}\times \left(1+\frac{\left(\frac{\left(1+\frac{1}{r}\right)^{t-m+1}-1}{\left(1+\frac{1}{r}\right)-1}\right)}{r}\right)=\frac{k}{r}\times \left(1+\frac{\left(\frac{\left(1+\frac{1}{r}\right)^{t-m+1}-1}{\frac{1}{r}} \right )}{r} \right)=\frac{k}{r}\times \left(1+\frac{\left(1+\frac{1}{r}\right)^{t-m+1}-1}{r\times \frac{1}{r}}\right)=\frac{k}{r}\times\left(1+\left(1+\frac{1}{r}\right)^{t-m+1}-1\right)=\frac{k}{r}\times\left(1+\frac{1}{r}\right)^{t-m+1}$
Por lo tanto queda demostrado que $a_n=\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{n-m}$ para todo $n$ tal que $t\geq n\geq m$.

Ahora, supongamos que $r^d|k$ para algún $d$ entero no negativo.
$a_{m+d}=\frac{k}{r}\times \left(1+\frac{1}{r}\right)^{d}$
Utilizando el hecho de que $\left ( x+y \right )^{n}=\sum_{i=0}^{n} \binom{n}{i}x^{n-i}y^i$, nos queda lo siguiente:
$a_{m+d}=\frac{k}{r}\left(\sum_{i=0}^{d} \binom{d}{i}1^{d-i}\left(\frac{1}{r}\right)^i\right)=\frac{k}{r}\left( \sum_{i=0}^{d}\binom{d}{i}\left(\frac{1}{r}\right)^i\right)=\sum_{i=0}^{d}\binom{d}{i}\left(\frac{k}{r}\right)\left(\frac{1}{r}\right)^i=\sum_{i=0}^{d}\binom{d}{i}\left(\frac{k}{r^{i+1}}\right)=\binom{d}{d}\left(\frac{k}{r^{d+1}}\right)+\sum_{i=0}^{d-1}\binom{d}{i}\left(\frac{k}{r^{i+1}}\right)=\frac{k}{r^{d+1}}+\sum_{i=1}^{d}\binom{d}{i-1}\left(\frac{k}{r^{i}}\right)$
Pero todos los términos de la sumatoria son enteros, ya que $r^n|k$ para todo $n\leq d$, y como $a_{m+d}$ también es entero, $\frac{k}{r^{d+1}}$ también debe serlo.
Por lo tanto, si $r^d|k$, entonces $r^{d+1}|k$. Y como sabemos que $d=0$ funciona, eso implica que $r^n|k$ para todo $n\in \mathbb{Z^{+}_{0}}$.
Pero dado que $k$ es un entero positivo (obviamente finito), el único valor de $r$ que puede satisfacer esto es $r=1$.
Por lo tanto, demostramos que existe un $m \in \mathbb N$ tal que para todo $n \geq m$, se cumple que $f_n=1\iff \frac{\sum_{i=1}^{n-1} a_i}{a_n}=1\iff \sum_{i=1}^{n-1} a_i=a_n$.
Fallo inapelable.
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 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: 460
Registrado: Jue 12 Oct, 2017 10:17 pm
Medallas: 16
Nivel: Exolímpico
Ubicación: Ciudad Gotica

Re: OFO 2020 Problema 8

Mensaje sin leer por Joacoini »

Spoiler: mostrar
Para $i\geq 10$ consideramos la secuencia $b_i=\frac{a_1+...+a_{i-1}}{a_i}$.

Tenemos que para $i\geq 10$

$a_i<a_{i+1}=\frac{a_1+...+a_i}{b_{i+1}}\Rightarrow b_{i+1}a_i<a_1+...+a_{i-1}+a_i=b_ia_i+a_i\Rightarrow b_{i+1}<b_i+1\Rightarrow b_{i+1}\leq b_i$

Esto ultimo porque trabajamos con enteros.

Supongamos que existe algún $k$ tal que para todo $n\geq k$ se cumple que $b_n=b_{n+1}=c>1$, lo que significa que $c$ divide a $a_1+...+a_n$ para todo $n\geq k$.

Sea $S_i=a_1+...+a_i$ y $V_i=v_c(S_i)$.

Para $i\geq k$

$v_c(a_{i+1})=v_c(\frac{S_i}{c})=V_i-1$

$V_{i+1}=v_c(S_i+a_{i+1})$

Como $c$ divide a $S_i$ y $v_c(S_i)\neq v_c(a_{i+1})$.

$V_{i+1}=min(v_c(S_i);v_c(a_{i+1}))=min(V_i;V_i-1)=V_i-1$

Tenemos que $V_{k+V_k}=V_k-V_k=0$ lo que contradice la suposición.

Como trabajamos con enteros positivos, $b_i\geq b_{i+1}$ y no sucede que existe algún $k$ tal que para todo $n\geq k$ se cumple que $b_n=b_{n+1}=c>1$ tenemos que existe un $m$ tal que para todo $n\geq m$ se cumple que $b_n=b_{n+1}=1$ lo cual significa que para todo $n \geq m$ se cumple que $a_n$ es igual a la suma de todos los términos anteriores.
2  
NO HAY ANÁLISIS.
Uriel J

OFO - Mención-OFO 2019 FOFO 9 años - Mención Especial-FOFO 9 años COFFEE - Mención-COFFEE Matías Saucedo OFO - Medalla de Bronce-OFO 2020 FOFO Pascua 2020 - Medalla-FOFO Pascua 2020
COFFEE - Mención-COFFEE Carolina González COFFEE - Mención-COFFEE Ariel Zylber COFFEE - Mención-COFFEE Iván Sadofschi FOFO 10 años - Medalla-FOFO 10 años OFO - Medalla de Plata-OFO 2021
OFO - Medalla de Plata-OFO 2022 OFO - Medalla de Oro-OFO 2023 FOFO 13 años - Copa-FOFO 13 años OFO - Jurado-OFO 2024
Mensajes: 57
Registrado: Jue 29 Nov, 2018 2:46 pm
Medallas: 14
Nivel: Exolímpico

Re: OFO 2020 Problema 8

Mensaje sin leer por Uriel J »

Solución:
Spoiler: mostrar
Si $n\geq 10$, $a_n$∣$a_{n−1}+a_{n−2}+.....+a_1$

Sea $a_{n−1} + a_{n−2} + ...... + a_1$ = $x$

Y entonces $\frac{x}{a_n} = i$ $ \Rightarrow $ $\frac{x}{i}$ = $a_n$

Ahora la suma de $a_1$ hasta $a_n$ es igual a $x$ + $a_n$

Entonces $\frac{x + a_n}{a_n}$ = $i+1$; por ende $\frac{x + a_n}{a_{n+1}} \leq i$ ya que $a_{n+1}$ > $a_n$ entonces necesitamos un divisor mayor a $a_n$ y como $\frac{x + a_n}{a_n}$ = $i+1$ entonces necesitamos que el resultado sea menor a este ultimo porque sino significa que el valor de $a_{n+1}$ disminuye o es igual a $a_n$
Entonces $\frac{x + a_n}{a_{n+1}} \leq i$

Ahora vamos a demostrar que en algun momento esta ultima cuenta va a ser menor que $i$ porque si para cada $a_p$ la division con la suma de todos los numeros anteriores con $a_p$ es igual a $i$, nunca va a existir tal $m$

$\frac{x + a_n}{a_{n+1}}$ = $i$; Veamos que para que esto funcione, $x + a_n$ tiene que ser multiplo de $i$, entonces $a_n$ tiene que ser multiplo de $i$ pero para que esto pase, significa que $x$ = $i^2$ . $c$
Y así la suma de los numeros anteriores a $a_n$ siempre va a tener que ser $i^2$ . $c$ para que $\frac{x + a_n}{a_{n+1}}$ sea siempre $i$ pero veamos que en un momento esto va a parar de pasar(esto porque en un momento la suma de los numeros anteriores de la sucesion no va a poder expresarse mas como $i^2$ ya que se iban reduciendo despues de cada operacion ya que la división retira factores), por ende esa división va a ser por lo menos $i−1$ hasta llegar a que esa división sea igual a $1$. (Veamos que $1^2$ = $1$ y como la suma siempre va a ser positiva y $a_n$ también, esa división siempre va a poder ser $1$).En ese momento llegamos a que $a_n$ es igual a la suma de todos los numeros anteriores, ahora veamos $a_{n+1}$ divide a $a_n$ . $2$ y $a_{n+1}$ es mayor a $a_n$ y $a_n$ es el mayor divisor de la suma diferente a $a_n$ . $2$ entonces significa que $a_{n+1}$ = $a_n$ . $2$
Entonces con esto demostramos que después de $a_n$ todos los números de la sucesión van a ser iguales a la suma de los anteriores numeros de la sucesion

Con esto demostramos que existe tal $m$
1  
Nice bro, congratulations!
Responder