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, stwierdzające, iż jeżeli przedmiotów włoży się do różnych szufladek, gdzie oraz (), 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ą nietrudno 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.
  • 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. Wystarczy w tym celu 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