Dirichlets skuffeprincip: Forskelle mellem versioner

Content deleted Content added
uddyber forklaring på eksempel
mNo edit summary
Linje 7:
[[Billede:Skuffe princip 001.PNG]]
 
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 [[Grafteori|grafteoretisk]] problem, som løser det resultat der angiver, at i en hvilken som helst graf findes der altid to knuder med samme [[Valens (grafteori)|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.