Zasada szufladkowa Dirichleta

Zasada szufladkowa Dirichleta mówi nam, że jeśli mamy x przedmiotów oraz y szuflad, gdzie x>y>0, to w którejś z nich znajdą się co najmniej dwa przedmioty.

Mówiąc prościej, jeśli mamy więcej rzeczy niż szuflad, w którejś z nich znajdą się minimalnie dwa przedmioty.

Przykład :
Jeśli mamy 8 książek oraz 7 szuflad, to do którejś z nich muszą wejść co najmniej dwa przedmioty, aby wszystko się zmieściło.

Ten przykład można było samemu wydedukować bez żadnych obliczeń, ale weźmy sobie trochę trudniejszy przykład.

Mamy 34 przedmioty i chcemy podzielić je do 6 szuflad. Aby to szybko policzyć, należy podzielić większą cyfrę przez mniejszą. W tym przypadku wygląda to tak:

= 5 r. 4 —— Stąd wiemy, że do każdej szuflady wchodzi nam 5 przedmiotów, ale zostaną nam jeszcze 4 z nich. Tak więc,
w którejś z szuflad musi być co najmniej 6 przedmiotów.
Dlaczego 6?
Jeśli wyjdzie nam jakakolwiek reszta zaokrąglamy całość do góry. Zawsze do góry, niezależnie jaka ta reszta będzie.
Tutaj wyszło nam 5, 4 zaokrąglenie tego w górę jest równe 6. Dlatego do jednej szuflady musimy dać co najmniej 6 przedmiotów.
Można to sprawdzić na rysunkach:

I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I I
1._______ 2.________ 3. ______ 4.______ 5.______ 6._______

Widzimy, że jak rozłożymy po 5 do każdej szuflady zostaną nam jeszcze 4 przedmioty do rozmieszczenia. Więc jeśli damy je do np. 1, 2, 3 i 4 szuflady, to rzeczywiście, w którejś z szuflad znajduje się 6 elementów.