Dirichlets skuffeprincip

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 $p$ genstande optager $q$ rum, og $p$ er større end $q$, så indeholder i det mindste ét rum mere end én genstand.

Generalisering

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

$x_1+x_2+x_3+\cdots+x_q=p,$

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

$x_1+x_2+x_3+\cdots+x_q\leq q\cdot \left( \left\lceil \frac{p}{q} \right\rceil-1 \right)$

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

$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

$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, som løser det resultat der 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 gviet være ækvivalent med valensen for den pågældende knude.

Referencer

• 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". In Jeff Miller (ed.) Earliest Known Uses of Some of the Words of Mathematics. Electronic document, retrieved November 11, 2006.