duiventil principe


Het duiventilprincipe.	© h.hofstede (h.hofstede@hogeland.nl)

Het duiventilprincipe (Engels: pigeon-hole, Nederlands ook wel: "laadjes-principe") is zeer eenvoudig, maar je kunt er verrassende dingen mee bewijzen.
Het principe zegt het volgende:

"Als een aantal duiven in gaten in een duiventil moeten,
en er zijn meer duiven dan gaten,
dan moeten er in minstens één gat twee duiven."

Klinkt eenvoudig niet?
Bij een bewijs is het alleen de kunst de 'duiven' en de 'gaten' goed te kiezen. Voorbeeld is de volgende stelling:

Er wonen in Nederland op elk moment minstens twee mensen
die precies even zwaar (in hele kg),
én even lang (in hele cm) én even oud (in hele jaren) zijn.

Het bewijs:
Laten we voor het gemak zeggen dat de gewichten van de mensen variëren tussen de 0 en 300 kg, dat hun lengte varieert van 0 tot 250 cm en hun leeftijd van 0 tot 120 jaar. Dan zijn er voor de combinatie van de drie 300•250•120 = 9 miljoen mogelijkheden. Maar het aantal mensen in Nederland is groter dan 9 miljoen!
Dus er zijn 9 miljoen 'gaten' (= combinaties lengte-gewicht-leeftijd) en meer dan 9 miljoen 'duiven' (= mensen). Het principe zegt dus dat er minstens twee mensen zijn die dezelfde combinatie hebben (= in hetzelfde gat moeten).

Oké, dat was een makkelijke. De volgende is ietsje lastiger:

"In een kamer met 2 of meer mensen zijn er altijd twee te vinden die hetzelfde aantal vrienden in die kamer hebben".

Het bewijs:

Ach, laten we de "Friends" zélf maar aan het woord laten:

In dit geval zijn dus de gaten de aantallen vrienden die mensen hebben, en de duiven de mensen zélf.

Bij elk veelvlak zijn er minstens twee vlakken met hetzelfde aantal zijden. Toon dat aan.

hint:

kies als gaten het aantal zijden van een vlak.

Kleur alle punten op een cirkel rood of blauw.
Dan bestaan er drie punten met gelijke tussenruimte van dezelfde kleur. Toon dat aan.

hint:

teken een regelmatige vijfhoek met de hoekpunten op de cirkel..

Kies 10 verschillende getallen kleiner dan 100.
Dan zijn er daarbinnen altijd twee groepjes te vinden die dezelfde som hebben. Toon dat aan.

hint:

kies als gaten de som van de 10 getallen.

Als je vijf roosterpunten met elkaar verbindt dan gaat er altijd minstens één verbindingslijn door een nieuw roosterpunt. Toon dat aan.

hint:

bekijk de coördinaten van de middens van de verbindingslijen.

Bij elke groep van N getallen zijn er altijd 2 te vinden zodat hun verschil deelbaar is door N-1.
Toon dat aan.

hint:

kies als gaten de rest bij delen door n - 1.

Als 25 mensen in een rij met 30 stoelen gaan zitten, zijn er minstens 5 stoelen naast elkaar bezet.
Toon dat aan.

hint:

5 lege stoelen verdelen de 30 in 6 groepen.

10 volleybalteams spelen een halve competitie. Geen enkel team verliest alles.
Bewijs dat er dan twee teams hetzelfde aantal partijen winnen.

hint:

kies als gaten het aantal winstpartijen.

De 20 leerlingen van een zelfde klas sturen in december elk 10 wenskaarten naar 10 verschillende klasgenoten. Toon aan dat er minstens 2 leerlingen zijn die een kaart naar elkaar sturen...

hint:

de gaten zijn de personenparen, de duiven zijn de brieven.