Do czego służy kalkulator zasady szufladkowej?
W kalkulatorze zasady szufladkowej Dirichleta sprawdzisz, ile elementów trzeba rozdzielić między grupy, aby mieć pewność, że w jednej grupie pojawi się co najmniej określona liczba elementów. Typowe pytania brzmią: „ile osób trzeba mieć, żeby co najmniej 2 urodziły się w tym samym miesiącu?”, „ile kulek gwarantuje 4 kulki w jednym pudełku?” albo „ile plików trafi do jednego folderu?”.
To narzędzie pasuje do działu matematyka dyskretna, logika, zbiory i grafy. Uzupełnia działania na zbiorach, tablice prawdy, prawa De Morgana, relacje i własności relacji oraz kalkulatory grafowe, takie jak drzewa w grafach.
Wzór i logika obliczeń
Podstawowa wersja zasady szufladkowej mówi: jeśli rozdzielisz N obiektów do s szuflad, to w co najmniej jednej szufladzie znajdzie się co najmniej ceil(N / s) obiektów.
Jeśli chcesz zagwarantować k obiektów w jednej szufladzie, minimalna liczba obiektów wynosi:
| Co liczysz? | Wzór | Jak czytać wynik? |
|---|---|---|
| Gwarancja z N obiektów | ceil(N / s) | Co najmniej tyle obiektów będzie w jednej szufladzie |
| Minimum dla gwarancji k | s(k - 1) + 1 | Tyle obiektów wystarczy, aby wymusić k w jednej grupie |
| Brak do gwarancji | Nmin - N | Ile obiektów trzeba jeszcze dodać |
Przykład obliczeń
Załóżmy, że w klasie jest 23 uczniów, a szufladami są 12 miesięcy urodzenia. Z zasady szufladkowej mamy ceil(23 / 12) = 2, więc w co najmniej jednym miesiącu urodziło się przynajmniej 2 uczniów.
Jeśli chcesz mieć pewność, że w jednym miesiącu będą co najmniej 3 osoby, potrzeba 12 · (3 - 1) + 1 = 25 uczniów.
Zadania przykładowe z odpowiedziami
Ile osób potrzeba, aby mieć pewność, że co najmniej 2 osoby urodziły się w tym samym miesiącu?
Do 5 pudełek wkładamy kulki. Ile kulek gwarantuje 4 kulki w jednym pudełku?
17 plików trafia do 4 folderów. Ile plików na pewno jest w którymś folderze?
Ile skarpetek trzeba wyjąć z 3 kolorów, aby mieć pewność, że dwie są tego samego koloru?
Odpowiedź 1: 13 osób, bo 12 · (2 - 1) + 1 = 13.
Odpowiedź 2: 16 kulek, bo 5 · (4 - 1) + 1 = 16.
Odpowiedź 3: Co najmniej 5 plików, bo ceil(17 / 4) = 5.
Odpowiedź 4: 4 skarpetki, bo 3 · (2 - 1) + 1 = 4.
Tabela referencyjna
| Liczba szuflad | Gwarancja 2 w jednej szufladzie | Gwarancja 3 w jednej szufladzie | Gwarancja 4 w jednej szufladzie |
|---|---|---|---|
| 3 | 4 | 7 | 10 |
| 5 | 6 | 11 | 16 |
| 10 | 11 | 21 | 31 |
| 12 | 13 | 25 | 37 |
Najczęstsze błędy i jak zwiększyć dokładność wyniku
- Mylenie gwarancji z możliwością - zasada szufladkowa mówi o pewności, nie o tym, co może się zdarzyć przypadkiem.
- Pomijanie +1 - we wzorze s(k - 1) + 1 ostatni element wymusza przekroczenie bezpiecznego rozkładu.
- Złe określenie szuflad - w zadaniu szufladami mogą być miesiące, kolory, reszty z dzielenia, foldery lub grupy.
- Nieczytanie pytania - „co najmniej 2” i „co najmniej 3” dają różne progi.
Ciekawostka
Zasada szufladkowa jest prosta, ale bardzo mocna. W zadaniach olimpijskich i informatycznych pomaga udowodnić, że pewne powtórzenie musi wystąpić, nawet jeśli nie wiemy, gdzie dokładnie.
Powiązane kalkulatory matematyki dyskretnej
Zasada szufladkowa często łączy się z resztami modulo, bo reszty mogą być szufladami. Warto też sprawdzić rozszerzony algorytm Euklidesa, działania na zbiorach i tablice prawdy.
Jeżeli pracujesz z grafami, przejdź do stopni wierzchołków, grafu pełnego, drzew w grafach i ścieżek i cykli w grafie.
Cały pakiet: matematyka dyskretna, logika, zbiory i grafy
Ten kalkulator należy do jednego pakietu z zakresu matematyki dyskretnej. Jeżeli pracujesz z logiką i zbiorami, przejdź kolejno przez tablica prawdy, prawa De Morgana, działania na zbiorach oraz relacje i własności relacji. Te narzędzia pomagają rozumieć zapisy zdań, negacje, diagramy Venna i własności relacji.
Jeśli zadanie dotyczy reszt z dzielenia, wybierz modulo i reszty z dzielenia, kongruencje liniowe albo rozszerzony algorytm Euklidesa. Do zadań z gwarantowanym powtórzeniem pasuje zasada szufladkowa Dirichleta, szczególnie gdy szufladami są reszty modulo, kolory, miesiące lub inne klasy.
Część grafową tworzą: stopnie wierzchołków grafu, graf pełny Kₙ, drzewa w grafach, ścieżki i cykle w grafie i macierz sąsiedztwa grafu. Dzięki temu możesz przejść od listy krawędzi, przez macierz sąsiedztwa, aż po stopnie, cykle, drzewa i graf pełny.
Wskazówka od KalkulatorXXL
W zadaniach z zasadą szufladkową najpierw nazwij szuflady. Dopiero potem licz obiekty. Jeśli dobrze rozpoznasz szuflady, wzór zwykle robi się oczywisty.
Cały dział matematyki dyskretnej: Akademia matematyki dyskretnej – logika, zbiory i grafy łączy tablice prawdy, prawa De Morgana, zbiory, relacje, modulo, kongruencje, podzielność, kombinatorykę, prawdopodobieństwo i teorię grafów.