sequenza infinita

[Chuck Schuldiner]

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.

[Leonida]

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?

[Chuck Schuldiner]

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