Dla nikogo nie jest niespodzianką, że jeśli mamy 10 przedmiotów, a tylko 4 szufladki, do których chcemy te przedmioty włożyć, to co najmniej jedna z nich będzie zawierała więcej niż jeden przedmiot. Nawet gdybyśmy mieli 9 szuflad, to i tak jedna będzie zawierała więcej niż jeden przedmiot. Niewielkie uogólnienie tego spostrzeżenia, zanotujemy jako lemat 12.6.1.

Lemat 12.6.1

Jeśli skończony zbiór X podzielimy na n podzbiorów, to co najmniej jeden z podzbiorów będzie miał co najmniej |X|/n elementów.

Gdyby każdy z podzbiorów, na które podzielimy zbiór X miał mniej elementów niż |X|/n , to moc sumy tych zbiorów byłaby mniejsza niż |X|. ♦

Lemat 12.6.1 jest jednym z prostszych sformułowań zasady szufladkowej Dirichleta.

Przypuśćmy, że pewne 9 osób O1, ..., O9, waży razem 810kg. Czy dowolna trójka tych osób może wsiąść do windy o udźwigu 250 kg?

Suma wag w każdym wierszu tablicy wynosi 810kg, czyli razem w trzech wierszach mamy 2430kg. Kolumny tej tablicy tworzą 9 różnych trójek. Na mocy zasady szufladkowej Dirichleta, przynajmniej w jednej kolumnie suma wag wynosi co najmniej 2430/9 = 270kg. Czyli istnieje (co najmniej jedna) taka trójka osób, które nie mogą razem wsiąść do windy.

Następujące twierdzenie jest nieco inną postacią zasady szufladkowej Dirichleta:

Twierdzenie 12.6.1

Niech f będzie funkcją całkowitą określoną na zbiorze X, f : X → Y oraz niech |X| > k*|Y|. Wtedy co najmniej dla jednego y, przeciwobraz f ^-1({y}) ma więcej niż k elementów.

Pytanie 12.6.1: W zbiorze 100 wybranych studentów PJWSTK wszystkie nazwiska zaczynają się od liter K, M, S i T. Wyjaśnij dlaczego w PJWSTK studiuje co najmniej 25 studentów, których nazwiska zaczynają się na tę samą literę.

Pewna Uczelnia zatrudnia 5 profesorów reprezentujących 4 różne specjalności. Przewiduje się, że na koniec roku akademickiego 40 studentów tej Uczelni będzie chciało bronić swoich prac magisterskich. W każdej komisji egzaminacyjnej, zgodnie z przyjętymi ustaleniami, powinno brać udział 3 profesorów reprezentujących różne specjalności. Udowodnić, że przynajmniej jedna z komisji będzie musiała uczestniczyć w co najmniej 6 egzaminach.

Oznaczmy profesorów-specjalistów w tej samej dziedzinie przez A i B. Wszystkie komisje trzyosobowe możemy podzielić na 3 kategorie:

Jest tylko jedna komisja 1go rodzaju, oraz 3 komisje drugiego i 3 komisje trzeciego rodzaju (wybieramy dwóch pozostałych członków komisji spośród trzech profesorów, czyli

). Możliwych komisji jest więc 7. Określmy funkcję f, która każdemu magistrantowi przypisuje komisję egzaminacyjną. Ponieważ 40 > 5*7, zatem na mocy zasady szufladkowej Dirichleta, co najmniej dla jednego x, przeciwobraz f ^-1({x}) ma więcej niż 5 elementów, co oznacza, że co najmniej jedna komisja będzie musiała uczestniczyć w co najmniej 6 egzaminach.

Załóżmy, że w jednej grupie ćwiczeniowej w PJWSTK jest co najwyżej 15 studentów. Oczywiście każdy student należy do jednej tylko grupy i różne grupy mają różne oznaczenia. Wśród 100 losowo wybranych studentów PJWSTK przeprowadzono anonimową ankietę dotyczącą oceny prowadzących zajęcia nauczycieli. Warunkiem uznania ankiety za ważną było wpisanie w odpowiedniej rubryce indentyfikatora grupy studenckiej, do której należy ankietowany. Po zebraniu ankiet okazało się, że wszystkie ankiety były ważne i, że ankietowani studenci należą tylko do 6 różnych grup. Czy można zaakceptować wyniki takiej ankiety? Udowodnić, że co najmniej jeden student nie był prawdomówny.

Zgodnie z przyjętymi założeniami w sześciu grupach studenckich może być co najwyżej 6*15 studentów. Ponieważ 100 > 6*15. Zatem co najmniej jeden z 6 numerów grup został wpisany przez więcej niż piętnastu studentów. Co najmniej 20 studentów nie napisało w ankiecie prawdy, a ponieważ stanowi to 1/5 wszystkich ankietowanych, zatem raczej trzeba powtórzyć przeprowadzenie tej ankiety.

Niech A będzie ustalonym dziesięcioelementowym podzbiorem zbioru {1,2,...50}. Udowodnić, że w zbiorze A istnieją dwa różne pięcioelementowe podzbiory takie, że sumy wszystkich liczb każdego z nich są równe.

Rozwiązanie. Niech X będzie zbiorem wszystkich pięcioelementowych podzbiorów A. Oczywiście zbiór X składa się z 252 podzbiorów. Określimy funkcję f : X → {1,2...50} tak, że dla dowolnego pięcioelementowego zbioru {a,b,c,d,e},

f({a,b,c,d,e}) = a+b+c+d+e.

Zbiór wartości funkcji f składa się z 226 elementów, bo 15 ≤ f({a,b,c,d,e}) ≤ 240. Zatem, na mocy twierdzenia 12.6.1 istnieją co najmniej dwa zbiory należące do X, dla których wartości funkcji f są takie same.

Następujące twierdzenie jest jeszcze jedną, prostą konsekwencją zasady Dirichleta.

Twierdzenie 12.6.2

Niech d₁, d₂, ..., d_n będzie ciągiem stopni wierzchołków pewnego n wierzchołkowego grafu prostego. Wtedy istnieją w tym grafie co najmniej dwa wierzchołki, które mają ten sam stopień.

Dowód.
Zgodnie z założeniami twierdzenia, stopnie wierzchołków tego grafu mogą przyjmować tylko wartości 0,1,2,...,n-1. Nie możemy jednak mieć równocześnie wierzchołka stopnia 0 i wierzchołka stopnia n-1. Zatem stopnie wierzchołków mogą przyjmować tylko n-1 rożnych wartości. Na mocy zasady Dirichleta, muszą więc istnieć co najmniej dwa wierzchołki o tym samym stopniu.

Pytanie 12.6.2: Załóżmy, że między dowolnymi dwoma miejscowościami pewnego regionu istnieje co najwyżej jedna, łącząca je droga. Uzasadnić, że w tym regionie istnieją co najmniej dwie miejscowości, które łączy taka sama liczba dróg z innymi miejscowościami.