Zasada szufladkowa Dirichleta

twierdzenie kombinatoryki

Zasada szufladkowa Dirichletatwierdzenie matematyczne, mówiące:

Gołębi jest więcej niż skrzynek, wobec czego w jednej są dwa ptaki
Jeżeli przedmiotów włoży się do różnych szufladek, gdzie to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty[1][2].

Formalna treść twierdzenia:

  • jeżeli zbiór liczy elementów, gdzie to któryś ze zbiorów musi zawierać co najmniej dwa elementy[1].

Inna wersja formalna brzmi następująco:

  • Jeżeli moc zbioru wynosi a zbioru i to nie istnieje funkcja różnowartościowa ze zbioru do zbioru [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ść

edytuj

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

Jeśli zbiór   ma nieskończenie wiele elementów, to któryś ze zbiorów   jest nieskończony[1].

Przykłady

edytuj
  • 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   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   osób   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   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   a każda z tych osób może mieć wśród zebranych najwyżej   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   oraz jego dopełnienie   to istnieje prostokąt, którego wszystkie wierzchołki należą do   albo taki, którego wszystkie wierzchołki należą do  
    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   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   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:   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   i   gdzie   – ich różnica jest równa   i dzieli się przez 1000. Liczba   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   Oznacza to, że jej zapis dziesiętny kończy się co najmniej trzema zerami:   a stąd natychmiast mamy, że  

Przypisy

edytuj
  1. a b c d e Wojciech Kryszewski: Wykład analizy matematycznej. T. 1: Funkcje jednej zmiennej. Wydawnictwo Naukowe Uniwersytetu Mikołaja Kopernika, 2014, s. 67. ISBN 83-231-2352-7.
  2. Dirichleta zasada szufladkowa, [w:] Encyklopedia PWN [online], Wydawnictwo Naukowe PWN [dostęp 2022-07-20].
  3. a b Benoît Rittaud, Albrecht Heeffer, The Pigeonhole Principle, Two Centuries Before Dirichlet, „The Mathematical Intelligencer”, 36 (2), 2014, s. 27–29, DOI10.1007/s00283-013-9389-1 [dostęp 2022-06-06] (ang.).
  4. Jean Leurechon, Selectae propositiones in tota sparsim mathematica pulcherrimae, Sebastianum Cramoisy, 1622, s. 2, DOI10.3931/e-rara-10537 (łac.).
  5. Lubert Stryer, Przepływ informacji genetycznej, [w:] Biochemia, wyd. 1, Warszawa: PWN, 1986, s. 96–120, ISBN 83-01-00140-2.

Bibliografia

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

edytuj