Zasada szufladkowa Dirichleta

Co się właśnie stało?

Rozmieściliśmy N obiektów w M szufladach, rozkładając je możliwie równo. Gdy obiektów jest więcej niż szuflad, przynajmniej jedna szuflada musi przyjąć drugi obiekt — nie ma innej możliwości.

Zasada szufladkowa Dirichleta:

Jeśli N obiektów rozmieszczamy w M szufladach i $N > M$, to co najmniej jedna szuflada zawiera dwa lub więcej obiektów. N — liczba obiektów, M — liczba szuflad.

Wersja ogólna (mocniejsza):

Nie tylko „co najmniej dwa" — zawsze istnieje szuflada z co najmniej sufitem ze średniej:

Dla 13 osób i 12 miesięcy: $\lceil 13/12\rceil = 2$ — gwarantowana para. Dla 25 osób i 12 miesięcy: $\lceil 25/12\rceil = 3$ — gwarantowana trójka.

Dlaczego to działa?

Dowód „nie wprost": gdyby każda z M szuflad miała najwyżej jeden obiekt, w sumie zmieściłoby się co najwyżej M obiektów. Ale mamy N > M, więc to niemożliwe — sprzeczność. Kolizja jest więc konieczna.

Po co Ci to na maturze:

Zasada szufladkowa to sztandarowe narzędzie w dowodach kombinatorycznych. Chwyt: nazwij „obiekty" i „szuflady" tak, by było ich odpowiednio N i M z N > M — reszta wynika sama. Klasyki: dwie osoby o tej samej liczbie znajomych, dwa punkty blisko siebie, powtórzenie reszty z dzielenia.

Zapamiętaj: więcej obiektów niż szuflad ⇒ pewna kolizja. Ogólnie najpełniejsza szuflada ma co najmniej ⌈N/M⌉ obiektów. To nie szansa — to konieczność.