Kombinatorisches Prinzip, das besagt, dass bei der Verteilung von mehr diskreten Objekten auf weniger Behälter mindestens ein Behälter mehr als ein Objekt enthalten muss.

Prinzip

Werden n+1 oder mehr Objekte auf n Kästen verteilt, enthält mindestens ein Kasten mindestens zwei Objekte; allgemeiner gilt: bei m Objekten und n Kästen existiert ein Kasten mit mindestens ⌈m/n⌉ Objekten.

Demonstration

Werden 13 Socken in 12 Schubladen gelegt, so enthält mindestens eine Schublade mindestens zwei Socken. Beim Geburtstagsparadoxon: mit 367 Personen und 366 möglichen Geburtstagen müssen zwei Personen den gleichen Geburtstag haben.

Fehlanwendung

Das Prinzip dazu verwenden, um konkret zu bestimmen, welcher Behälter überfüllt ist; aus der Existenzbehauptung Wahrscheinlichkeitsaussagen ableiten; oder es auf unendliche/ungezählte kontinuierliche Verteilungen anwenden, ohne zu discretisieren.

Konsequenz

Ermöglicht einfache Existenzbeweise und untere Schranken in Kombinatorik, Zahlentheorie und Informatik; garantiert Kollisionen oder Duplikate, ohne konstruktiv anzugeben, wo diese auftreten.

Umkehrung

Gibt es weniger Objekte als Behälter, so können alle Behälter leer oder höchstens mit einem Objekt belegt sein; eine Existenz eines belegten Behälters ist dann nicht zwangsläufig.

Abgrenzung

Gilt für endliche, diskrete Zuordnungen oder diskretisierbare Situationen; quantifiziert nicht das Ausmaß der Überbelegung über die reine Existenz hinaus und setzt eine klare Festlegung von Objekt und Behälter voraus.

Semantische Spannung

Spannung zwischen der deterministischen Existenzbehauptung und probabilistischen Deutungen (Kollisionswahrscheinlichkeit, erwartete Belegung), die zusätzliche Annahmen benötigen.

Synthese

Das Schubfachprinzip ist ein grundlegendes kombinatorisches Existenzgesetz: Wird eine endliche Menge diskreter Objekte auf weniger unterscheidbare Behälter verteilt, so garantiert es die Existenz eines Behälters mit mehreren Objekten und dient als Basis nichtkonstruktiver Beweise und Kollisionsargumente.