Dirichlets lådprincip
Wikipedia
"Princip" inom den diskreta matematiken, även kallad brevlådeprincipen, vilken utsäger att
Om m föremål ska placeras i n lådor, och m > n, så kommer minst en låda att innehålla mer en ett föremål.
Detta låter ju närmast självklart, men visar sig mycket kraftfullt i många sammanhang. Eng: "The Pigeonhole Principle".
Exempel
Visa att bland n heltal finns alltid 2 vars differens är delbar med n-1.
Använd lådprincipen (så klart). Låt resten när man delar ett tal med (n-1) vara lådorna. Vi får då (n-1) lådor (med resterna 0, 1,..., n-2). Enligt lådprincipen kommer då (minst) två tal ha samma rest om man delar med (n-1). Därmed är deras differens delbar med n-1. Vi kan alltså alltid finna två tal bland n heltal vars differens är delbar med n-1. Detta förutsatt att vi anser att talet 0 är delbart med (n-1), två tal kan ju vara lika och då är deras differens 0.
Finns det helt säkert tio svenskar som är lika långa på en mikrometer när?
Ja. Det finns ca 9 miljoner svenskar. Minst hälften av dessa, ca 4500000 personer, är helt säkert mellan 150 och 190 cm långa. Antalet mikrometerlånga intervall däremellan är 400000. Det måste alltså finnas minst ett mikrometerlångt intervall inom vilket det finns fler än 10 personer vars längd ligger i detta intervall.
Lådprincipen är, sitt namn till trots, i själva verket ett matematiskt teorem.
