Dirichlets lådprincip

Från Rilpedia

Texten från svenska Wikipedia

Inspirationen för namnet på principen: duvor i duvbon. Här är n = 7 och m = 9 vilken ger att det måste finnas åtminstone två tomma duvbon.

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, så kommer något postfack att innehålla minst två brev.

Även om detta kan låta närmast självklart visar det sig mycket kraftfullt i många sammanhang.

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.

Svaret är ja. Det finns cirka nio miljoner svenskar, och minst hälften av dessa, ungefär 4 500 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.

• 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.

Lådprincipen är, sitt namn till trots, i själva verket ett matematiskt teorem.

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.

Externa länkar

• Ett bevis för lådprincipen

 Denna artikel om kombinatorik eller diskret matematik är bara påbörjad. Du kan hjälpa till genom att utöka den.