Stel je tien duiven voor die in je zelfgemaakte duivenhok vliegen, maar je hebt er slechts 9 gemaakt. Waar gaat de laatste duif heen? Wat is het verhaal achter het hele duivenhokprincipe?

Aangezien de bevolking van Londen het maximale aantal haren op een menselijk hoofd overschrijdt, vereist het duivenhokprincipe dat ten minste twee personen in Londen hetzelfde aantal haren op hun hoofd hebben. Dit wiskundige principe bestaat sinds 1624.

Het duivenhokprincipe

Het duivenhokprincipe is een van de meest basale maar waardevolle concepten in de wiskunde. Het is al gedocumenteerd vanaf 1624. Het staat ook bekend als het doosprincipe van Dirichlet of het ladeprincipe van Dirichlet. (Bron: Jeff 560)

In de eenvoudigste uitleg bepaalt het principe dat als tien duiven naar negen duivenhokken gaan, ten minste één van de duivenhokken meer dan één duif zal bevatten.

In de stelling: als X het gemiddelde aantal duiven per hok is, waarbij X geen geheel getal is, dan bevat ten minste één duivenhok het maximaal toegestane aantal duiven, en de overige duivenhokken zullen waarschijnlijk het minste aantal duiven hebben. (Bron: Geeks For Geeks)

Om verder uit te leggen, als n plus één object in n containers worden geplaatst, dan zal ten minste één container twee of meer dingen bevatten. Het duivenhokprincipe wordt gebruikt om aan te tonen dat resultaten geldig moeten zijn omdat ze ‘te groot om te falen’ zijn. Dit betekent dat ten minste twee objecten een eigenschap hebben of delen voor elk aanzienlijk aantal dingen met een limiet of een specifiek aantal eigenschappen. En de toepassingen van dit principe zijn interessant, verrassend en tot nadenken stemmend. (bron: Stanford)

Enkele voorbeelden van het principe

Het eerste voorbeeld, zoals hierboven vermeld, toont het duivenhokprincipe als volgt: de bevolking van Londen, exclusief kale mensen, bedraagt ongeveer 7,5 miljoen. Het maximale aantal haren bij een gemiddeld persoon is ongeveer 150.000. Het principe zou bepalen dat ongeveer 50 mensen hetzelfde aantal haren hebben. (Bron: Maths Careers)

Stel vervolgens dat twee of meer mensen dit artikel lezen die dezelfde verjaardag hebben. Het principe stelt dat er 366 mogelijke verjaardagen zijn in een schrikkeljaar. Dit artikel heeft meer dan 367 lezers. Daarom hebben twee van jullie lezers dezelfde verjaardag.

Een ander voorbeeld zou zijn een stapel gewone speelkaarten. Als iemand vijf kaarten kiest uit de 52 kaarten in een standaard spel kaarten, zullen ten minste twee van die vijf kaarten dezelfde kleur hebben. Ter verduidelijking, er zijn vier kleuren in een standaard spel kaarten – klaveren, schoppen, harten en ruiten. Elke van de vijf kaarten moet tot een van de vier kleuren behoren. Het volgt dus dat twee van die kaarten dezelfde kleur hebben. (Bron: Mind Your Decisions) 

Is er een praktische toepassing voor dit principe?

Het duifhokprincipe helpt bij het bewijzen van verliesloze compressie die wordt gebruikt in de datawetenschappen. Datacompressie is de theorie waarbij echte gegevens kunnen worden gecomprimeerd door simpelweg redundantie weg te laten.

Dit is een cruciale theorie die in de wereld van vandaag wordt gebruikt in de vorm van gegevensoverdracht, of de informatie nu via het netwerk, dvd’s, USB‑sticks of e‑mails wordt overgebracht, om er maar een paar te noemen.

Het idee van verliesloze compressie is om elke bitreeks van informatie te vervangen door een kortere bitreeks. Echter, zodra de kortere bitreeks wordt gedecomprimeerd, zal deze nog steeds de ongewijzigde informatie van de oorspronkelijke bitreeks onthullen. (Bron: Stanford)

Het duifhokprincipe bewijst verliesloze compressie waarbij het alleen mogelijk is om sterk repetitieve data te comprimeren, waarbij twee “duiven”, stukjes data, één “duivenhok” of plaats in de bitreeks innemen. (Bron: Stanford)