verzamelingen

Kies $x_1=1$. Kies nu het kleinste element van $S$, ongelijk aan $x_1$ dat werkt voor $x_2$. zoek vervolgens voor $x_3$ de kleinste waarde in $S$, op $x_1$ en $x_2$ na, die werkt. Enzovoort. Veronderstel dat deze manier van kiezen voor alle $x_i$ fout loopt bij $x_k$, voor een zekere $k\leq 100$. Met andere woorden, alle $x_1, x_2, \dots x_{k-1}$ hebben al een (verschillende) waarde toegekend gekregen, maar geen enkele van de resterende $10^6-(k-1)$ waarden in $S$ werkt als keuze voor $x_k$.

Zij $A=\{a_1, a_2,\dots,a_{101}\}$ en definieer $A_i\colon=\{a+x_i\mid a \in A\}$.

We wilden dat $x_k\ne x_i+a_m-a_n$ voor alle $1\leq i < k$ en $1\le m,n\le 101$, $m\ne n$, maar dit mislukt voor elke keuze van $x_k\in S\setminus \{x_1,\dots,x_{k-1}\}$ per veronderstelling. Dat betekent, omdat er $101\cdot 100 \cdot (k-1)$ keuzes zijn voor $i,m,n$, dat er maximaal $10100(k-1)$ waardes in $S\setminus \{x_1,\dots,x_{k-1}\}$ zijn die $x_k$ niet mag aannemen, of anders zou $x_k+a_n=x_i+a_m$, zodat $x_k$ niet aan de voorwaarde voldoet dat $A_k$ een lege doorsnede heeft met alle $A_j$ met $1\le j < k$.

Precies omdat we $k$ namen zodat we geen $x_k$ konden vinden, moeten er meer waarden zijn die $x_k$ onmogelijk kan aannemen dan dat er waarden initieel beschikbaar waar. Met andere woorden, er zijn minder waarden waaruit je $x_k$ kon kiezen dan het maximaal aantal onbeschikbare waarden voor $x_k$ in $S$: $$10^6-(k-1)< 10100(k-1)$$

Hieruit volgt $k -1\ge \lceil \frac{10^6}{10101}\rceil=\lceil 99+\frac{1}{10101}\rceil=100$, een contradictie met de aanname dat $k\le 100$.
Deze contradictie betekent dat het verkeerd was om aan te nemen dat het proces van $x_i$ kiezen zou fout lopen voor een bepaalde $k\leq 100$, en het gevraagde is bewezen, QED