Sia $ a_1, a_2, \ldots $ una successione di interi che contiene infiniti termini negativi e infiniti termini positivi, tale che, per ogni n, i numeri $ a_1, \ldots, a_n $ danno tutti resti diversi nella divisione per n.
Dimostrare che ogni intero compare esattamente una volta in tale successione.
IMO 2005 - Problema A2
Proviamo...
Sol:
I) un intero non può ripetersi più di una volta: è evidente che se a un certo punto della sequenza ci si trovasse ad avere due numeri uguali, essi darebbero lo stesso resto divisi per qualsiasi numero. Ciò falserebbe l'ipotesi di avere ad ogni passo n classi di resto distinte tra gli n termini della sequenza.
II) ogni intero compare almeno una volta: consideriamo un certo termine $ a_n $: esso deve distare al massimo $ n-1 $ da ciascuno dei termini precedenti. Infatti se distasse $ n+k $ (con $ k \in \mathbb{N} $ ) da un qualche $ a_m $, si avrebbe poi, al passo $ n+k $, $ a_n \equiv a_m \pmod{n+k} $, contraddicendo anche in questo caso l'ipotesi di avere tutte le classi di resto distinte.
Poichè all' $ n $-esimo passo ci sono $ n $ termini, e tra questi i due più distanti distano al massimo $ n-1 $, ne segue che l'unica configurazione compatibile con queste condizioni è una $ n $-upla di interi consecutivi: ad ogni passo i termini della sequenza saranno tutti consecutivi.
L'ipotesi sull'infinità di positivi e negativi, poi, garantisce che compariranno tutti gli interi, non essendoci nè un massimo nè un minimo (nè "buchi" interni, per quanto detto prima).
Sol:
I) un intero non può ripetersi più di una volta: è evidente che se a un certo punto della sequenza ci si trovasse ad avere due numeri uguali, essi darebbero lo stesso resto divisi per qualsiasi numero. Ciò falserebbe l'ipotesi di avere ad ogni passo n classi di resto distinte tra gli n termini della sequenza.
II) ogni intero compare almeno una volta: consideriamo un certo termine $ a_n $: esso deve distare al massimo $ n-1 $ da ciascuno dei termini precedenti. Infatti se distasse $ n+k $ (con $ k \in \mathbb{N} $ ) da un qualche $ a_m $, si avrebbe poi, al passo $ n+k $, $ a_n \equiv a_m \pmod{n+k} $, contraddicendo anche in questo caso l'ipotesi di avere tutte le classi di resto distinte.
Poichè all' $ n $-esimo passo ci sono $ n $ termini, e tra questi i due più distanti distano al massimo $ n-1 $, ne segue che l'unica configurazione compatibile con queste condizioni è una $ n $-upla di interi consecutivi: ad ogni passo i termini della sequenza saranno tutti consecutivi.
L'ipotesi sull'infinità di positivi e negativi, poi, garantisce che compariranno tutti gli interi, non essendoci nè un massimo nè un minimo (nè "buchi" interni, per quanto detto prima).