Wanorde

In de wiskunde wemelt het van de stellingen die elk op hun eigen manier zeggen dat totale wanorde onmogelijk is.

De stelling van Van der Waerden, die een vermoeden van Baudet bevestigde, is er zo één. Het vermoeden van Baudet gaat over het verdelen van de verzameling der natuurlijke getallen, $\mathbb{N}$, in twee delen. De stelling van Van der Waerden gaat over iets meer: het verdelen van $\mathbb{N}$ in eindig veel delen. Voor we het vermoeden en de stelling formuleren kijken we eerst naar het allereenvoudigste geval.

In dit geval proberen we wanorde te creëren door $\mathbb{N}$ in twee verzamelingen $A$ en $B$ te verdelen op zo'n manier dat elk rekenkundig rijtje van lengte drie wordt gesplitst: elke verzameling van de vorm $\{b, b+v, b+2v\}$ (een rekenkundig rijtje van lengte drie dus) bevat punten van $A$ en van $B$. Anders gezegd: noch $A$ noch $B$ mag een rekenkundig rijtje van lengte drie bevatten.

In het begin lijkt dat te lukken: ga maar eens na dat $A = \{1,4,5,8\}$ en $B=\{2,3,6,7\}$ een wanordelijke verdeling van $\{1,2,3,4,5,6,7,8\}$ opleveren: $A$ en $B$ bevatten geen rekenkundig rijtje van lengte drie.

Echter, bij $n=9$ strandt onze poging: hoe je de verzameling $\{1,2,3,4,5,6,7,8,9\}$ ook in deelverzamelingen $A$ en $B$ opdeelt, er is altijd een rekenkundig rijtje $\{b, b+v, b+2v\}$ dat helemaal binnen $A$ of helemaal binnen $B$ ligt.

Dat kun je nagaan door alle 256 opdelingen langs te lopen. Dat duurt wel even, maar het kan korter: als je systematisch probeert een wanordelijke verdeling te maken zul je zien dat elke poging doodloopt.

Aan het eind van dit artikel zullen we laten zien hoe dit in zijn werk gaat maar we gaan het eerst over het algemene vermoeden van Baudet, ofwel de stelling van Van der Waerden, hebben.

Het vermoeden

Hoe Baudet tot zijn vermoeden kwam weten we niet, misschien wel door probeersels als aan het eind van dit artikel, maar hij dacht dat het antwoord op de volgende vraag bevestigend zou luiden:

Als je de hele verzameling $\mathbb{N}$ in twee verzamelingen $A$ en $B$ verdeelt, is het dan noodzakelijk zo dat (ten minste) één van die twee verzamelingen willekeurig lange rekenkundige rijtjes bevat?

Aan het begin hebben we gezien dat één van de stukken een rekenkundig rijtje van lengte drie moet bevatten, omdat dat al binnen $\{1,2,3,4,5,6,7,8,9\}$ moet gebeuren. Wat ook bekend is, is dat als je $\{1, 2, \dots, 35\}$ in twee verzamelingen opdeelt er een rekenkundig rijtje van lengte vier is dat geheel binnen één van de verzamelingen ligt. De Nederlandse wiskundige Van der Waerden publiceerde in 1927 een bewijs. In het artikel staat een algemenere bewering die lijkt op wat we al gezien hebben:

Gegeven twee natuurlijke getallen $k$ en $l$ bestaat een natuurlijk getal \(W(k,l)\) zodanig dat ongeacht hoe je de verzameling $\{1, 2, 3, \dots, W(k, l)\}$ in $k$ verzamelingen opdeelt er altijd een rekenkundig rijtje van lengte $l$ geheel binnen één van de verzamelingen ligt.

Hier kun je het vermoeden van Baudet uit afleiden. Neem een verdeling van $N$ in twee verzamelingen $A$ en $B$. Voor elke $l$ is er dan binnen $\{1, 2, 3, \dots, W(2,l)\}$ een rekenkundig rijtje van lengte $l$ dat geheel binnen $A$ of geheel binnen $B$ ligt. Hierbij is telkens $A$ of $B$ de verzameling die een rekenkundig rijtje van lengte $l$ bevat. Maar dan is of $A$ of $B$ oneindig vaak de verzameling en dus bevat of $A$ of $B$ willekeurig lange rekenkundige rijtjes.

Het bewijs

Er zijn veel bewijzen van de stelling gegeven. Geen van die bewijzen is echt eenvoudig; dat is een beetje te zien aan het bewijs hieronder dat $W(2,3)=9$. Daar moeten we een paar gevallen, deelgevallen en deeldeelgevallen onderscheiden. Voor langere rekenkundige rijtjes zou dat alleen maar erger worden. De bewijzen die gegeven zijn gaan anders dan 'systematisch proberen' maar zijn nog steeds veel te lang om hier samen te vatten. Voor wie meer wil weten, zie de link aan het eind.

W(2, 3) = 9

We hebben al gezien dat $\{1, 2, 3, 4, 5, 6, 7, 8\}$ een wanordelijke verdeling heeft. We gaan nu laten zien dat $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ dat niet heeft en daarmee is dan vastgesteld dat $W(2,3)=9$.

We gaan proberen $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ op te delen in verzamelingen $A$ en $B$ die elk geen rekenkundig rijtje van lengte drie bevatten. En we zullen zien dat deze poging tot mislukken gedoemd is. Het is handig hier potlood en papier bij de hand te hebben en de pogingen met $a$-tjes en $b$-tjes na te spelen. We laten in één geval zien hoe dat gaat. We beginnen met twee gevallen te onderscheiden: de getallen $1$ en $2$ in dezelfde verzameling versus de getallen $1$ en $2$ in verschillende verzamelingen, daarna vertakken die mogelijkheden zich een paar keer, maar elke tak loopt dood.

Geval 1: $1$ en $2$ gaan in $A.$
Dan moet $3$ in $B,$ omdat $\{1, 2 ,3 \}$ gesplitst moet worden. De situatie is nu $aab\_ \_ \_ \_ \_ \_.$ Onze poging wanorde te creëren vertakt zich nu in twee deelgevallen.

Geval 1a: $4$ gaat in $A.$
Omdat $\{1, 4, 7\}$ gesplitst moet worden moet $7$ in $B,$ en $6$ ook want $\{2, 4, 6\}$ moet gesplitst, dit geeft $aaba\_bb\_ \_.$ Maar $\{5, 6, 7\}$ en $\{6, 7, 8\}$ moeten gesplitst, dus $5$ en $8$ moeten in $A,$ we krijgen $aabaabba\_.$ Echter, nu is $\{2, 5, 8\}$ niet gesplitst, dus dit loopt dood. Van nu af moet je zelf de $a$-tjes en $b$-tjes bij gaan houden.

Geval 1b: $4$ gaat in $B.$
Dan moet $5$ in $A$ om $\{3,4,5\}$ te splitsen. Om $\{1,5,9\}$ en $\{2,5,8\}$ te splitsen moeten $8$ en $9$ dan in $B.$ Maar nu moet $7$ in $A$ (splits $\{7,8,9\}).$ De zaak loopt weer dood want om zowel $\{5,6,7\}$ als $\{4,6,8\}$ te splitsen mag $6$ niet in $A$ en niet in $B.$

Geval 2: $1$ gaat in $A$ en $2$ gaat in $B.$
We vertakken weer.

Geval 2a: $3$ gaat in $A.$
Dan moet $5$ in $B$ (splits $\{1,3,5\})$ en dan moet $8$ in $A$ (splits $\{2,5,8\}).$ Nu moet we weer vertakken.

Geval 2aa: $4$ gaat in $A.$
Om $\{1,4,7\}$ te splitsen gaat $7$ in $B$ en dan moet $6$ in $A$ (splits $\{5,6,7\}).$ Dit loopt dood: $\{4,6,8\}$ is niet gesplitst.

Geval 2ab: $4$ gaat in $B.$
Weer moet $6$ in $A$ (om $\{4,5,6\}$ te splitsen) en $7$ moet in $B$ om $\{6,7,8\}$ te splitsen. Maar nu kunnen we niet tegelijk $\{3,6,9\}$ en $\{5,7,9\}$ splitsen.

Geval 2b: $3$ gaat in $B.$
Dan moet $4$ in $A$ (splits $\{2,3,4\})$ en $7$ moet in $B$ (splits $\{1,4,7\}).$ Verder moet $5$ in $A$ om $\{3,5,7\}$ te splitsen, dus $6$ in $B$ (splits $\{4,5,6\})$ en $8$ in $A$ (splits $\{6,7,8\}).$ Ook dit loopt nu dood: we kunnen niet $\{1,5,9\}$ en $\{3,6,9\}$ tegelijk splitsen.

Hoe dan ook: het lukt ons niet wanorde in $\{1,2,3,4,5,6,7,8,9\}$ te creëeren.