Zasada szufladkowa Dirichleta

Gołębi jest więcej niż skrzynek, wobec czego w jednej są dwa ptaki

Zasada szufladkowa Dirichleta – twierdzenie matematyczne, mówiące:

Jeżeli ${\displaystyle m}$ przedmiotów włoży się do ${\displaystyle n}$ różnych szufladek, gdzie ${\displaystyle m>n>0,}$ to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty^[1][2].

Formalna treść twierdzenia:

• jeżeli zbiór ${\displaystyle X=X_{1}\cup X_{2}\cup \dots \cup X_{k}}$ liczy ${\displaystyle n}$ elementów, gdzie ${\displaystyle n>k,}$ to któryś ze zbiorów ${\displaystyle X_{i}\ (i\in \{1,\dots ,k\})}$ musi zawierać co najmniej dwa elementy^[1].

Inna wersja formalna brzmi następująco:

• Jeżeli moc zbioru ${\displaystyle X}$ wynosi ${\displaystyle n,}$ a zbioru ${\displaystyle Y}$ – ${\displaystyle m}$ i ${\displaystyle n>m,}$ to nie istnieje funkcja różnowartościowa ze zbioru ${\displaystyle X}$ do zbioru ${\displaystyle Y}$^[1].

Wydaje się, że ta oczywista obserwacja nie może mieć poważnych zastosowań, ale jest dokładnie przeciwnie. Zasada szufladkowa bywa wykorzystywana w dowodach wielu głębokich twierdzeń matematycznych i często samo zauważenie, że można ją zastosować, jest kluczem do rozwiązania problemu^[1].

Sformułowanie zasady szufladkowej przypisuje się często Peterowi Dirichletowi w 1834 r., który nazwał ją Schubfachprinzip^[3]. Jednak w literaturze zasada ta pojawiała się znacznie wcześniej, pierwszy raz prawdopodobnie w książce Selectae propositiones in tota sparsim mathematica pulcherrimae z 1622 r. autorstwa francuskiego jezuity Jeana Leurechona^[3][4].

Uogólnienie na nieskończoność

Zasadę szufladkową Dirichleta można uogólnić na zbiory nieskończone. Brzmi ona wtedy następująco:

Jeśli zbiór ${\displaystyle X=X_{1}\cup X_{2}\cup \dots \cup X_{k}}$ ma nieskończenie wiele elementów, to któryś ze zbiorów ${\displaystyle X_{i}\ (i\in \{1,\dots ,k\})}$ jest nieskończony^[1].

Przykłady

• W oparciu o zasadę szufladkową łatwo wykazać, że wśród mieszkańców Warszawy co najmniej dwie osoby mają tę samą liczbę włosów na głowie. Można założyć, że liczba włosów na głowie człowieka nie przekracza 500 000; liczba mieszkańców Warszawy wynosi prawie dwa miliony. Weźmy 500 001 szufladek ponumerowanych kolejnymi liczbami naturalnymi od 0 do 500 000 i wkładajmy do szufladki o danym numerze osoby, które mają taką liczbę włosów na głowie, jak numer szufladki. Ponieważ osób jest ponad 1 760 000, a szufladek 500 001, z zasady szufladkowej Dirichleta wynika, że w jednej lub więcej szufladkach musi się znaleźć więcej niż jedna osoba.
• Analogicznie można wykazać, że w grupie 20 osób muszą być co najmniej dwie, które urodziły się w tym samym miesiącu. W tym celu wystarczy wziąć 12 szufladek z nazwami miesięcy i wkładać do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest 20, a szufladek 12, w nie mniej niż jednej z nich muszą być co najmniej dwie osoby.
• Aminokwasy tworzące białka są kodowane przez trójnukleotydowe kodony. Ponieważ są 4 rodzaje nukleotydów, więc liczba różnych trypletów jest równa ${\displaystyle 4^{3}=64}$. Tymczasem kodowanych aminokwasów jest jedynie 20–23. W efekcie większość aminokwasów jest kodowanych przez więcej niż jeden kodon (przy czym niektóre sekwencje trójnukleotydowe nie kodują żadnego aminokwasu). Jest tzw. degeneracja kodu genetycznego^[5].
• Zebranych jest ${\displaystyle N}$ osób ${\displaystyle (N\geqslant 2).}$ Być może niektórzy z nich mają wśród zebranych znajomych. Być może każdy ma wśród nich kogoś znajomego, a może żaden nie ma. Wśród tych ${\displaystyle N}$ osób są dwie osoby, które mają wśród zebranych tyle samo znajomych. Bardziej formalnie: w każdym grafie skończonym o co najmniej dwu węzłach istnieją dwa węzły o tym samym stopniu.
  Dla dowodu wystarczy zauważyć, że osób jest ${\displaystyle N,}$ a każda z tych osób może mieć wśród zebranych najwyżej ${\displaystyle N-1}$ znajomych.
• Jeśli pomalujemy płaszczyznę w dowolny sposób na dwa kolory: biały i czarny, tzn. przypiszemy każdemu punktowi płaszczyzny jeden z tych dwu kolorów, to istnieje prostokąt, który ma wszystkie wierzchołki tego samego koloru. Bardziej formalnie: jeśli ustalimy na płaszczyźnie dowolny zbiór ${\displaystyle B}$ oraz jego dopełnienie ${\displaystyle C=B',}$ to istnieje prostokąt, którego wszystkie wierzchołki należą do ${\displaystyle B,}$ albo taki, którego wszystkie wierzchołki należą do ${\displaystyle C.}$
  Dla dowodu wystarczy skonstruować dowolny prostokąt o wymiarach 2×8, który rozpada się na 16 kwadratowych segmentów o wymiarach 1×1. Każdy punkt płaszczyzny, który jest jakimś wierzchołkiem jakiegoś z tych kwadratów nazwijmy punktem kratowym. Każda trójka punktów kratowych leżących na odcinku równoległym do krótszego boku prostokąta może być pomalowana na ${\displaystyle 2^{3}=8}$ sposobów. Ponieważ takich trójek jest 9, więc któreś dwie trójki muszą być pomalowane w identyczny sposób. Wystarczy wybrać z jednej trójki dwa punkty kratowe o tym samym kolorze (na pewno takie istnieją) i odpowiadające im dwa punkty z drugiej trójki. Tak wybrane 4 punkty są wierzchołkami szukanego prostokąta.
• W oparciu o zasadę szufladkową można wykazać, że wśród kolejnych potęg liczby ${\displaystyle 7{:}\ 7^{1},\ 7^{2},\ 7^{3},\ 7^{4},\dots }$ istnieje taka, której zapis dziesiętny kończy się na 001.
  Dla dowodu wystarczy rozważyć reszty z dzielenia przez 1000 kolejnych liczb tej postaci: ${\displaystyle 7^{1},\ 7^{2},\ 7^{3},\ 7^{4},\dots ,\ 7^{1001}.}$ Trzeba wkładać do jednej szufladki dwie potęgi liczby 7 wtedy i tylko wtedy, gdy z dzielenia przez 1000 dają tę samą resztę – ponieważ różnych reszt jest co najwyżej 1000 (mogą to być liczby 0,1,2,...,999), a potęg liczby 7 jest 1001, co najmniej dwie potęgi muszą znaleźć się w tej samej szufladce, co oznacza, że ich różnica jest podzielna przez 1000. Niech będą to liczby ${\displaystyle 7^{k}}$ i ${\displaystyle 7^{l},}$ gdzie ${\displaystyle k>l}$ – ich różnica jest równa ${\displaystyle 7^{k}-7^{l}=7^{l}(7^{k-l}-1)}$ i dzieli się przez 1000. Liczba ${\displaystyle 7^{l}}$ oraz 1000 nie mają wspólnych dzielników większych od 1(tzn. są względnie pierwsze), a zatem musi przez 1000 dzielić się liczba ${\displaystyle 7^{k-l}-1.}$ Oznacza to, że jej zapis dziesiętny kończy się co najmniej trzema zerami: ${\displaystyle 7^{k-l}-1=\dots 000,}$ a stąd natychmiast mamy, że ${\displaystyle 7^{k-l}=\dots 000+1=\dots 001.}$

Przypisy

Bibliografia

• Kazimierz Kuratowski, Andrzej Mostowski: Teoria mnogości wraz ze wstępem do opisowej teorii mnogości. Warszawa: Państwowe Wydawnictwo Naukowe, 1978, seria: Monografie Matematyczne tom 27., s. 113–115.
• K. Cegiełka, E. Stachowski, K. Szymański: Encyklopedia dla wszystkich. Matematyka. Warszawa: Wydawnictwa Naukowo-Techniczne, 2000. ISBN 83-204-2334-1., s. 213.

Linki zewnętrzne

• WiktorW. Bartol WiktorW., Szuflady pana Dirichleta, [w:] pismo „Delta” [online], deltami.edu.pl, sierpień 2004, ISSN 0137-3005 [dostęp 2022-07-20]  (pol.).
• Eric W.E.W. Weisstein Eric W.E.W., Dirichlet's Box Principle, [w:] MathWorld [online], Wolfram Research [dostęp 2020-12-12]  (ang.).