Home » Wetenschap » Wiskunde » Wat is het Pigeonhole-principe?

Wat is het Pigeonhole-principe?

Stel je voor dat tien duiven in je zelfgemaakte hokje vliegen, maar je hebt er maar 9 gemaakt. Waar gaat de laatste duif heen? Wat is het verhaal achter het geheel? Duivengat principe?

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

Het duivengatprincipe

Het duivenhokprincipe is een van de meest elementaire maar waardevolle concepten van de wiskunde. Het is al in 1624 geregistreerd. Het is algemeen bekend als het doosprincipe van Dirichlet of het ladeprincipe van Dirichlet. (Bron: Jef 560)

In zijn eenvoudigste verklaring dicteert het principe dat als tien duiven samenkomen in negen hokjes, ten minste één van de hokjes meer dan één duif zou hebben. 

Stelling: als X het gemiddelde aantal duiven per hok is, waarbij X geen geheel getal is, dan bevat ten minste één hokje het maximaal toegestane aantal duiven, en de overige hokjes hebben hoogstwaarschijnlijk het minste aantal duiven. (Bron: Geeks voor 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 Pigeonhole-principe wordt gebruikt om aan te tonen dat resultaten geldig moeten zijn omdat ze "too big to fail" zijn. Dit betekent dat ten minste twee objecten een eigenschap hebben of delen voor een aanzienlijk aantal dingen met een gebonden of een specifiek aantal eigenschappen. En de toepassingen voor dit principe zijn interessant, verrassend en tot nadenken stemmend. (bron: Stanford)

Enkele voorbeelden van het principe

Het eerste voorbeeld, zoals hierboven vermeld, demonstreert het Pigeonhole-principe als zodanig: de bevolking van Londen, uitgezonderd kale mensen, bedraagt ​​ongeveer 7.5 miljoen. Het maximale aantal haren in een gemiddelde persoon is ongeveer 150,000. Het principe zou dicteren dat ongeveer 50 mensen hetzelfde aantal strengen zouden hebben. (Bron: Wiskunde Carrières)

Laten we vervolgens zeggen dat twee of meer mensen dit artikel lezen die op dezelfde dag jarig zijn. Het principe zal stellen dat er 366 mogelijke verjaardagen zijn in een schrikkeljaar. Dit artikel heeft meer dan 367 lezers. Daarom zijn twee van jullie lezers op dezelfde dag jarig.

Een ander voorbeeld zou zijn wanneer een pak gewone speelkaarten. Als een persoon vijf kaarten kiest uit de 52 kaarten in een standaardspel speelkaarten, zullen ten minste twee van die vijf kaarten dezelfde reeks hebben. Door uitleg, zijn er vier kleuren in een gewoon spel kaarten - kruidnagel, schoppen, harten en ruiten. Elk van de vijf kaarten moet tot een van de vier kleuren behoren. Hieruit volgt dat twee van die kaarten dezelfde kleur hebben. (Bron: Let op je beslissingen

Is er een praktische toepassing voor dit principe?

Het duivenhokprincipe helpt bij het bewijzen van de Lossless Compression die in Data Sciences wordt gebruikt. Gegevenscompressie is de theorie waarin gegevens uit de echte wereld kunnen worden gecomprimeerd door eenvoudigweg redundanties weg te laten.

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

Het idee van Lossless Compression is om elke bitstring van informatie te vervangen door een kortere bitstring. Zodra de kortere bitstring echter is gedecomprimeerd, zal deze nog steeds de intacte informatie van de originele bitstring onthullen. (Bron: Stanford)


Het duivengatprincipe bewijst Lossless Compression waarbij het alleen mogelijk is om zeer repetitieve gegevens te comprimeren, waarbij twee "duiven", stukjes gegevens, één "pigeonhole" of plaats in de bitstring innemen. (Bron: Stanford)

Laat een bericht achter