Zasada Szufladkowa Dirichleta, czyli proste narzędzie do (również) niebanalnych problemów

Gdy n + 1 przedmiotów włożymy do n szufladek, na pewno w którejś szufladce znajdą się przynajmniej dwa przedmioty – to potoczne brzmienie twierdzenia zwanego Zasadą Szufladkową Dirichleta. Ogólniejsze wersje również są łatwe do odkrycia:

• A gdy włożymy n · k + 1 przedmiotów do n szufladek, to ile co najmniej znajduje się ich w którejś szufladce?1
• Ile musimy mieć przedmiotów, aby mieć pewność, że wkładając je do n szufladek, w którejś znajdzie się co najmniej m przedmiotów?2
• A gdy włożymy n przedmiotów do k szufladek, ile (co najmniej) na pewno znajdzie się w jednej z nich?

Odpowiedź na ostatnie z ww. pytań może wymagać już dokonania kilku prób na konkretnych liczbach, a forma odpowiedzi może zależeć od tego, z czym nasi uczniowie już się zetknęli. Jeśli poznali część całkowitą liczby x (zwaną też cechą lub podłogą i oznaczaną [x] bądź ⎣x⎦) oraz sufit (⎡x⎤), możemy spodziewać się odpowiedzi w najbardziej zwartej formie: ⎡⎤. Jeśli nie, odpowiedź pewnie będzie bardziej opisowa: 
Jeśli n dzieli się przez k, to w którejś szufladce znajduje się na pewno co najmniej  przedmiotów, a jeśli n nie dzieli się przez k, to w którejś szufladce znajduje się co najmniej część całkowita3 liczby , powiększona o 1.
Wiele zadań o różnym stopniu trudności wykorzystuje Zasadę Szufladkową Dirichleta. Zarówno dla starszych klas szkoły podstawowej, jak i dla uczniów szkół ponadgimnazjalnych/ponadpodstawowych można znaleźć ciekawe problemy. Młodsi uczniowie mogą rozpocząć przygodę z ZSD od zadań typu:

• uzasadnij, że pewnych dwóch mieszkańców Warszawy ma tyle samo włosów na głowie4,
• uzasadnij, że pewnych dwóch/trzech5 uczniów klasy ma urodziny w tym samym miesiącu.

Dla starszych rozpocznę od zadania z drugiego etapu 69. Olimpiady Matematycznej, które można było rozwiązać, korzystając z ZSD i… cierpliwości6.

Zadanie 1 
Dane są takie pięcioelementowe podzbiory {A1, A2, … , Ak} zbioru {1, 2, … , 23}, że dla wszystkich 1 ≤ i ≤ j ≤ k zbiór  Ai ∩ Aj ma co najwyżej trzy elementy. Wykazać, że k ≤ 2018.
Rozwiązanie: Przypuśćmy, że k > 2018. Wypisujemy po kolei wszystkie liczby ze wszystkich zbiorów A1, A2, … , Ak, czyli 5k liczb. Ponieważ k > 2018 wypisaliśmy przynajmniej 2019 · 5 = 10 095 liczb ze zbioru {1, 2, … , 23}, więc któraś z nich – nazwijmy ją a – powtórzyła się przynajmniej ⎡⎤ = ⎡438,91…⎤ = 439 razy – po raz pierwszy wykorzystaliśmy ZSD. Niech B1, B2, … , B439 będą tymi zbiorami z {A1, A2, … , Ak}, które ją zawierają. I znowu wypisujemy z nich wszystkie elementy, powtarzając, ale już bez a, które występowało w każdym z nich. Wypisaliśmy 4 · 439 liczb ze zbioru 22-elementowego (tj. ze zbioru {1, 2, 3, … , 23} \ {a}), więc któraś, nazwijmy ją b, powtórzyła się przyn...