IMO 2005 - P2

Avatar de Usuario
Gianni De Rico

FOFO 7 años - Mención Especial OFO - Medalla de Oro
Mensajes: 940
Registrado: Vie 16 Sep, 2016 6:58 pm
Medallas: 2
Nivel: Exolímpico
Ubicación: Rosario
Contactar:

IMO 2005 - P2

Mensaje sin leer por Gianni De Rico » Sab 07 Jul, 2018 1:32 pm

Sea $a_1,a_2,\ldots$ una sucesión de enteros que tiene infinitos términos positivos e infinitos términos negativos. Supongamos que para cada entero positivo $n$, los números $a_1,a_2,\ldots ,a_n$ tienen $n$ restos distintos en la división por $n$. Demuestre que cada entero aparece exactamente una vez en la sucesión.
[math]

juandodyk
Mensajes: 14
Registrado: Mar 26 Jun, 2018 1:59 am
Nivel: Exolímpico

Re: IMO 2005 - P2

Mensaje sin leer por juandodyk » Sab 28 Jul, 2018 11:50 pm

Spoiler: mostrar
Notar primero que $a_i\neq a_j$ si $i\neq j$ porque tienen distinto resto en la división por $\max\{i,j\}$. Si $i,j\leqq n$ tenemos que $a_i, a_j$ tienen el mismo resto en la división por $|a_i-a_j|$ (porque $|a_i-a_j| \mid a_i-a_j$) luego $|a_i-a_j|<n$ (si $d=|a_i-a_j| \geqq n$ entonces $a_1, \ldots, a_d$ incluye a $a_i, a_j$, pero tienen restos distintos en la división por $d$, absurdo). Entonces si $a_*$ es el mínimo de $a_1, \ldots, a_n$ y $a^*$ el máximo, tenemos $a^*-a_* \geqq n-1$ (porque hay $n-2$ números distintos entre medio de ellos) pero $a^*-a_*\leqq n-1$, luego es una igualdad y los números $a_1, \ldots, a_n$ son (en algún orden) $a_*, a_*+1, \ldots, a_*+n-1$. Se deduce que si $a_i$ y $a_j$ están en la secuencia, también están todos los enteros $a$ tales que $a_i \leqq a \leqq a_j$. Como hay infinitos positivos e infinitos negativos, hay $a_i$ arbitrariamente chicos y $a_j$ arbitrariamente grandes, luego están todos los enteros.

BrunZo

OFO - Medalla de Bronce FOFO 8 años - Mención Especial OFO - Medalla de Plata FOFO Pascua 2019 - Medalla
Mensajes: 85
Registrado: Mar 21 Nov, 2017 8:12 pm
Medallas: 4
Nivel: 1

Re: IMO 2005 - P2

Mensaje sin leer por BrunZo » Dom 02 Jun, 2019 6:47 pm

Solución:
Spoiler: mostrar
Asumamos, WLOG, que $a_1=0$ (puesto que restamos $a_1$ de todos los términos de la sucesión, y ambas propiedades se siguen cumpliendo).
Es claro que $a_i\neq a_j$ para $i\neq j$.
Sabemos que $0=a_1\not\equiv a_n\mod m\iff m\not\mid a_n$ para todo $m\geq n$. De este modo, $a_n\in (-n,n)$.

Decimos que una secuencia de $n$ números es buena si cumplen que: Si $x$ pertenece a la secuencia, $x-\text{sgn}(x)$ también lo hace ($\text{sgn}(x)=\frac{x}{|x|}$).
Notemos que, como $a_2\in\{-1,1\}$, la secuencia $a_1, a_2$ es buena.
Ahora, supongamos que $a_1, a_2,\dots, a_n$ es buena. Sean $a_-=\text{min}(a_1,a_2,\dots,a_n)$ y $a_+=\text{max}(a_1,a_2,\dots,a_n)$.
Es claro entonces, que si el resto de $a_{n+1}$ módulo $n+1$ es $r$ (con $0\leq r\leq n$), entonces $a_+<r<(n+1)+a_-$. Esto es, aplicando que $a_{n+1}\in[-n,n]$, o bien $a_n=a_++1$, o bien $a_n=a_--1$, de lo que se sigue que $a_1, a_2,\dots, a_n, a_{n+1}$.
Aplicando inducción, para todo $n$, la secuencia $a_1, a_2,\dots, a_n$ es buena.

Finalmente, como hay infinitos números positivos, $a_n$ puede tomar valores arbitrariamente grandes, pero por el párrafo anterior, también debe tomar todos los valores positivos menores. Similarmente, $a_n$ toma todos los valores desde $-1$ hasta un número arbitrariamente pequeño, con lo que finalizamos.

Responder