Skuffeprinsippet

Skuffeprinsippet, eller Dirichlets skuffeprinsipp er et prinsipp i matematikk som ofte brukes i kombinatoriske argumenter. Det sier at hvis man skal legge et visst antall objekter i et visst antall skuffer, og man har flere objekter enn skuffer, så må minst én skuff inneholde minst to objekter. Man antar at prinsippet først ble formulert av Dirichlet i 1834. Prinsippet er i Norge også kjent under sitt engelske navn, pigeonhole principle, eller ved fornorskningen duehullprinsippet. Det engelske ordet pigeonhole har imidlertid en videre betydning enn duehull; det kan for eksempel bety brevhylle, men brukes også som bås i uttrykket sette i bås.

Matematisk formulering

Forklaringen ovenfor er uformell. Matematisk kan man uttrykke det mer formelt på denne måten: La $f$ være en funksjon fra mengden $X$ til mengden $Y$. Hvis $|X|>|Y|$ (det vil si at $X$ har større kardinalitet enn $Y$, eller at $X$ har flere elementer enn $Y$) så kan ikke $f$ være injektiv.

Denne formuleringen er også riktig om man lar $X$, og eventuelt $Y$, ha uendelig mange elementer.

Eksempler

Til tross for at prinsippet virker nærmest trivielt, kan det ofte brukes til å bevise andre utsagn som ikke er like åpenbare. Her er et par eksempler:

• Det finnes to nordmenn med like mange hår på hodet. For å ikke gjøre det trivielt, kan vi se bort fra folk som er skallede, så vi kan heller si: «Det finnes to nordmenn med mer enn 50 000 hodehår som har det samme antallet hår på hodet.» Typisk har mennesker mellom 100 000 og 200 000 hodehår, og det er nokså sikkert ingen som har mer enn én million hår. Hvis vi i tillegg antar at minst halvparten av befolkningen har mer enn 50 000 hår, og vi vet at det finnes mer enn fire millioner nordmenn, så betyr det at det finnes minst to millioner nordmenn med mellom 50 000 og én million hår. Med andre ord kan vi tenke oss at to millioner nordmenn skal fordeles på 950 000 skuffer, noe som ikke er mulig med mindre en skuff inneholder mer enn én nordmann. Altså finnes det to personer med det samme antallet hodehår.
• Anta at det er $n$ personer i et rom, hvor noen har håndhilst på hverandre, mens andre ikke har det. Da må det finnes to personer i rommet som har håndhilst like mange ganger, forutsatt at ingen har håndhilst mer enn én gang på den samme personen. For å se at dette stemmer, kan man først legge merke til at hver person har håndhilst mellom 0 og $n-1$ ganger: dette gir $n$ forskjellige muligheter. Men hvis det finnes en som har håndhilst $n-1$ ganger, må han ha håndhilst på alle de andre, og da kan det ikke finnes noen som har håndhilst 0 ganger. Hvis man sorterer personene i «skuffer» etter hvor mange ganger de har håndhilst, kan de bare fordeles på $n-1$ skuffer, siden enten skuffen for 0 håndtrykk eller skuffen for $n-1$ håndtrykk må være tom. Siden $n$ personer skal fordeles på $n-1$ skuffer, må minst én skuff inneholde to personer. Disse to personene har da håndhilst like mange ganger.

Generalisering

En generalisering av skuffeprinsippet lyder: Hvis $n$ objekter skal legges i $m$ skuffer, så må minst én skuff inneholde minst $\lceil n/m\rceil$ objekter. Her betegner $\lceil x\rceil$ det minste heltallet som er større enn eller lik $x$.

Se også

• Ramsey-teori