## [Schubfachprinzip (Taubenlochprinzip)](/de/node/63488) Definition Die kombinatorische Behauptung, dass wenn n+1 Objekte in n Schubladen verteilt werden, mindestens eine Schublade mehr als ein Objekt enthält; allgemeiner: bei mehr Objekten als Behältern enthält irgendein Behälter mindestens die Decke von Objekte/Behälter. ## Prinzip Prinzip Unvermeidlichkeit durch Zählvergleich: Die ordnende Idee ist, dass einfache Kardinalitätsvergleiche Kollisionen oder Wiederholungen erzwingen, wenn Objekte die Behälter übersteigen, und so eine minimale Existenzgarantie liefern ohne detaillierte Verteilungsinformation. ## Demonstration Demonstration Werden 13 Socken in 12 Schubladen gelegt, garantiert das Prinzip eine Schublade mit mindestens 2 Socken. Allgemeiner stellt die Verteilung von 10 Objekten auf 3 Kästen sicher, dass ein Kasten mindestens ⌈10/3⌉ = 4 Objekte enthält. ## Fehlanwendung Fehlanwendung Das Prinzip auf stetige Verteilungen ohne Diskretisierung anwenden, oder aus dem Schubfachschluss auf Gleichverteilung schließen (verwechseln von 'ein Kasten hat ≥k' mit 'jeder Kasten hat ≥k'), oder es einsetzen wenn Behälter nicht eindeutig definiert sind. ## Konsequenz Konsequenz Erzeugt viele elementare Existenzresultate und untere Schranken in Kombinatorik, Zahlentheorie und Informatik (z. B. Kollisionen beim Hashing, garantierte gleiche Reste modulo m oder wiederholte Werte in Folgen). ## Umkehrung Umkehrung Das Gegenteil liegt vor, wenn die Objekte die Behälter nicht übersteigen; dann zwingt das Prinzip nicht zu Kollisionen und alle Behälter können leer oder einfach besetzt sein; die Umkehrung der Ungleichung entfernt die garantierte Wiederholung. ## Abgrenzung Abgrenzung Gilt für endliche diskrete Verteilungen mit wohldefinierten Behältern und abzählbaren Objekten; gilt nicht unmittelbar für stetige Maße ohne Diskretisierung und gibt keinen Hinweis, wo genau Kollisionen auftreten, außer dass eine existiert. ## Semantische Spannung Semantische Spannung Spannung zur probabilistischen Erwartung: Das Schubfachprinzip garantiert eine kombinatorische Kollision extremer Art, liefert aber keine Aussage über typische Verteilungen oder Wahrscheinlichkeiten — Existenz im Worst-Case versus Durchschnittsverhalten. ## Synthese Synthese Das Schubfachprinzip ist eine einfache Zählgarantie: Wenn Objekte die Behälter übersteigen, sind Kollisionen unvermeidlich; es ist ein kraftvolles Existenzwerkzeug zum Beweisen von Wiederholungen, unteren Schranken und Unvermeidbarkeitsresultaten in der diskreten Mathematik.