Zasada szufladkowa Dirichleta

Z Wikipedii

Niniejszy artykuł jest częścią cyklu kombinatoryka.

permutacja kombinacja bez powtórzeń kombinacja z powtórzeniami wariacja bez powtórzeń wariacja z powtórzeniami liczby Stirlinga liczby Bella liczby Eulera zasada szufladkowa Dirichleta zasada włączeń i wyłączeń

edytuj ten szablon

Zasada szufladkowa Dirichleta – twierdzenie mówiące, że jeżeli m przedmiotów włożymy do n różnych szufladek, przy czym m > n, to co najmniej w jednej szufladce znajdą się co najmniej dwa przedmioty.

Sformułowanie twierdzenia przypisuje się Dirichletowi, a w bardziej formalnym języku można wysłowić je na przykład tak:

• jeżeli zbiór X liczy n elementów i i n > k, to któryś ze zbiorów X_i musi liczyć przynajmniej dwa elementy.

Inna wersja formalna brzmi następująco:

• Jeżeli zbiór X liczy n elementów, zbiór Y – m elementów i n > m, to nie istnieje funkcja różnowartościowa ze zbioru X do zbioru y.

Wydaje się, że ta oczywista obserwacja nie może mieć poważnych zastosowań, ale jest akurat odwrotnie. Zasada szufladkowa 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.

[edytuj] Przykłady

• 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. Rzeczywiście, liczba włosów na głowie człowieka nie przekracza 500 000, natomiast liczba mieszkańców Warszawy przekracza 1 000 000. 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 1 000 000, a szufladek 500 000, z naszej zasady wynika, że w jednej szufladce muszą znaleźć się co najmniej dwie osoby (a nawet co najmniej trzy).
• 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. Weźmy mianowicie 12 szufladek z nazwami miesięcy i wkładajmy do nich osoby, które urodziły się w danym miesiącu. Ponieważ osób jest 20, a szufladek 12, w jednej z nich muszą być co najmniej dwie osoby.
• Następny przykład dotyczy spraw nieco "poważniejszych" – w oparciu o zasadę szufladkową uzasadnimy, że wśród kolejnych potęg liczby 7: 7, 7², 7³, 7⁴, ... istnieje taka, której zapis dziesiętny kończy się na 001.

Rozważmy mianowicie 1000 kolejnych liczb tej postaci: 7, 7², 7³, 7⁴, ..., 7¹⁰⁰⁰ i przyjrzyjmy się ich resztom z dzielenia przez 1000. Żadna z reszt nie jest równa 0 (bo żadna z wypisanych liczb nie dzieli się przez 1000). Wkładajmy do jednej szufladki dwie liczby wtedy i tylko wtedy, gdy z dzielenia przez 1000 dają tę samą resztę – ponieważ różnych reszt jest co najwyżej 999, a liczb 1000, co najmniej dwie liczby muszą znaleźć się w tej samej szufladce, co oznacza, że ich różnica jest podzielna przez 1000. Zatem ich różnica jest podzielna przez 1000. Niech będą to liczby 7^k i 7^l, gdzie k > l – ich różnica jest równa 7^k − 7^l = 7^l(7^{k − l} − 1) i dzieli się przez 1000. Liczba 7^l przez 1000 się nie dzieli, a zatem musi przez 1000 dzielić się liczba 7^{k − l} − 1. Oznacza to, że jej zapis dziesiętny kończy się co najmniej trzema zerami: , a stąd natychmiast mamy, że .

I jeszcze dwa przykłady.

• Pomalujmy płaszczyznę w dowolny sposób na dwa kolory: biały i czarny. To znaczy przypiszmy każdemu punktowi płaszczyzny jeden z tych dwu kolorów. Na takiej płaszczyźnie istnieje prostokąt, który ma wszystkie wierzchołki tego samego koloru. Bardziej formalnie: wyznaczmy na płaszczyźnie dowolny zbiór B oraz jego dopełnienie C=B′; istnieje prostokąt, którego wszystkie wierzchołki należą do B, albo taki, którego wszystkie wierzchołki należą do C.
• Zbierzmy 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.