Dirichlets skuffeprincip

Denne side virker ikke som en encyklopædisk artikel Du kan se hvad Wikipedia er og ikke er og hjælpe ved at omskrive den til en konkret og dokumenteret beskrivelse af fakta.

Dirichlets skuffeprincip eller Dueslagsprincippet (eng. The pigeonhole principle) er et kombinatorisk begreb, der anvendes til løsning af mange kombinatoriske problemer, hvor observationen ofte anvendes i forklædning. Princippet drejer sig om det velkendte forhold, der går ud på, at der, hvis man fordeler et antal objekter i skuffer, med flere objekter end der er skuffer, må gælde, at mindst en af skufferne indeholder mere end et objekt. Udtrykt generelt: Hvis ${\displaystyle p}$ genstande optager ${\displaystyle q}$ rum, og ${\displaystyle p}$ er større end ${\displaystyle q}$, så indeholder i det mindste ét rum mere end én genstand. Begrebet er opkaldt efter den tyske matematiker Johann Peter Gustav Lejeune Dirichlet.

Generalisering

En mere generel sætning siger, at hvis man har p genstande og q rum, så er der et rum med mindst ${\displaystyle \left\lceil {\frac {p}{q}}\right\rceil }$ genstande, hvor ${\displaystyle \lceil k\rceil }$ betegner det mindste heltal større end eller lig ${\displaystyle k}$. Dette kan simpelt bevises ved at antage en fordeling af ${\displaystyle p}$ genstande i ${\displaystyle q}$ rum, hvor intet rum indeholder ${\displaystyle \left\lceil {\frac {p}{q}}\right\rceil }$ eller flere genstande. Hvis vi nummerer rummene med ${\displaystyle 1,2,3,...,q}$ og betegner antallet af genstande i rum nummer ${\displaystyle k}$ med ${\displaystyle x_{k}}$, så ved vi, at der gælder

${\displaystyle x_{1}+x_{2}+x_{3}+\cdots +x_{q}=p,}$

men idet der for alle ${\displaystyle x_{k}}$ gælder ${\displaystyle x_{k}\leq \left\lceil {\frac {p}{q}}\right\rceil -1}$, så får vi følgende ulighed:

${\displaystyle x_{1}+x_{2}+x_{3}+\cdots +x_{q}\leq q\cdot \left(\left\lceil {\frac {p}{q}}\right\rceil -1\right)}$

Idet ${\displaystyle \left\lceil {\frac {p}{q}}\right\rceil <{\frac {p}{q}}+1}$, så gælder

${\displaystyle q\cdot \left(\left\lceil {\frac {p}{q}}\right\rceil -1\right)<q\cdot \left(\left({\frac {p}{q}}+1\right)-1\right)=p}$

Dermed har vi opnået en modstrid i forhold til den første ligning ved

${\displaystyle x_{1}+x_{2}+x_{3}+\cdots +x_{q}<p,}$

Q.E.D.

Eksempel på anvendelse

Antag at en gruppe med n personer (f.eks. til en fest) beslutter sig at hilse på hinanden ved at give hånd, således at ingen person giver hånd til sig selv og der findes ikke nogen par som hilser på hinanden mere end en gang. Vi ønsker at vise at der må være to personer som har givet samme antal hånd. Vi løser problemet ved at oprette n skuffer og numerere dem fra 0 til n-1.

Vi beder derefter personerne skrive deres navn på en seddel og lægge seddelen i den skuffe, der svarer til antallet af hænder personen har givet. For at vise at der må være to personer som har givet samme antal hånd, så må vi vise, at en af skufferne indeholder mere end en seddel. Antag at Paul Nielsen har lagt sin seddel i skuffe nr. 0, og Louise Petersen har lagt sin seddel i skuffe nr. n-1. Dette betyder at Paul har ikke hilst på nogen, hvorimod Louise har hilst på alle (inklusive Paul); hvilket er umuligt. Derved kan ikke både skuffe nr. 0 og skuffe nr. n-1 være udfyldt (sand). Deraf følger at n personer bliver placeret i n-1 skuffer, så mindst en skuffe må indeholde sedler fra to personer.

Dette problem kan nemt oversættes til et grafteoretisk problem, der i dette tilfælde angiver, at i en hvilken som helst graf findes der altid to knuder med samme valens. Lader man nemlig knuderne i grafen repræsentere personerne, hvor en direkte forbindelse mellem to knuder (via en kant) svarer til en hånd; da vil antallet af hænder en person har givet være ækvivalent med valensen for den pågældende knude.

Referencer

Der mangler kildehenvisninger i teksten Denne artikel har en liste med kilder, en litteraturliste eller eksterne henvisninger, men informationerne i artiklen er ikke underbygget, fordi kildehenvisninger ikke er indsat i teksten. Du kan hjælpe ved at indføre præcise kildehenvisninger på passende steder.

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. 4th edn. 1998. ISBN 0-201-19912-2. pp. 244–248.
• Jeff Miller, Peter Flor, Gunnar Berg, and Julio González Cabillón. "Pigeonhole principle Arkiveret 12. februar 2010 hos Wayback Machine". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics Arkiveret 4. marts 2009 hos Wayback Machine. Electronic document, retrieved November 11, 2006.