Wirtualne laboratorium/Matematyka/Kombinatoryka/Zasada szufladkowa Dirichleta
Wielkie odkrycie 1834 — Dirichlet

Zasada szufladkowa Dirichleta

Zasada szufladkowa (Dirichlet, 1834): jeśli obiektów jest więcej niż szuflad, jakaś szuflada musi zawierać co najmniej dwa. Ustaw liczby i zobacz nieuniknioną kolizję.

Zasada szufladkowa Dirichleta
Matematyka · Kombinatoryka · Zasada szufladkowa Dirichleta (1834)
Obiekty NN9 szt.
Szuflady MM4 szufl.
W grupie 13 osób co najmniej dwie urodziły się w tym samym miesiącu?
obiekty N
9
szuflady M
4
min. w najpełniejszej ⌈N/M⌉
3
kolizja
pewna
🎯 Wyzwanie: wymuś gwarantowane minimum
seria: 0

Dam Ci docelowe minimum — dobierz N i M tak, by najpełniejsza szuflada miała gwarantowane co najmniej tyle, czyli ⌈N/M⌉ = cel.

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:

N>M  ⇒  ∃ szuflada z≥⌈NM⌉obiektamiN > M \;\Rightarrow\; \exists\, \text{szuflada z} \ge \left\lceil \tfrac{N}{M} \right\rceil \text{obiektami}

Jeśli N obiektów rozmieszczamy w M szufladach i N>MN > 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:

max⁡j ∣Sj∣  ≥  ⌈NM⌉\max_j \, |S_j| \;\ge\; \left\lceil \frac{N}{M} \right\rceil

Dla 13 osób i 12 miesięcy: ⌈13/12⌉=2\lceil 13/12\rceil = 2 — gwarantowana para. Dla 25 osób i 12 miesięcy: ⌈25/12⌉=3\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ść.

Model poglądowy · Wirtualne laboratorium NexTutor

Spodobał Ci się eksperyment? Udostępnij go.

Jest darmowy — podeślij znajomym ze szkoły.

Teoria i wzory

Zasada Dirichleta

Jeśli NN obiektów wkładamy do MM szuflad i N>MN>M, to co najmniej jedna szuflada zawiera ≥2\ge 2 obiekty.

Wersja ogólna

Istnieje szuflada z co najmniej: ⌈NM⌉\left\lceil \frac{N}{M}\right\rceil obiektami.

Przykład

1313 osób, 1212 miesięcy — dwie osoby na pewno mają urodziny w tym samym miesiącu.

Oznaczenia: NN liczba obiektów, MM liczba szuflad, ⌈⋅⌉\lceil\cdot\rceil zaokrąglenie w górę.

Uczysz? Umieść ten eksperyment na swojej stronie.

Darmowy widget — wklej na stronę szkoły, bloga lub notatki. Linkuje do pełnej wersji.

Uczysz w klasie albo korepetujesz? Prowadź uczniów w NexTutor →

Najczęstsze pytania

›

Czy w grupie 13 osób dwie muszą mieć urodziny w tym samym miesiącu?

Tak, na pewno — 13 osób, 12 miesięcy, więc z zasady szufladkowej jakiś miesiąc się powtórzy.

›

Co mówi zasada szufladkowa ogólnie?

Przy N obiektach i M szufladach istnieje szuflada z co najmniej ⌈N/M⌉ obiektami.

Teoria (klasa): MAT.4.4.1 → Lekcja maturalna: MAT.M.14.1 →

Powiązane eksperymenty

Paradoks urodzinowy →Permutacje, wariacje, kombinacje →Reguła mnożenia →Twierdzenie Ramseya — porządek w chaosie →