partities van N

Opgave - IrMO 1998 dag 3 vraag 2

Toon aan dat we $\mathbb N$ in drie disjuncte deelverzamelingen kunnen partitioneren zodat als $|m-n|=2$ of $5$, dan zitten $m$ en $n$ in verschillende deelverzamelingen. Toon aan dat we $\mathbb N$ in vier disjuncte deelverzamelingen kunnen partitioneren zodat als $|m-n|=2,3$ of $5$, dan zitten $m$ en $n$ in verschillende deelverzamelingen, maar dat dit niet mogelijk is met slechts drie disjuncte deelverzamelingen.

Oplossing

$(a)$ de 3 restklassen modulo 3 voldoen, want dan is $\mid m-n\mid$ altijd een drievoud als deze twee in dezelfde restklasse zitten.

$(b)$ de 4 restklassen modulo 4 voldoen, idem als $(a)$

$(c)$ als er maar 3 partities zijn, mag elk verschil tussen twee elementen uit dezelfde deelverzameling niet 2,3,5 zijn. stel dat er zo'n 3 disjuncte verzamelingen bestaan. Bekijk nu een element $a$ uit de eerste deelverzameling, stel nu WLOG dat er een element $a+2$ in de tweede deelverzameling zit en dan moet $a+5$ in de derde deelverzameling zitten. $a+3$ zit in de tweede deelverzameling, want anders is er ergens een verschil van 2 of 3 in dezelfde deelverzameling. Om dezelfde reden zitten $a+7$ en $a+8$ in de eerste verzameling. $a+6$ moet in de derde partitie.

1) $a$, $a+4$, $a+7$, $a+8$
2) $a+2$,$a+3$
3) $a+5$, $a+6$

Maar nu zijn we klaar om een contradictie af te leiden. Inderdaad, want $a+4$ mag in geen enkele deelverzameling! verschil van $3,2,2$ resp. met $a+7,a+2,a+6 $ $\blacksquare$