Strona głównaKombinatorykaZasada szufladkowa Dirichleta

Zasada szufladkowa Dirichleta

Jeżeli n+1n+1 przedmiotów włożymy do nn szuflad, to w co najmniej jednej szufladzie znajdą się co najmniej dwa przedmioty. Zdanie jest tak oczywiste, że wygląda na niewarte nazwy — a mimo to rozwiązuje zadania, które bez niego są nie do ruszenia. Cała sztuka polega nie na samej zasadzie, tylko na wymyśleniu, co w danym zadaniu jest szufladą.

Dział: KombinatorykaPoziom: poza podstawą programową — dla chętnych

1Treść zasady i dlaczego jest prawdziwa

Zagadnienie dodatkowe — poza podstawą programową (SP/LO 2025)

Zasada szufladkowa nie występuje w podstawie programowej — ani w szkole podstawowej, ani w liceum, także w zakresie rozszerzonym. Na egzaminie ósmoklasisty ani na maturze nie pojawi się jako polecenie.

Jest natomiast stałym gościem konkursów matematycznych i jednym z najprostszych twierdzeń, których dowód prowadzi się nie wprost — dlatego warto ją znać, choć nikt jej nie wymaga.

Strona należy do działu Zagadnienia dodatkowe: materiał dla tych, którzy chcą wyjść poza program.

Dowód mieści się w jednym zdaniu i jest dowodem nie wprost: gdyby w każdej z nn szuflad był co najwyżej jeden przedmiot, to przedmiotów byłoby co najwyżej nn — a jest ich n+1n+1. Sprzeczność.

Warto zwrócić uwagę, że zasada mówi „co najmniej dwa”, a nie „dokładnie dwa”. Przy 100100 przedmiotach i 22 szufladach w którejś będzie ich co najmniej 5050, a nie dwa.

Wersja ogólna — z sufitem

Jeżeli nn przedmiotów rozmieścimy w kk szufladach, to w co najmniej jednej szufladzie znajdzie się co najmniej nk\left\lceil \dfrac{n}{k} \right\rceil przedmiotów.

Symbol   \lceil \; \rceil to sufit, czyli zaokrąglenie w górę do liczby całkowitej. Dla 3030 uczniów i 1212 miesięcy daje to 3012=2,5=3\left\lceil \tfrac{30}{12} \right\rceil = \lceil 2{,}5 \rceil = 3.

Zaokrąglanie w górę jest tu istotne. Gdyby zaokrąglić w dół, wyszłoby 22 — a to jest twierdzenie fałszywe w drugą stronę: dwóch uczniów w jednym miesiącu owszem będzie, ale zasada gwarantuje więcej.

Uzasadnienie znów przez sprzeczność: gdyby w każdej szufladzie było najwyżej n/k1\lceil n/k \rceil - 1 przedmiotów, łącznie byłoby ich mniej niż nn.

Nazwa pochodzi od Petera Dirichleta, który sformułował zasadę w XIX wieku. W literaturze angielskiej nosi nazwę „zasady gołębi i przegródek”, bo klasyczną ilustracją jest gołębnik: przy większej liczbie gołębi niż przegródek w którejś muszą siedzieć co najmniej dwa.

2Trzy pytania, które trzeba sobie zadać

Zastosowanie zasady sprowadza się zawsze do tego samego schematu:

  1. Co jest przedmiotem? Zwykle to, czego jest dużo i co wymieniono w treści: ludzie, liczby, punkty.
  2. Co jest szufladą? To najtrudniejszy krok. Szuflada to zwykle cecha, którą przedmioty mogą dzielić: miesiąc urodzenia, kolor, reszta z dzielenia, parzystość współrzędnych.
  3. Ile jest szuflad? Trzeba je policzyć dokładnie. Pomyłka o jeden psuje całe rozumowanie.

Gdy liczba przedmiotów przekracza liczbę szuflad, wniosek zapada sam: dwa przedmioty trafią do tej samej szuflady, czyli mają wspólną cechę. I to właśnie ta wspólna cecha jest zwykle tezą zadania.

Klasyczny przykład: włosy na głowie

Teza: w Warszawie mieszkają co najmniej dwie osoby o dokładnie tej samej liczbie włosów na głowie.

Przedmioty: mieszkańcy — około 18000001\,800\,000 osób. Szuflady: możliwe liczby włosów. Człowiek ma ich najwyżej około 200000200\,000, więc szuflad jest 200001200\,001 (od zera do dwustu tysięcy).

Przedmiotów jest więcej niż szuflad, więc teza zachodzi. Można nawet mocniej: 8200001=16000088 \cdot 200\,001 = 1\,600\,008, czyli mniej niż 18000001\,800\,000 — więc po ośmiu osobach na szufladę nadal by nie starczyło. W którejś jest co najmniej dziewięć osób.

Zwróć uwagę, czego ten dowód nie daje: nie wskazuje ani jednej takiej osoby. Wiemy, że istnieją, i nie mamy pojęcia, kim są.

3Reszty z dzielenia jako szuflady

Najczęstsze zastosowanie w zadaniach matematycznych: szufladami są reszty z dzielenia przez ustaloną liczbę.

Przy dzieleniu przez kk możliwych reszt jest dokładnie kk: 0,1,2,,k10, 1, 2, \ldots, k-1. To gotowy komplet szuflad, i to o znanej z góry liczbie.

Kluczowa obserwacja, która zamienia „ta sama szuflada” w tezę zadania: jeśli dwie liczby dają tę samą resztę z dzielenia przez kk, to ich różnica dzieli się przez kk. Wynika to wprost z zapisu: skoro a=qk+ra = qk + r i b=pk+rb = pk + r, to ab=(qp)ka - b = (q-p)k.

zadanieszufladyile ich jest
dwie liczby o różnicy podzielnej przez 44reszty z dzielenia przez 4444 — wystarczy 55 liczb
dwie liczby o różnicy podzielnej przez 1010reszty z dzielenia przez 10101010 — wystarczy 1111 liczb
dwie liczby o tej samej ostatniej cyfrzeostatnia cyfra1010 — wystarczy 1111 liczb
dwa punkty kratowe o kratowym środkuparzystość obu współrzędnych44 — wystarczy 55 punktów

Ostatni wiersz jest najładniejszy i wart osobnego zdania. Każdy punkt kratowy ma współrzędne albo parzyste, albo nieparzyste — niezależnie dla xx i dla yy, więc kombinacji jest 22=42 \cdot 2 = 4. Przy pięciu punktach dwa trafiają do tej samej kategorii, a wtedy obie sumy współrzędnych są parzyste, więc środek odcinka między nimi ma współrzędne całkowite.

4Czego zasada nie mówi

Zasada szufladkowa jest twierdzeniem o istnieniu, i to bardzo słabym — dlatego łatwo z niej wyciągnąć wniosek, którego nie zawiera:

Ten czwarty punkt jest najczęstszym źródłem błędnych rozwiązań. Zdanie „wśród 1212 osób dwie urodziły się w tym samym miesiącu” jest fałszywe — kontrprzykład to dwunastu ludzi urodzonych w dwunastu różnych miesiącach. Dopiero trzynasta osoba wymusza powtórzenie.

Dlatego przy każdym zadaniu warto sprawdzić, czy liczba przedmiotów jest co najmniej o jeden większa od liczby szuflad. Jeśli jest dokładnie równa — zasady zastosować nie wolno, a zadanie prawdopodobnie pyta o coś innego. Jeśli jest większa o więcej niż jeden, tym lepiej: wtedy działa wersja ogólna z sufitem i można wykazać coś mocniejszego niż samo „co najmniej dwa”, jak w przykładzie z trzydziestoma uczniami.

5Gdzie się to przydaje

Skoro zasady nie ma w podstawie programowej (ramka na górze strony), warto powiedzieć wprost, komu i do czego się przydaje.

Jest stałym gościem konkursów matematycznych na wszystkich poziomach, bo pozwala udowodnić istnienie czegoś bez wskazywania tego czegoś — a zadania konkursowe lubią właśnie taką konstrukcję.

Ma też wartość poza konkursami: uczy myślenia o klasyfikowaniu obiektów. Umiejętność zauważenia, że reszty z dzielenia przez 44 dzielą wszystkie liczby całkowite na cztery grupy, przydaje się potem przy cechach podzielności, przy dowodach parzystości i przy zadaniach o okresowości.

Warto też docenić jej rolę dydaktyczną: to jedno z najprostszych twierdzeń, których dowód jest nie wprost. Uczeń, który raz prześledzi rozumowanie „gdyby w każdej szufladzie był najwyżej jeden, to byłoby ich za mało”, ma gotowy wzorzec do dowodu niewymierności 2\sqrt{2} i do wielu zadań na wykazanie.

6Przykłady krok po kroku

Pięć zadań: miesiące urodzenia, wersja ogólna z sufitem, skarpetki po ciemku, reszty z dzielenia i punkty kratowe.

Przykład 1 Miesiąc urodzenia

Wykaż, że wśród dowolnych 13\textcolor{#16A06A}{13} osób znajdą się dwie urodzone w tym samym miesiącu.

  1. Przedmioty: osoby — jest ich 1313.
  2. Szuflady: miesiące urodzenia. Miesięcy jest 12\textcolor{#16A06A}{12}.
  3. Każda osoba trafia do dokładnie jednej szuflady, bo urodziła się w dokładnie jednym miesiącu.
  4. Przedmiotów jest więcej niż szuflad (13>1213 > 12), więc z zasady szufladkowej w którymś miesiącu jest co najmniej 2\textcolor{#E0453A}{2} osoby.
  5. Kontrola przez sprzeczność: gdyby każdy miesiąc miał najwyżej jedną osobę, osób byłoby najwyżej 1212 — a jest 1313
  6. Kontrola granicy: dla 1212 osób teza nie zachodzi — kontrprzykładem jest dwanaście osób urodzonych w dwunastu różnych miesiącach. Liczba 1313 w treści jest więc najmniejszą działającą ✓

Odpowiedź: Tak — przy 1313 osobach i 1212 miesiącach co najmniej dwie osoby dzielą miesiąc urodzenia.

Ostatnia kontrola jest tu ważniejsza niż samo rozwiązanie. Pokazuje, że liczba 1313 nie jest przypadkowa: przy 1212 zadanie byłoby fałszywe.

Przykład 2 Wersja ogólna — trzech w jednym miesiącu

W klasie jest 30\textcolor{#16A06A}{30} uczniów. Wykaż, że co najmniej trzech urodziło się w tym samym miesiącu.

  1. Przedmiotów jest 3030, szuflad (miesięcy) — 1212. Zwykła wersja zasady dałaby tylko „co najmniej dwóch”, a to za mało.
  2. Sięgam po wersję ogólną: w którejś szufladzie jest co najmniej nk\left\lceil \dfrac{n}{k} \right\rceil przedmiotów.
  3. 3012=2,5\dfrac{30}{12} = 2{,}5, a sufit z 2,52{,}5 to 3\textcolor{#E0453A}{3}.
  4. Zatem w którymś miesiącu urodziło się co najmniej trzech uczniów.
  5. Kontrola przez sprzeczność: gdyby w każdym miesiącu było najwyżej dwóch uczniów, byłoby ich najwyżej 122=2412 \cdot 2 = 24 — a jest 3030
  6. Kontrola granicy w drugą stronę: dla 2424 uczniów teza o trzech nie zachodziłaby, bo da się rozłożyć dokładnie po dwóch na miesiąc. Najmniejsza działająca liczba to 2525
  7. Kontrola zaokrąglenia: sufit, nie podłoga. Podłoga z 2,52{,}5 dałaby 22 — twierdzenie prawdziwe, ale słabsze, niż można udowodnić ✓

Odpowiedź: Tak — przy 3030 uczniach w którymś miesiącu urodziło się co najmniej trzech.

Kontrola przez sprzeczność w piątym kroku jest najlepszym sposobem sprawdzenia, czy sufit został policzony dobrze. Mnożymy liczbę szuflad przez „o jeden mniej” i patrzymy, czy wychodzi za mało.

Przykład 3 Skarpetki po ciemku

W szufladzie leży 10\textcolor{#16A06A}{10} czarnych i 10\textcolor{#16A06A}{10} białych skarpetek. Ile najmniej skarpetek trzeba wyjąć po ciemku, żeby mieć pewność, że wśród nich jest para tego samego koloru?

  1. Szuflady: kolory. Są 2\textcolor{#16A06A}{2}: czarny i biały. Przedmioty: wyjęte skarpetki.
  2. Żeby zagwarantować dwie skarpetki w jednej szufladzie, przedmiotów musi być o jeden więcej niż szuflad.
  3. Wystarczy więc 2+1=32 + 1 = \textcolor{#E0453A}{3} skarpetki.
  4. Kontrola, że 33 wystarcza: przy trzech skarpetkach i dwóch kolorach z zasady szufladkowej dwie mają ten sam kolor ✓
  5. Kontrola, że 22 nie wystarcza: można wyjąć jedną czarną i jedną białą — pary nie ma. Czyli 33 to naprawdę minimum ✓
  6. Uogólnienie: przy kk kolorach odpowiedzią jest k+1k+1. Liczba skarpetek każdego koloru nie ma znaczenia, byle każdego było co najmniej po jednej.

Odpowiedź: Trzy skarpetki — i liczba 1010 w treści jest tu bez znaczenia.

To zadanie uczy odróżniania danych istotnych od tła. Liczba skarpetek każdego koloru nie wpływa na odpowiedź; liczy się wyłącznie liczba kolorów, czyli liczba szuflad.

Przykład 4 Reszty z dzielenia

Wykaż, że wśród dowolnych 5\textcolor{#16A06A}{5} liczb całkowitych znajdą się dwie, których różnica dzieli się przez 4\textcolor{#16A06A}{4}.

  1. Szuflady: reszty z dzielenia przez 44. Możliwe reszty to 0,1,2,30, 1, 2, 3 — szuflad jest dokładnie 44.
  2. Przedmioty: pięć danych liczb. Każda ma dokładnie jedną resztę z dzielenia przez 44, więc trafia do dokładnie jednej szuflady.
  3. 5>45 > 4, więc z zasady szufladkowej dwie liczby mają tę samą resztę. Oznaczam je aa i bb, a wspólną resztę rr.
  4. Zapisuję je: a=4q+ra = 4q + r oraz b=4p+rb = 4p + r, gdzie qq i pp są całkowite.
  5. Odejmuję: ab=(4q+r)(4p+r)=4q4p=4(qp)a - b = (4q + r) - (4p + r) = 4q - 4p = \textcolor{#E0453A}{4(q-p)}.
  6. Liczba qpq - p jest całkowita, więc różnica jest wielokrotnością 44 — co kończy dowód.
  7. Kontrola na konkretnych liczbach: weźmy 3,7,10,15,223, 7, 10, 15, 22. Reszty z dzielenia przez 44 to kolejno 3,3,2,3,23, 3, 2, 3, 2. Para 33 i 77 ma wspólną resztę, a 73=47 - 3 = 4 dzieli się przez 44
  8. Kontrola granicy: dla czterech liczb teza nie zachodzi — kontrprzykład 1,2,3,41, 2, 3, 4 ma reszty 1,2,3,01, 2, 3, 0, wszystkie różne, i żadna różnica nie dzieli się przez 44

Odpowiedź: Tak — przy pięciu liczbach dwie muszą dawać tę samą resztę z dzielenia przez 44, a wtedy ich różnica jest podzielna przez 44.

To najważniejszy schemat w całym temacie: reszty z dzielenia przez kk to gotowy komplet kk szuflad. Większość zadań konkursowych z zasady szufladkowej korzysta właśnie z niego.

Przykład 5 Punkty kratowe

Na płaszczyźnie dano 5\textcolor{#16A06A}{5} punktów o obu współrzędnych całkowitych. Wykaż, że wśród nich są dwa takie, że środek łączącego je odcinka też ma obie współrzędne całkowite.

  1. Szuflady: parzystość obu współrzędnych. Współrzędna xx jest parzysta albo nieparzysta, tak samo yy, więc kombinacji jest 22=42 \cdot 2 = \textcolor{#16A06A}{4}: (p, p), (p, n), (n, p), (n, n).
  2. Przedmioty: pięć danych punktów. 5>45 > 4, więc dwa punkty trafiają do tej samej szuflady.
  3. Oznaczam je A=(x1,y1)A = (x_1, y_1) i B=(x2,y2)B = (x_2, y_2). Mają tę samą parzystość obu współrzędnych.
  4. Skoro x1x_1 i x2x_2 są tej samej parzystości, ich suma x1+x2x_1 + x_2 jest parzysta. Tak samo y1+y2y_1 + y_2.
  5. Środek odcinka ABAB ma współrzędne (x1+x22,y1+y22)\left( \dfrac{x_1+x_2}{2}, \dfrac{y_1+y_2}{2} \right). Obie sumy są parzyste, więc po podzieleniu przez 22 dają liczby całkowite\textcolor{#E0453A}{\text{całkowite}}
  6. Kontrola na przykładzie: punkty (1,3)(1,3) i (5,7)(5,7) są oba w szufladzie (n, n). Środek: (1+52,3+72)=(3,5)\left( \tfrac{1+5}{2}, \tfrac{3+7}{2} \right) = (3, 5) — kratowy ✓
  7. Kontrola kontrprzykładem dla czterech punktów: (0,0)(0,0), (0,1)(0,1), (1,0)(1,0), (1,1)(1,1) leżą w czterech różnych szufladach. Środek dowolnej pary, np. (0,0)(0,0) i (0,1)(0,1), to (0;0,5)(0; 0{,}5) — nie jest kratowy ✓ Zatem pięć punktów to minimum.

Odpowiedź: Tak — przy pięciu punktach kratowych dwa mają tę samą parzystość obu współrzędnych, a środek łączącego je odcinka jest wtedy kratowy.

Wymyślenie, że szufladą jest parzystość pary współrzędnych, jest tu całą trudnością. Reszta rozwiązania to trzy linijki rachunku — i tak wygląda większość zadań z tej zasady.

7Najczęstsze błędy

Dwa pierwsze błędy dotyczą liczenia i rozpoznawania szuflad, trzeci jest rachunkowy (podłoga zamiast sufitu), a dwa ostatnie — zakresu wniosku, jaki wolno z zasady wyciągnąć.

Stosowanie zasady, gdy przedmiotów jest tyle samo co szuflad.

Skąd się bierze: Liczby wyglądają na „pasujące do siebie”, a warunek „o jeden więcej” bywa zapamiętany nieprecyzyjnie.

Jak zrobić dobrze: Potrzebna jest ostra nierówność. Zdanie „wśród 1212 osób dwie urodziły się w tym samym miesiącu” jest fałszywe\textcolor{#9b1c14}{\text{fałszywe}} — dwanaście osób może mieć dwanaście różnych miesięcy. Dopiero trzynasta wymusza powtórzenie.

Zamiana ról przedmiotów i szuflad.

Skąd się bierze: Oba zbiory są w treści wymienione obok siebie, a nazwy „przedmiot” i „szuflada” nie są w zadaniu podane wprost.

Jak zrobić dobrze: Szufladą jest zawsze cecha, a przedmiotem — obiekt, który tę cechę ma. W zadaniu o miesiącach szufladami są miesiące, a osoby przedmiotami; odwrotnie wyszłoby, że jeden miesiąc ma dwie osoby\textcolor{#9b1c14}{\text{jeden miesiąc ma dwie osoby}} jako założenie, a to jest teza.

Użycie podłogi zamiast sufitu w wersji ogólnej.

Skąd się bierze: Zaokrąglanie w dół jest odruchem przy dzieleniu z resztą, bo tak działa iloraz całkowity.

Jak zrobić dobrze: Obowiązuje sufit: dla 3030 uczniów i 1212 miesięcy jest to 2,5=3\lceil 2{,}5 \rceil = 3, a nie 2\textcolor{#9b1c14}{2}. Kontrola: 122=24<3012 \cdot 2 = 24 < 30, więc dwóch na miesiąc nie starcza.

Oczekiwanie, że zasada wskaże, która szuflada jest pełna.

Skąd się bierze: Dowód wygląda na konstrukcyjny, bo operuje konkretnymi liczbami z treści.

Jak zrobić dobrze: To twierdzenie czysto egzystencjalne — mówi, że taka szuflada istnieje, i nic ponad to. W zadaniu o włosach wiemy, że dwie osoby mają ich tyle samo, ale nie umiemy wskazać ani jednej\textcolor{#9b1c14}{\text{ani jednej}} z nich.

Odwracanie wniosku.

Skąd się bierze: Zdanie „więcej przedmiotów niż szuflad ⟹ jakaś szuflada ma dwa” bywa czytane jako równoważność.

Jak zrobić dobrze: Implikacja działa tylko w jedną stronę. Z tego, że dwa przedmioty leżą razem, nie wynika, że przedmiotów jest więcej niż szuflad — mogą leżeć razem także wtedy, gdy pozostałe\textcolor{#9b1c14}{\text{pozostałe}} szuflady stoją puste.

8Pytania i odpowiedzi

Co mówi zasada szufladkowa Dirichleta?

Mówi, że jeżeli przedmiotów jest więcej niż szuflad, do których je wkładamy, to w co najmniej jednej szufladzie znajdą się przynajmniej dwa przedmioty. Dowodzi się jej nie wprost, zauważając, że po jednym przedmiocie na szufladę byłoby ich za mało.

Jak brzmi wersja ogólna tej zasady?

Przy rozmieszczeniu pewnej liczby przedmiotów w pewnej liczbie szuflad w którejś z nich znajdzie się co najmniej tyle przedmiotów, ile wynosi iloraz obu liczb zaokrąglony w górę. Zaokrąglanie w górę jest tu istotne, bo w dół dawałoby wniosek słabszy.

Co najczęściej bywa szufladą w zadaniach?

Najczęściej reszty z dzielenia przez ustaloną liczbę, ponieważ tworzą gotowy komplet szuflad o znanej liczbie. Dwie liczby o tej samej reszcie mają różnicę podzielną przez tę liczbę, co zwykle jest właśnie tezą zadania.

Czy zasada wskazuje, w której szufladzie są dwa przedmioty?

Nie wskazuje i to jest jej najważniejsze ograniczenie. Dowodzi jedynie, że taka szuflada istnieje, nie podając o którą chodzi ani nie pozwalając jej znaleźć. Jest to twierdzenie o istnieniu, a nie metoda konstrukcji.

Czy zasada szufladkowa jest wymagana na maturze?

Nie występuje w podstawie programowej na żadnym poziomie, więc nie pojawi się jako polecenie egzaminacyjne. Jest natomiast stałym elementem zadań konkursowych i dobrym wprowadzeniem do dowodów prowadzonych nie wprost.

Czytaj dalej

Mateusz Będkowski — nauczyciel matematyki, autor serwisu Nie każ mu liczyć

Mateusz Będkowski

nauczyciel matematyki, autor „Nie każ mu liczyć”

Uczę matematyki od 13 lat, w tym 7 lat w szkole — dziś w dwóch szkołach w Kaliszu. Magister pedagogiki ze specjalnością terapia pedagogiczna, po studiach podyplomowych z matematyki. Rozwiązania na tej stronie liczę sam, krok po kroku, i zapisuję dokładnie tak, jak tłumaczę je uczniowi na kartce.

Ostatnia aktualizacja: 2026-08-02. Tekst redakcji „Nie każ mu liczyć”.