OliForum Matematico

Sia $ a_1,a_2,... $ una sequenza di interi con infiniti interi positivi ed infiniti interi negativi. Supponiamo che per ogni n positivo $ a_1,a_2,...,a_n $ danno tutti resti diversi mod n. Dimostrare che ogni intero compare nella sequenza esattamente una volta.

Ci provo, anche se non sono convintissimo...
Innanzitutto dimostro che se un numero compare, esso non compare più di una volta. Suppongo per assurdo che esistano $i<j$ t.c.$a_{i}=a_{j}$: allora troncando la sequenza al termine $a_{j}$, abbiamo $a_{i} \equiv a_{j} \pmod j$. Dato che $a_{1},...,a_{j}$ e $0,...,j-1$ hanno la stessa cardinalità, segue che una classe di resto non verrà rappresentata, assurdo per ipotesi.

Lemma 1: sia $i<j$. Allora $\left|a_{i}- a_{j}\right| < j$.
Dim: per ipotesi $a_{1},...,a_{j}$ prendono tutte le classi di resto modulo $j$ quindi $a_{i} \not\equiv a_{j} \pmod j$; analogamente vale $a_{i} \not\equiv a_{j} \pmod k$ per ogni $k>j$. Se $\left|a_{i}- a_{j}\right| =k, k \geq j$ allora $a_{i} \equiv a_{j} \pmod k$ e, come prima, una classe di resto modulo $k$ non viene rappresentata.

Lemma 2: per ogni $n$, $a_{1},...,a_{n}$ sono $n$ numeri consecutivi (in qualche permutazione).
Dim: induzione. Il passo base $n=2$ è vero perchè dal lemma 1 ottengo $\left|a_{1}- a_{2}\right| < 2$ e non può essere $0$ perchè sono distinti. Passo induttivo: suppongo vero per $n$ e lo dimostro per $n+1$. Siano $a_{min}$ e $a_{max}$ rispettivamente il più piccolo e il più grande tra i primi $n$ termini, per ipotesi induttiva vale $a_{max}- a_{min} =n-1$. Se $a_{n+1}= a_{min}-1$ o $a_{n+1}= a_{max}+1$ il passo induttivo è verificato; altrimenti $\left|a_{max}- a_{n+1}\right| > n+1$ oppure $\left|a_{min}- a_{n+1}\right| > n+1$, entrambe assurde per il Lemma 1.

Supponiamo per assurdo che esiste $A$ intero che non compare nella sequenza. Allora $\forall i$ deve valere $a_{i} > A$ oppure $a_{i} < A$: l'esistenza di $h,k$ t.c. $a_{h} < A < a_{k}$ implica che $a_{1},...,a_{max(h,k)}$ non contiene tutti termini consecutivi e contraddice il Lemma 2. A questo punto, se $a_{i} > A$ $\forall i$ la sequenza contiene un numero finito di interi negativi, se $a_{i} < A$ $\forall i$ essa contiene un numero finito di interi positivi: ed entrambi i casi contraddicono le ipotesi, perciò $A$ non esiste e tutti gli interi compaiono nella sequenza.
Da dove viene questo problema?

Leonida ha scritto:Ci provo, anche se non sono convintissimo...
Innanzitutto dimostro che se un numero compare, esso non compare più di una volta. Suppongo per assurdo che esistano $i<j$ t.c.$a_{i}=a_{j}$: allora troncando la sequenza al termine $a_{j}$, abbiamo $a_{i} \equiv a_{j} \pmod j$. Dato che $a_{1},...,a_{j}$ e $0,...,j-1$ hanno la stessa cardinalità, segue che una classe di resto non verrà rappresentata, assurdo per ipotesi.

Lemma 1: sia $i<j$. Allora $\left|a_{i}- a_{j}\right| < j$.
Dim: per ipotesi $a_{1},...,a_{j}$ prendono tutte le classi di resto modulo $j$ quindi $a_{i} \not\equiv a_{j} \pmod j$; analogamente vale $a_{i} \not\equiv a_{j} \pmod k$ per ogni $k>j$. Se $\left|a_{i}- a_{j}\right| =k, k \geq j$ allora $a_{i} \equiv a_{j} \pmod k$ e, come prima, una classe di resto modulo $k$ non viene rappresentata.

Lemma 2: per ogni $n$, $a_{1},...,a_{n}$ sono $n$ numeri consecutivi (in qualche permutazione).
Dim: induzione. Il passo base $n=2$ è vero perchè dal lemma 1 ottengo $\left|a_{1}- a_{2}\right| < 2$ e non può essere $0$ perchè sono distinti. Passo induttivo: suppongo vero per $n$ e lo dimostro per $n+1$. Siano $a_{min}$ e $a_{max}$ rispettivamente il più piccolo e il più grande tra i primi $n$ termini, per ipotesi induttiva vale $a_{max}- a_{min} =n-1$. Se $a_{n+1}= a_{min}-1$ o $a_{n+1}= a_{max}+1$ il passo induttivo è verificato; altrimenti $\left|a_{max}- a_{n+1}\right| > n+1$ oppure $\left|a_{min}- a_{n+1}\right| > n+1$, entrambe assurde per il Lemma 1.

Supponiamo per assurdo che esiste $A$ intero che non compare nella sequenza. Allora $\forall i$ deve valere $a_{i} > A$ oppure $a_{i} < A$: l'esistenza di $h,k$ t.c. $a_{h} < A < a_{k}$ implica che $a_{1},...,a_{max(h,k)}$ non contiene tutti termini consecutivi e contraddice il Lemma 2. A questo punto, se $a_{i} > A$ $\forall i$ la sequenza contiene un numero finito di interi negativi, se $a_{i} < A$ $\forall i$ essa contiene un numero finito di interi positivi: ed entrambi i casi contraddicono le ipotesi, perciò $A$ non esiste e tutti gli interi compaiono nella sequenza.
Da dove viene questo problema?

E' giusta Era l'imo 2005/2