Wie lautet das verallgemeinerte Taubenschlagprinzip?

Damit bei k Behältern garantiert mindestens m Objekte in einem Behälter liegen, werden mindestens k(m−1)+1 Objekte benötigt.

Warum wird bei der Formel eins addiert?

k(m−1) Objekte lassen sich noch mit höchstens m−1 Objekten je Behälter verteilen. Das nächste Objekt erzwingt die Belegung m.

Was ist der Unterschied zum Geburtstagsparadoxon?

Das Taubenschlagprinzip liefert eine sichere Garantie. Das Geburtstagsparadoxon beschreibt dagegen eine Wahrscheinlichkeit.

📪

Taubenschlagprinzip-Rechner

Verallgemeinerte Formel · Schritt-für-Schritt-Beweis · Klassische Beispiele

Berechnen Sie die Mindestanzahl an Objekten, damit garantiert mindestens m Objekte im selben Behälter liegen. Verwendet werden k(m−1)+1 und ⌈n/k⌉.

Berechnungsart wählen

Modus 1: Aus der Anzahl der Behälter (k) und der Garantieschwelle (m) wird die kleinste Gesamtzahl bestimmt, bei der mindestens ein Behälter m oder mehr Objekte enthält. Formel: k(m−1) + 1

Schnellbeispiele

k — Anzahl der Behälter

m — Garantieschwelle

Wählen Sie ein Beispiel, um die vollständige Lösung mit dem Taubenschlagprinzip anzuzeigen.

🎂

Geburtstagsproblem

365/366 mögliche Geburtstage

Wie viele Personen garantieren einen gemeinsamen Geburtstag für zwei oder drei Personen?

367 Personen → 2 gemeinsam; 733 → 3 gemeinsam

🤤

Socken in einer Schublade

Farben und passende Paare

Wie viele Socken müssen blind gezogen werden, um ein gleichfarbiges Paar zu garantieren?

k Farben → k+1 Socken erforderlich

📅

Kalendermonate & Wochentage

Monate und Wochentage

Garantiert zwei Personen mit gleichem Geburtsmonat oder Wochentag.

13 Personen (Monate); 8 Personen (Wochentage)

♠

Spielkarten

4 Farben, Kartenspiel mit 52 Karten

Mindestzahl gezogener Karten für zwei Karten derselben Farbe.

5 Karten garantieren 2 derselben Farbe

🔢

Ganze Zahlen mit Summe 11

Aus der Menge {1, 2, …, 10}

Beliebige 6 Zahlen aus {1…10} garantieren ein Paar mit Summe 11.

6 Zahlen → ein Paar ergibt 11

■

Punkte im Einheitsquadrat

Garantierte Abstandsgrenze

5 Punkte in einem 1×1-Quadrat garantieren 2 Punkte mit Abstand ≤ 1/√2.

5 Punkte → Abstand ≤ 0,707

Schnellübersicht — klassische Beispiele

Wählen Sie eine Karte, um den Rechner automatisch auszufüllen.

Karten & Farben

k=4, m=2 → 5

5 Karten aus einem Kartenspiel garantieren 2 derselben Farbe

Birthdays (Month)

k=12, m=2 → 13

13 Personen garantieren 2 mit demselben Geburtsmonat

Gleicher Wochentag

k=7, m=2 → 8

8 Personen garantieren 2 mit demselben Wochentag

Passende Socken

k=5, m=2 → 6

Bei 5 Sockenfarben garantieren 6 Socken ein gleichfarbiges Paar

Geburtstag (Tag)

k=366, m=2 → 367

367 Personen garantieren 2 mit demselben Geburtstag

3 gemeinsame Geburtstage

k=366, m=3 → 733

733 Personen garantieren 3 mit demselben Geburtstag

Was ist das Taubenschlagprinzip?

Das Taubenschlagprinzip, auch Schubfachprinzip oder Dirichletsches Schubfachprinzip genannt, ist ein Grundsatz der Kombinatorik. Werden n Objekte auf k Behälter verteilt, enthält mindestens ein Behälter wenigstens ⌈n/k⌉ Objekte.

Verallgemeinerte Formel

N = k(m − 1) + 1

Dabei ist k die Anzahl der Behälter und m die Belegung, die in mindestens einem Behälter garantiert werden soll. Mit k(m−1) Objekten könnte jeder Behälter noch genau m−1 Objekte enthalten; das zusätzliche Objekt erzwingt die Belegung m.

Historischer Hintergrund

Der deutsche Mathematiker Peter Gustav Lejeune Dirichlet formulierte das Schubfachprinzip im 19. Jahrhundert und nutzte es unter anderem für Resultate der diophantischen Approximation.

Anwendungen in Mathematik und Informatik

Existenzbeweise in Zahlentheorie und Graphentheorie
Kollisionen bei Hashfunktionen
Grenzen verlustfreier Datenkompression
Untere Schranken für Sortierverfahren
Geburtstags-, Karten- und Belegungsprobleme

Geburtstagsproblem und Geburtstagsparadoxon

Bei höchstens 366 möglichen Geburtstagen garantieren 367 Personen einen gemeinsamen Geburtstag. Das Geburtstagsparadoxon beantwortet eine andere Frage: Bereits bei 23 Personen liegt die Wahrscheinlichkeit einer Übereinstimmung über 50 Prozent. Das Taubenschlagprinzip liefert eine sichere Grenze, keine Wahrscheinlichkeit.

Beispieltabelle

Beispiel	Behälter	Garantie	Mindestanzahl
Gleicher Geburtstag	366 Tage	2 Personen	367
Gleicher Geburtsmonat	12 Monate	2 Personen	13
Gleiche Kartenfarbe	4 Farben	2 Karten	5
Sockenpaar	k Farben	2 Socken	k+1

Häufig gestellte Fragen

Was besagt das Taubenschlagprinzip?

Werden mehr Objekte als Behälter verteilt, liegen mindestens zwei Objekte im selben Behälter. Allgemein sind mindestens ⌈n/k⌉ Objekte gemeinsam.

Wie lautet die verallgemeinerte Formel?

Für k Behälter und die garantierte Belegung m werden mindestens k(m−1)+1 Objekte benötigt.

Warum wird eins addiert?

k(m−1) Objekte lassen sich noch gleichmäßig ohne Belegung m verteilen. Erst das nächste Objekt erzwingt sie.

Wie wird das Prinzip in der Informatik genutzt?

Es weist Hashkollisionen nach, erklärt Grenzen der Kompression und liefert Schranken für Algorithmen und Graphenfärbungen.

Was unterscheidet das Geburtstagsparadoxon?

Das Taubenschlagprinzip liefert eine sichere Garantie; das Geburtstagsparadoxon berechnet eine Wahrscheinlichkeit.

Taubenschlagprinzip-Rechner

Schritt-für-Schritt-Beweis

Visuelle Darstellung

Lösung