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  være en funksjon fra mengden  til mengden . Hvis  (det vil si at  har større kardinalitet enn , eller at  har flere elementer enn ) så kan ikke  være injektiv.

Denne formuleringen er også riktig om man lar , og eventuelt , 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  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  ganger: dette gir  forskjellige muligheter. Men hvis det finnes en som har håndhilst  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å  skuffer, siden enten skuffen for 0 håndtrykk eller skuffen for  håndtrykk må være tom. Siden  personer skal fordeles på  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  objekter skal legges i  skuffer, så må minst én skuff inneholde minst  objekter. Her betegner  det minste heltallet som er større enn eller lik .

 Se også 
 Ramsey-teori

Kategori:Kombinatorikk