permutatie van de gehele getallen

Opgave - IMO 2005 dag 1 vraag 2

We hebben een oneindige rij $a_1,a_2,\cdots$ van gehele getallen zodat geldt dat $a_1,\cdots,a_n$ de $n$ resten modulo $n$ vertegenwoordigen.
De rij bevat zowel oneindig veel positieve als negatieve waarden,
Bewijs dan dat de rij ieder gehele getal exact $1$ keer bevat.

Oplossing

Merk allereerst op dat er geen geheel getal kan zijn dat de rij twee keer bevat; mocht dit wel het geval zijn, dan zou er voor $n$ groot genoeg een rest modulo $n$ zijn die twee keer vertegenwoordigd is in $a_1, a_2, ..., a_n$. Wegens het duivenhokprincipe geldt dan dus dat er een rest niet vertegenwoordigd is, contradictie!

Stel zonder verlies van de algemeenheid dat $a_1=0$. Als $a_1$ een andere waarde dan nul heeft, kan je namelijk van elke term van de rij hetzelfde gepaste getal optellen of aftrekken zodat $a_1=0$. Dan zal de voorwaarde dat de eerste $n$ termen van de rij de $n$ resten modulo $n$ vertegenwoordigen, behouden blijven. Stel namelijk dat er voor een bepaalde $n$ twee keer dezelfde rest is, dan zal voor bepaalde $a,b,k$ gelden dat $a+k \equiv b+k \pmod n$, dus $a \equiv b \pmod n$, contradictie! Als er in de oorspronkelijke rij een geheel getal ontbreekt, zal er automatisch in de rij met $a_1=0$ ook één ontbreken en als er geen ontbreekt, zal er in de rij met $a_1=0$ ook geen ontbreken.

Merk nu op dat als $i \leq n$, geldt dat $-n < a_i < n$. Stel dat $|a_i|>n$. Dan zouden $a_1$ en $a_i$ congruent zijn met elkaar modulo een getal groter dan $n$, contradictie! Als $|a_i|=n$, dan zouden $a_1$ en $a_i$ congruent zijn met elkaar modulo $n$, ook een contradictie! Hieruit volgt dat voor een rest $k$ er maximaal twee mogelijkheden zijn om deze te representeren modulo $n$; anders zou er wegens het DVH één zijn wiens absolute waarde groter dan of gelijk aan $n$ is.

Stel nu dat er een positief geheel getal $k$ ontbreekt in de rij. Zij $i$ een strikt positief geheel getal. Dan geldt dat voor een bepaalde $x \leq k+i$, $a_x=-i$; mocht dit niet het geval zijn, dan zou de rest $k$ modulo $k+i$ niet vertegenwoordigd zijn in $a_1,...,a_{k+i}$. Dit wilt zeggen dat voor elke $i>0$ geldt dat in de verzameling $S=\{a_1,a_2,\ldots,a_{k+i}\}$ alle getallen $-1, -2, ..., -i$ al eens moeten zijn voorgekomen en dat er niet meer dan $k$ positieve getallen zijn in $S$. Dit impliceert dat het aantal positieve getallen in de rij eindig is, contradictie!

Analoog tonen we aan dat er geen negatief getal kan ontbreken. Q.E.D.