Zum Inhalt springen
Inhaltsverzeichnis öffnen
Kapitel 2Aufbau25 Min.

Mehr als zwei im selben Fach

Das verallgemeinerte Schubfachprinzip · Abschnitt 5 von 64

Gelöstes Beispiel

Aufrunden ist unvermeidlich

Bei 25 Objekten in sieben Fächern ist 25/7>325/7>3. Es gilt lceil25/7ceil=4lceil25/7 ceil=4: Mindestens ein Fach hat vier Objekte.

Gelöstes Beispiel

Die letzte vermeidbare Verteilung

Um rr im selben Fach noch zu vermeiden, dürfen höchstens r1r-1 in jedes der kk Fächer: insgesamt k(r1)k(r-1).

Gelöstes Beispiel

Warum die Schranke scharf ist

Genau r1r-1 Objekte in jedem Fach zeigen: Weniger als k(r1)+1k(r-1)+1 Objekte garantieren die Zielbelegung noch nicht – die Schranke ist scharf.