De stelling van Ramsey

Klaas Pieter Hart

Abstract:

Als je heel veel dingen over weinig dozen verdeelt zal tenminste één van die dozen behoorlijk vol raken. Veel resultaten uit de wiskunde zijn tot deze observatie terug te brengen; de stelling van Ramsey is één van de fraaiste voorbeelden.

Als je vijf individuen bij elkaar zet weet je zeker dat er tenminste drie hetzelfde geslacht zullen hebben. Met andere woorden: als je alléén de eigenschap ``man of vrouw'' gebruikt om mensen te onderscheiden zullen er in een groep van vijf mensen zeker drie zijn die je niet uit elkaar kunt houden.

Je kunt naar hartelust op dit thema variëren: als je 367 mensen bij elkaar zet zijn er zeker twee op dezelfde dag jarig (denk aan 29 februari). Als je dertien getallen uit het interval $(-\frac12\pi,\frac12\pi)$ kiest zullen er twee minder dan $\frac1{12}\pi$ verschillen.

Je kunt zelfs een algemene stelling formuleren.

Stelling. Als $m$ en $n$ twee natuurlijke getallen zijn en je verdeelt $nm+1$ dingen over $m$ potten dan moet één pot tenminste $n+1$ dingen bevatten.

De stelling van Ramsey, die we in dit artikel bespreken, zegt dat dergelijke verschijnselen altijd optreden: als je een aantal eigenschappen opschrijft kun je bij een gegeven $n$ altijd een $N$ vinden zó dat in elke groep van $N$ mensen er $n$ te vinden die door die eigenschappen niet onderscheiden kunnen worden. De eigenschappen waar de stelling van Ramsey over spreekt kunnen ook van toepassing zijn op paren, drietallen, enzovoort. In dit artikel bekijken we eigenschappen van paren.