Schubfachprinzip

Studium

n_1 + \ldots + n_k = n \;\Rightarrow\; \max_{1 \leq j \leq k} n_j \geq \left\lceil \frac{n}{k} \right\rceil

Voraussetzung: $n, k \in \mathbb{N},$ $k \geq 1,$ $n_1, \ldots, n_k \in \mathbb{N}_0$

$n$: Anzahl der verteilten Objekte
$k$: Anzahl der Fächer
$n_j$: Anzahl der Objekte im Fach j
$\left\lceil x \right\rceil$: Aufrundung, die kleinste ganze Zahl größer oder gleich x

Verteilt man n Objekte auf k Fächer, liegen in mindestens einem Fach mindestens n/k aufgerundet Objekte.

Erklärung

Das Schubfachprinzip (auch Dirichletsches Prinzip) ist ein einfaches, aber starkes Beweiswerkzeug: Legt man mehr Objekte in Fächer, als es Fächer gibt, dann landen in einem Fach mindestens zwei Objekte.

Allgemein liegen bei $n$ Objekten in $k$ Fächern in mindestens einem Fach $\lceil n/k \rceil$ Objekte. Beweis: Enthielte jedes Fach höchstens $\lceil n/k \rceil - 1 < n/k$ Objekte, wären es insgesamt weniger als $k \cdot n/k = n$ .

Das Prinzip ist ein Existenzbeweis: Es sagt, dass ein volles Fach existiert, aber nicht, welches. Die Kunst liegt darin, geeignete Objekte und Fächer zu wählen, etwa Reste modulo $m$ , Teilintervalle oder Farben.

Beispiele

Geburtstage: Unter $367$ Menschen haben mindestens zwei am selben Tag Geburtstag, denn es gibt nur $366$ mögliche Tage: $\lceil 367/366 \rceil = 2$ .

Socken: In einer Schublade liegen Socken in $3$ Farben. Wer im Dunkeln $4$ Socken nimmt, hat sicher zwei gleicher Farbe: $\lceil 4/3 \rceil = 2$ .

Monate: Von $100$ Personen haben mindestens $\lceil 100/12 \rceil = 9$ im selben Monat Geburtstag.

Zahlentheorie: Unter je $6$ ganzen Zahlen gibt es zwei, deren Differenz durch $5$ teilbar ist. Fächer sind die $5$ möglichen Reste modulo $5$ ; zwei Zahlen mit gleichem Rest haben eine durch $5$ teilbare Differenz.

Typische Fehler

Abrunden statt aufrunden. $\lfloor 100/12 \rfloor = 8$ ist zu schwach. Mit nur $8$ pro Monat kämen höchstens $8 \cdot 12 = 96$ Personen unter, also muss ein Monat $9$ haben.
Gleich viele Objekte wie Fächer. Bei $366$ Personen und $366$ Tagen ist eine Doppelung nicht garantiert. Man braucht mindestens ein Objekt mehr als Fächer.
Mehr behaupten als bewiesen. Das Prinzip sagt nicht, welches Fach voll ist, und auch nicht, dass die Objekte gleichmäßig verteilt sind.

Schubfachprinzip