Zasada szufladkowa Dirichleta

Q: Czy zasada mówi, w której szufladzie są dwa przedmioty?

Nie. Gwarantuje jedynie istnienie takiej szuflady. To dowód niekonstruktywny - wiemy, że coś istnieje, choć nie potrafimy tego wskazać.

Q: Czym różni się wersja uogólniona od podstawowej?

Podstawowa daje wniosek „co najmniej dwa" i wymaga n + 1 przedmiotów w n szufladach. Uogólniona działa dla dowolnych liczb i mówi, ile dokładnie przedmiotów musi się spotkać: lceil n/k rceil.

Q: Jak rozpoznać zadanie na zasadę szufladkową?

Zwykle po sformułowaniu „wykaż, że istnieją dwa...", „zawsze znajdą się...", „co najmniej dwa obiekty mają wspólną cechę". Trzeba wtedy zapytać: co jest przedmiotem, a co szufladą?

Q: Czy zasada działa dla zbiorów nieskończonych?

Podstawowa wersja dotyczy zbiorów skończonych. Dla nieskończonych obowiązuje jej odpowiednik: jeśli nieskończenie wiele przedmiotów rozmieścimy w skończenie wielu szufladach, to w którejś będzie ich nieskończenie wiele.

Q: Dlaczego coś tak oczywistego nazywa się twierdzeniem?

Bo mimo trywialnej treści wymaga dowodu i pozwala udowadniać rzeczy zupełnie nieoczywiste - jak przykład z włosami czy z punktami w kwadracie. W matematyce siła narzędzia nie zależy od jego skomplikowania.

Zasada szufladkowa

Jeśli $n + 1$ przedmiotów rozmieścimy w $n$ szufladach, to w pewnej szufladzie znajdą się co najmniej dwa przedmioty.

Wersja uogólniona: jeśli $n$ przedmiotów rozmieścimy w $k$ szufladach, to w pewnej szufladzie znajdzie się co najmniej

$\left\lceil \frac{n}{k} \right\rceil$

przedmiotów.

Co mówi zasada

To najbardziej oczywiste twierdzenie w matematyce - i jednocześnie jedno z najbardziej zaskakujących w skutkach. Jeśli masz $11$ par skarpetek i $10$ szuflad, to gdziekolwiek je włożysz, w którejś szufladzie będą co najmniej dwie pary. Nie da się inaczej.

Cała sztuka polega na tym, żeby w konkretnym zadaniu dostrzec, co jest przedmiotem, a co szufladą. Sama zasada nie mówi, w której szufladzie leżą dwa przedmioty ani jak je znaleźć - gwarantuje tylko, że taka szuflada istnieje. To typowy dowód niekonstruktywny.

Dowód

Pokaż dowódUkryj dowód

Krok 1. Zakładamy nie wprost, że w każdej szufladzie leży co najwyżej jeden przedmiot.

Krok 2. Liczymy przedmioty. Szuflad jest $n$ , w każdej co najwyżej jeden przedmiot, więc łącznie mamy co najwyżej

$\underbrace{1 + 1 + \ldots + 1}_{n \text{ składników}} = n$

przedmiotów.

Krok 3. Sprzeczność. Przedmiotów jest $n + 1$ , a naliczyliśmy co najwyżej $n$ . Założenie z kroku 1 musi być fałszywe - w pewnej szufladzie są co najmniej dwa przedmioty. $\blacksquare$

Wersja uogólniona dowodzi się tak samo: gdyby w każdej z $k$ szuflad było co najwyżej $\lceil n/k \rceil - 1$ przedmiotów, to razem byłoby ich co najwyżej

$k \cdot \left( \left\lceil \frac{n}{k} \right\rceil - 1 \right) < k \cdot \frac{n}{k} = n,$

czyli mniej niż $n$ - sprzeczność.

Przykład 1 - miesiące urodzenia

W dowolnej grupie $13$ osób są dwie urodzone w tym samym miesiącu.

Przedmioty to osoby ( $13$ ), szuflady to miesiące ( $12$ ). Skoro osób jest więcej niż miesięcy, któryś miesiąc powtórzy się co najmniej dwa razy.

Zauważ, że dla $12$ osób twierdzenie przestaje być prawdziwe - mogłyby urodzić się w dwunastu różnych miesiącach. Liczba $13$ jest tu najmniejszą, która działa.

Przykład 2 - włosy mieszkańców Warszawy

W Warszawie żyją dwie osoby o dokładnie tej samej liczbie włosów na głowie.

Brzmi jak zagadka detektywistyczna, a jest prostym rachunkiem:

człowiek ma na głowie najwyżej około $200\,000$ włosów (typowo $100$ - $150$ tysięcy);
Warszawa liczy około $1\,860\,000$ mieszkańców.

Szufladami są możliwe liczby włosów: $0, 1, 2, \ldots, 200\,000$ , czyli $200\,001$ szuflad. Przedmiotów (mieszkańców) jest prawie dziesięć razy więcej. Z wersji uogólnionej dostajemy nawet mocniejszy wniosek: istnieje liczba włosów wspólna dla co najmniej

$\left\lceil \frac{1\,860\,000}{200\,001} \right\rceil = 10$

mieszkańców.

Nie wiemy, kim są ci ludzie ani ile mają włosów - a mimo to wiemy na pewno, że istnieją.

Przykład 3 - punkty w kwadracie

Jeśli w kwadracie o boku $2$ umieścimy $5$ punktów, to dwa z nich są w odległości nie większej niż $\sqrt{2}$ .

Krok 1. Budujemy szuflady. Dzielimy kwadrat $2 \times 2$ na cztery kwadraty jednostkowe $1 \times 1$ .

Krok 2. Stosujemy zasadę. Punktów jest $5$ , kwadratów $4$ , więc w którymś małym kwadracie znajdą się co najmniej dwa punkty.

Krok 3. Szacujemy odległość. Dwa punkty w kwadracie o boku $1$ są od siebie oddalone co najwyżej o długość przekątnej:

$d \leq \sqrt{1^2 + 1^2} = \sqrt{2}.$

To wszystko. Kluczowy był krok 1 - wymyślenie właściwych szuflad.

Przykład 4 - reszty z dzielenia

Wśród dowolnych $5$ liczb całkowitych są dwie, których różnica dzieli się przez $4$ .

Szufladami są reszty z dzielenia przez $4$ : $0, 1, 2, 3$ - są cztery. Liczb jest pięć, więc dwie z nich, powiedzmy $a$ i $b$ , dają tę samą resztę $r$ :

$a = 4k + r, \qquad b = 4l + r.$

Wtedy

$a - b = 4(k - l),$

czyli różnica dzieli się przez $4$ . Ta sztuczka - „szufladami są reszty” - jest jednym z najczęstszych chwytów w zadaniach olimpijskich z teorii liczb.

Kto i kiedy

Zasadę spopularyzował Peter Gustav Lejeune Dirichlet w 1834 roku, używając jej w dowodach z teorii liczb; po niemiecku nosi nazwę Schubfachprinzip - dosłownie „zasada szufladek”. W literaturze angielskiej mówi się o pigeonhole principle, czyli „zasadzie gołębników”: gołębi jest więcej niż przegródek, więc w którejś siedzą co najmniej dwa.

Sama obserwacja pojawiała się wcześniej, m.in. u francuskiego jezuity Jeana Leurechona w XVII wieku - w wersji z porównywaniem liczby włosów mieszkańców, którą przytoczyliśmy wyżej.

Najczęstsze pytania

Czy zasada mówi, w której szufladzie są dwa przedmioty? Nie. Gwarantuje jedynie istnienie takiej szuflady. To dowód niekonstruktywny - wiemy, że coś istnieje, choć nie potrafimy tego wskazać.

Czym różni się wersja uogólniona od podstawowej? Podstawowa daje wniosek „co najmniej dwa” i wymaga $n + 1$ przedmiotów w $n$ szufladach. Uogólniona działa dla dowolnych liczb i mówi, ile dokładnie przedmiotów musi się spotkać: $\lceil n/k \rceil$ .

Jak rozpoznać zadanie na zasadę szufladkową? Zwykle po sformułowaniu „wykaż, że istnieją dwa…”, „zawsze znajdą się…”, „co najmniej dwa obiekty mają wspólną cechę”. Trzeba wtedy zapytać: co jest przedmiotem, a co szufladą?

Czy zasada działa dla zbiorów nieskończonych? Podstawowa wersja dotyczy zbiorów skończonych. Dla nieskończonych obowiązuje jej odpowiednik: jeśli nieskończenie wiele przedmiotów rozmieścimy w skończenie wielu szufladach, to w którejś będzie ich nieskończenie wiele.

Dlaczego coś tak oczywistego nazywa się twierdzeniem? Bo mimo trywialnej treści wymaga dowodu i pozwala udowadniać rzeczy zupełnie nieoczywiste - jak przykład z włosami czy z punktami w kwadracie. W matematyce siła narzędzia nie zależy od jego skomplikowania.

Podsumowanie

Zasada: $n + 1$ przedmiotów w $n$ szufladach oznacza, że gdzieś spotkają się co najmniej dwa.
Wersja uogólniona podaje mocniejszy wniosek: w pewnej szufladzie jest co najmniej $\lceil n/k \rceil$ przedmiotów.
Dowód jest jednolinijkowy (zliczanie nie wprost) - trudność zadań leży zawsze w wymyśleniu szuflad.
Typowe szuflady: reszty z dzielenia, przedziały, pola figury, możliwe wartości cechy.
Zasada dowodzi istnienia, ale nie wskazuje obiektu - to klasyczny dowód niekonstruktywny.