Zasada szufladkowa Dirichleta

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj
Niniejszy artykuł jest częścią cyklu kombinatoryka.




permutacja bez powtórzeń
permutacja z powtórzeniami


kombinacja bez powtórzeń
kombinacja z powtórzeniami


wariacja bez powtórzeń
wariacja z powtórzeniami


liczby Bella
liczby Catalana
liczby Stirlinga
liczby Eulera


zasada szufladkowa Dirichleta
zasada włączeń i wyłączeń


Zasada szufladkowa Dirichleta – twierdzenie matematyczne, którego sformułowanie przypisuje się Dirichletowi:

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

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

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 000 szufladek ponumerowanych kolejnymi liczbami naturalnymi od 1 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 000 000, a szufladek 500 000, 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.
  • Niektóre aminokwasy są kodowane przez różne triplety (jest tzw. degeneracja kodu genetycznego ). Wynika to stąd, że triplet zawiera 3 nukleotydy, których są 4 rodzaj, więc liczba różnych tripletów jest równa 4^3=64. Tymczasem kodowanych aminokwasów jest mniej niż 30.
  • Jeśli zbierzemy razem N osób (N≥2). Być może niektórzy z nich mają wśród zebranych znajomych. Być może każdy ma w niej kogoś znajomego; a może żaden nie ma. Wśród tych 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 N, a każda z tych osób może mieć wśród zebranych najwyżej 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 B oraz jego dopełnienie C=B′, to istnieje prostokąt, którego wszystkie wierzchołki należą do B, albo taki, którego wszystkie wierzchołki należą do 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 23=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 7: 71, 72, 73, 74, ... 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: 71, 72, 73, 74, ..., 71001. 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 7k i 7l, 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

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

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. str. 113-115
  • K. Cegiełka, E. Stachowski, K. Szymański: Encyklopedia dla wszystkich. Matematyka. Warszawa: Wydawnictwo Naukowo-Techniczne, 2000. ISBN 83-204-2334-1. str. 213