Dirichlets lådprincip

Tio duvor i nio postfack. Eftersom antalet duvor är högre än antalet fack säger principen att det måste finnas minst två duvor i något fack.

Dirichlets lådprincip, även kallad Postfacksprincipen eller duvslagsprincipen är ett resultat inom den diskreta matematiken och lyder som följer:

Om man har fler brev än postfack kommer något postfack att innehålla minst två brev, om man lägger varje brev i något av postfacken.

Även om detta kan låta närmast självklart visar det sig mycket kraftfullt i många sammanhang. Dirichlets lådprincip blandas ofta samman med Dirichlets princip, ett begrepp som infördes av Bernhard Riemann inom potentialteorin.

Den första formaliseringen av Dirichlets lådprincip tros ha gjorts av Peter Gustav Lejeune Dirichlet 1834.

Exempel

• Ett exempel där principen kan användas är om man vill undersöka huruvida det helt säkert finns tio svenskar som är lika långa på en mikrometer när.

Svaret är ja. Det finns cirka tio miljoner svenskar, och minst hälften av dessa, ungefär 5 000 000 personer, är helt säkert mellan 150 och 190 cm långa. Antalet mikrometerlånga intervall däremellan är 400 000, varför det alltså måste finnas minst ett mikrometerlångt intervall som delas av fler än 10 personer. (Här utnyttjas en trivial utvidgning av principen som säger att om det finns fler än n gånger så många objekt som fack, så innehåller något fack fler än n objekt.)

• Ett annat exempel där principen kan utnyttjas är då man vill visa att det bland n stycken heltal alltid går att finna två vars differens är delbar med talet n-1.

Genom att använda lådprincipen, och låta resterna vid division med talet n-1 utgöra lådorna, får man n-1 stycken lådor etiketterade med resterna 0, 1,..., n-2. Enligt lådprincipen kommer minst två av de n talen att hamna i samma låda, det vill säga ha samma rest vid division med talet n-1. Därmed är deras differens delbar med n-1.

Tag exempelvis de fyra primtalen 2,3,7 och 13. Här är n=4 och minst två av dessa tal skall ha en differens som är delbar med talet 3. Differensen mellan talen 7 och 13 är talet 6, vilket visar att Dirichlets lådprincip stämmer i detta exempel.

• Ett tredje exempel säger att det i varje enkel oriktad loopfri graf (varje kant går mellan två olika noder och mellan varje par av noder går högst en kant) finns minst två noder med samma grad. Hos grafer som består av n noder kan nodernas grad variera från noll till n-1, alltså anta n olika värden. Men att graden hos en nod är noll innebär att den inte är ansluten till någon annan nod och då kan inte samtidigt någon annan nod i grafen ha graden n-1, det vill säga vara ansluten till alla andra noder. Sålunda kan graden hos de n noderna hos en specifik graf högst anta n-1 olika värden och därför måste minst två noder ha samma grad.

Lådprincipen är, sitt namn till trots, i själva verket en matematisk sats.

Postfacksprincipen utgör startpunkten inom det område inom kombinatorik som går under namnet Ramseyteori.

Referenser

• Grimaldi, Ralph P. Discrete and Combinatorial Mathematics: An Applied Introduction. Fjärde upplagan 1998. ISBN 0-201-19912-2. sidor. 244–248.
• Jeff Miller, Peter Flor, Gunnar Berg, och Julio González Cabillón. "Pigeonhole principle".
• Edwin Kwek Swee Hee, Huang Meiizhuo, Koh Chan Swee och Heng Wee Kuan, River Valley High School. Applications of the Pigeonhole Principle 2003.