Das Schubfachprinzip beweist, dass etwas existiert, ohne es zu finden

Gewissheit bei 367, Münzwurf bei 23

Der Abstand zwischen Garantiertem und Wahrscheinlichem ist hier gewaltig, und er macht das Geburtstagsproblem so überraschend. Dreiundzwanzig Menschen ergeben bereits 50,7 Prozent Wahrscheinlichkeit, dass zwei ein Datum teilen, siebenundfünfzig treiben sie auf 99 Prozent — und dennoch verlangt Gewissheit weiterhin 367, denn eine Anordnung, in der alle Geburtstage verschieden sind, bleibt bis dahin möglich. Das Schubfachprinzip spricht nur über die garantierte Spalte und schweigt zur anderen. Danach zu greifen, wenn man eine Wahrscheinlichkeit wollte, ergibt eine wahre und nutzlose Aussage; nach der Wahrscheinlichkeit zu greifen, wenn man eine Garantie brauchte, ergibt eine Behauptung, die an genau der nicht bedachten Anordnung scheitert.

Existenzbeweise, die die Antwort verbergen

Eine Hashfunktion, die jede Datei in eine feste Bitzahl verwandelt, hat mehr mögliche Eingaben als Ausgaben; Kollisionen müssen also existieren — zwei verschiedene Dateien mit gleichem Hash — und das Schubfachprinzip beweist es in einer Zeile. Eine zu finden ist etwas ganz anderes, und die praktische Sicherheit eines Hashes ruht auf dieser Lücke: Jeder weiß, dass Kollisionen da sind, und bei einer soliden Funktion kann sie niemand vorlegen. Dieselbe Gestalt taucht überall auf, wo ein Abzählargument verfügbar ist: Es klärt, ob etwas möglich ist, und lässt die Suche unberührt. Ein Vorzug, wenn man wissen muss, dass eine Suche nicht vergeblich ist — eine Enttäuschung, wenn man eine Adresse erwartet hat.

Häufige Fragen

Warum 366 und nicht 365?

Weil der 29. Februar ein möglicher Geburtstag ist und das Prinzip den schlimmsten Fall überstehen muss. Mit 365 Fächern erhielte man eine Garantie ab 366 Personen, die scheitert, sobald jemand in der Gruppe an einem Schalttag geboren ist — und eine Garantie, die scheitert, ist keine. Das ist die kennzeichnende Disziplin des Prinzips: Jede Zählung muss die Zahl der denkbar nutzbaren Fächer sein, nicht die der üblicherweise genutzten, und jedes auf den Regelfall gebaute Argument bricht genau an dem Beispiel zusammen, das jemand zur Probe vorlegen wird.

Gibt es eine Fassung für ungleiche Fächer?

Ja, und es ist dasselbe Abzählargument, sorgfältiger geschrieben. Hat jedes Fach eine eigene Kapazität, zählt die Gesamtkapazität: Übersteigt man die Summe, ist irgendein Fach über seinem Limit — welches, sagt das Prinzip weiterhin nicht. Es gibt auch einen probabilistischen Vetter, genutzt wenn die Gegenstände nicht bösartig, sondern zufällig verteilt werden, und der liefert viel kleinere Schwellen — das Geburtstagsproblem ist genau dieser Vetter, und der Abstand zwischen 23 und 367 misst gut, was die Zufallsannahme einbringt.