Poziom studiów
Zasada szufladkowa Dirichleta pozwala rozstrzygać istnienie powtórzeń w skończonych zbiorach.
Jej najprostsza wersja mówi, że jeśli \(n+1\) obiektów rozmieścimy w \(n\) szufladkach, to istnieje szufladka zawierająca co najmniej dwa obiekty.
Jeżeli \(10\) gołębi włożymy do \(9\) klatek, to musi istnieć klatka z dwoma gołębiami:
Zasada szufladkowa Dirichleta
Jeżeli \(n\) przedmiotów włoży się do \(k\) szufladek, gdzie \(n \gt k\), to w co najmniej jednej szufladce znajdą się co najmniej dwa przedmioty. Czasami użyteczne jest też sformułowanie zasady szufladkowej na zbiorach.
Sformułowanie na zbiorach
Jeżeli zbiór \(n\)-elementowy \(X\) można zapisać w postaci sumy \(k\) zbiorów: \(X=X_{1}\cup X_{2}\cup \dots \cup X_{k}\), gdzie \(k \lt n\), to któryś ze zbiorów \(X_1,...,X_k\) musi zawierać co najmniej dwa elementy. Uzasadnij, że wśród \(500\) można znaleźć dwie osoby, które mają urodziny tego samego dnia.
Mamy \(500\) osób i tylko \(365\) dni w roku (szufladek). Ponieważ \(500 \gt 365\), zatem z zasady Dirichleta w co najmniej jeden dzień w roku trafią co najmniej dwie osoby.
Wykaż, że jeśli w szufladzie znajdują się skarpety w \(7\) różnych kolorach, to wyciągając 8 skarpet, otrzymamy co najmniej dwie skarpety tego samego koloru.
Mamy \(8\) wyciągniętych skarpet (przedmiotów) i tylko \(7\) zbiorów-kolorów (szufladek). Ponieważ \(8 \gt 7\), więc zasada Dirichleta gwarantuje, że wśród \(8\) wyciągniętych skarpet zawsze będą co najmniej dwie w tym samym kolorze.
W dowolnej grupie \(n\) osób (\(n\ge2\)) każda osoba zna pewną liczbę osób z tej grupy (od 0 do \(n-1\)). Wykaż, że w takiej grupie są co najmniej dwie osoby, które znają tę samą liczbę osób.
Zakładamy, że znajomość jest relacją symetryczną (jeśli osoba \(A\) zna \(B\), to \(B\) zna \(A\)).
Zauważmy, że każdej osobie możemy przypisać liczbę znajomych od \(0\) do \(n-1\) czyli mamy \(n\) możliwości. Mamy także \(n\) osób, więc niewiele brakuje, żeby można było skorzystać z zasady Dirichleta (wystarczy, że liczbę możliwości na znajomych zmniejszymy z \(n\) do \(n-1\), aby była mniejsza od liczby osób).
Jeśli istniałaby osoba mająca \(0\) znajomych, to nikt nie może znać wszystkich pozostałych \(n-1\) osób (bo istnieje osoba, któa nie zna nikogo), więc wartość \(n-1\) nie wystąpi wśród pozostałych osób. Analogicznie, jeśli ktoś zna wszystkich pozostałych (\(n-1\) osoby), to nikt nie może mieć znać \(0\) osób. W obu wypadkach nie mogą wystąpić jednocześnie obie wartości skrajne \(0\) i \(n-1\).
Zatem możliwe wartości liczby znajomych to zbiór \(\{0,1,\dots,n-1\}\) z wykluczeniem co najmniej jednej z dwóch wartości skrajnych. Mamy więc co najwyżej \(n-1\) różnych wartości na liczbę znajomych, ale jest \(n\) osób. Skoro \(n \gt n-1\), to z zasady Dirichleta wynika, że dwie osoby muszą mieć ten sam stopień znajomości, czyli znają tę samą liczbę osób z grupy.
Wykaż, że w dowolnym zbiorze \(11\) liczb naturalnych istnieją co najmniej dwie liczby mające tę samą ostatnią cyfrę (w zapisie dziesiętnym).
Zbiór liczb naturalnych \(\mathbb{N} \) można zapisać w postaci sumy \(10\) zbiorów: \[\mathbb{N} = C_0\cup C_1\ \cup\, ...\, \cup\ C_9\] takich, że: \[C_k = \{n \in \mathbb{N}: n \equiv k \quad(\bmod 10)\}\] gdzie \(k\in \{0,1,2,...,9\}\)
Czyli \(C_k\) to zbiór liczb naturalnych kończących się na cyfrę \(k\).
Zatem podzieliliśmy zbiór liczb naturalnych na \(10\) podzbiorów ze względu na cyfrę na jaką kończy się dana liczba naturalna.
Mamy \(11\) liczb naturalnych i tylko \(10\) możliwych zbiorów (szufladek) do których możemy je włożyć. Ponieważ \(11 \gt 10\), zasada Dirichleta gwarantuje, że istnieje przynajmniej jeden zbiór \(C_k\), do której należą co najmniej dwie z podanych liczb. To znaczy - co najmniej dwie spośród tych \(11\) liczb mają tę samą resztę przy dzieleniu przez \(10\), a więc tę samą ostatnią cyfrę.
Wykaż, że w dowolnym zbiorze \(n+1\) liczb naturalnych istnieją dwie, których różnica dzieli się przez \(n\).
Podzielmy wszystkie liczby naturalne na \(n\) klas reszt modulo \(n\): \[ C_0, C_1, \dots, C_{n-1}, \] gdzie \[ C_k = \{\,m\in\mathbb{N}:m\equiv k\pmod n\},\quad k=0,1,\dots,n-1. \] Każda liczba zadanego zbioru należy więc do jednej z tych \(n\) klas.
Mamy \(n+1\) liczb i tylko \(n\) klas. Z zasady Dirichleta wynika, że co najmniej w jednej klasie znajdą się dwie liczby, powiedzmy \(a\) i \(b\). Wówczas \[ a\equiv b\pmod n \quad\Longrightarrow\quad a - b \equiv 0\pmod n, \] czyli \(n\) dzieli różnicę \(a-b\).
Stąd w dowolnym zbiorze \(n+1\) liczb naturalnych zawsze znajdą się dwie, których różnica jest podzielna przez \(n\).
W każde pole szachownicy \(10\times10\) wpisujemy jedną z liczb: \(-1,0,1\). Następnie obliczamy sumy liczb w każdym wierszu, w każdej kolumnie oraz na obu przekątnych. Pokaż, że spośród otrzymanych sum co najmniej dwie są równe.
Mamy \(10\) wierszy, \(10\) kolumn i \(2\) przekątne, czyli łącznie mamy: \[ 10 + 10 + 2 = 22 \] sum.
Każda z tych sum jest liczbą ze zboru: \(-10,-9,\dots,0,\dots,9,10,\).
Czyli jest \(21\) możliwych wartości jakie mogą przyjmować sumy.
Z zasady Dirichleta, przy próbie umieszczenia \(22\) obiektów (sum) w \(21\) „szufladkach” (wartościach), co najmniej dwie sumy muszą trafić do tej samej szufladki – a więc są równe.
Grupa 20 studentów pisała kolokwium składające się z pięciu zadań. Za każde zadanie można było otrzymać 0, 1, 2 lub 3 punkty. Pokaż, że co najmniej dwoje z nich uzyskało taką samą sumaryczną liczbę punktów.
Każdy student otrzymuje sumę pięciu ocen, z których każda jest w zbiorze \(\{0,1,2,3\}\). Zatem łączny wynik każdego studenta to liczba z zakresu \[ 0,1,2,\dots,15, \] czyli jest \(16\) możliwych wartości.
Mamy \(20\) studentów („przedmiotów”) i tylko \(16\) możliwych sum („szufladek”). Ponieważ \[ 20 > 16, \] z zasady Dirichleta wynika, że co najmniej dwie sumy muszą być równe. W konsekwencji co najmniej dwoje studentów uzyskało taką samą sumaryczną liczbę punktów.
Dany jest zbiór złożony z dziesięciu liczb naturalnych dwucyfrowych w zapisie dziesiętnym. Pokaż, że w zbiorze tym istnieją dwa niepuste podzbiory, których sumy są równe.
Rozważmy wszystkie niepuste podzbiory tego zbioru. Jest ich dokładnie \[ 2^{10}-1 = 1023. \] Każdy taki podzbiór ma sumę będącą liczbą naturalną z przedziału \[ 10,11,12,\dots,990, \] a więc co najwyżej \[ 990 - 10 + 1 = 981 \] różnych wartości. Zatem przy próbie przypisania \(1023\) podzbiorom wartości sum do \(981\) możliwych „szufladek” zasada Dirichleta gwarantuje, że co najmniej dwa różne podzbiory otrzymają tę samą sumę. W konsekwencji w zbiorze istnieją dwa niepuste podzbiory o równych sumach.
Ile minimalnie musi być studentów w grupie zdającej trzy egzaminy (oceny: bdb, db, dst, ndst), aby zagwarantować, że co najmniej dwie osoby otrzymają identyczne oceny na wszystkich egzaminach?
Każdy student uzyskuje konfigurację trzech ocen, gdzie każda ocena może być jedną z \(4\) wartości: \[ \{\text{bdb},\;\text{db},\;\text{dst},\;\text{ndst}\}. \] Liczba wszystkich możliwych konfiguracji \(3\) ocen uzyskanych przez studenta, to: \[ 4 \cdot 4 \cdot 4 = 4^3 = 64 \] Jeżeli w grupie jest \(65\) studentów i tylko \(64\) możliwych konfiguracji ocen („szufladek”), to zasada Dirichleta gwarantuje, że co najmniej dwie konfiguracje muszą być takie same.
Zatem musi być minimum \(65\) studentów, żeby zagwarantować, że co najmniej dwie osoby otrzymają identyczne oceny na wszystkich egzaminach.