Dirichlets skuffeprincip

Fra Wikipedia, den frie encyklopædi
Gå til: navigation, søg

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[redigér | redigér wikikode]

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[redigér | redigér wikikode]

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.

Dirichlets skuffeprincip

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[redigér | redigér wikikode]