Mathematische Sachaufgaben & Denkmodelle · Combinatorics & Pigeonhole Principle
Schubfachprinzip & Dirichlet-Visualisierer
Dirichletsches Schubfachprinzip & Worst-Case-Szenarien: Sockenpaare und garantierte Treffer
- Clientseitig
- Keine Anmeldung
- Echtzeit-Herleitung
- Projektormodus
- A4-Arbeitsblatt
Mathe-Demofenster● 60 FPS
Experimentelle Steuerungsparameter
Echtzeit-Herleitung & Kennzahlen
Garantiertes Minimum in mindestens 1 Kiste
--
Ganzzahliger Quotient q
--
Rest r
--
Schwelle im schlimmsten Fall
--
Echtzeit-Formelherleitung
Grundformel:
--Einsetzungsschritte:
--Ergebnis: --
Typische Beispielaufgaben & Prüfungsfallen
Worked Problem
Aufgabe: 370 students graduate. At least how many share a birth month? A birthday?
Schrittweise Herleitung:
- Months: 370 / 12 = 30 R 10 => at least 30 + 1 = 31 in same month. Days: 370 / 366 = 1 R 4 => at least 1 + 1 = 2 share birthday.
Worked Problem
Aufgabe: Bag has 8 red, 7 yellow, 5 blue, 3 white balls. Minimum draws to guarantee: 1) a matching pair; 2) at least 1 blue ball?
Schrittweise Herleitung:
- 1) Matching pair: 4 colors + 1 = 5 draws. 2) Blue guaranteed: exhaust all non-blue (8+7+3 = 18), then draw 1 = 18 + 1 = 19 draws.
Arbeitsblatt für den Unterricht & Hausaufgaben
Q1. Variant 1: Does any set of 5 consecutive integers contain a multiple of 5? Why?
Answer Key: Always! Remainders modulo 5 are {0, 1, 2, 3, 4} (5 drawers). 5 consecutive integers map to all 5 remainders, including remainder 0.
Q2. Variant 2: Standard 52-card deck (4 suits of 13). Minimum draws to guarantee at least 3 cards of the same suit?
Answer Key: Worst case: draw 2 cards of each of the 4 suits = 4 * 2 = 8 cards. Next card makes a triplet: 8 + 1 = 9 cards.
Q3. Variant 3: Prove that placing 5 points inside an equilateral triangle of side 1 guarantees two points closer than 0.5.
Answer Key: Connect midpoints of sides to divide into 4 smaller equilateral triangles of side 0.5. 5 points into 4 triangles forces 2 into one triangle.
Häufige Fragen & typische Missverständnisse
If division has remainder 2 or 3, is the pigeonhole formula still Quotient + 1?
Yes, strictly Quotient + 1! Any non-zero remainder ceiling-rounds up. Only when remainder is exactly 0 does it equal Quotient.
How do Worst-Case Scenario and Pigeonhole Principle interrelate?
They are dual inverses! Pigeonhole takes inputs and derives minimum guarantees. Worst-case takes target goals and back-calculates required sample size.
Do two people in Beijing have the exact same number of hairs? Prove via pigeonhole.
Human scalp has <300,000 hairs. Beijing has >20,000,000 people. 20M people in 300K drawers forces multiple people to share the exact hair count.
How does the pigeonhole principle dictate hash table collisions in computer science?
Mapping keys to finite buckets inevitably produces collisions when keys exceed bucket capacity, mandating collision resolution chains.