Dirichlets skuffeprincip

Fra Wikipedia, den frie encyklopædi

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.

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