\(\begingroup\)\(\newcommand{\IX}{\mathbb{X}} \newcommand{\IW}{\mathbb{M}} \newcommand{\politician}[1]{\text{Ich habe die Frage nicht verstanden. #1}} \newcommand{\ba}{\begin{aligned}} \newcommand{\ea}{\end{aligned}} \newcommand{\bpm}{\begin{pmatrix}} \newcommand{\epm}{\end{pmatrix}} \newcommand{\bc}{\begin{cases}} \newcommand{\ec}{\end{cases}} \newcommand{\on}{\operatorname} \newcommand{\ds}{\displaystyle}\) Man kann es sich vorstellen: Johann Peter Gustav Lejeune Dirichlet, (1805 bis 1859), sitzt an seinem Schreibtisch in seinem Berliner Arbeitszimmer und sucht nach einem überzeugenden Argument, mit dem er einen Beweis abschließen kann.
Es gelingt aber nicht recht, und schließlich lehnt er sich etwas zurück, nimmt seine Brille ab, putzt sie und setzt sie wieder auf.
Sein Blick fällt auf den Aufsatz des Schreibmöbels, an dem er sitzt, und er erfreut sich, wie schon oft, an diesem schönen Stück, mit den vielen kleinen Schubladen und den reichhaltigen Intarsien aus verschiedenen Edelhölzern.
Nach diesem kurzen Moment der Entspannung wendet er sich erneut seiner Arbeit zu. Direkt aus der Feder formulieren sich nun die Sätze, mit denen er seinen Beweis zu Ende führt.

Später, nach seinem Tod, wurden Dirichlets Vorlesungen über Zahlentheorie von seinem Schüler Richard Dedekind veröffentlicht - das war 1863.
Darin findet sich die erste bekannte Formulierung dessen, was wir heute Schubfachprinzip nennen. Dirichlet selbst hatte dem keinen besonderen Namen gegeben.

Schubfachprinzip: Werden nk+1 Perlen auf n Schubfächer verteilt, so gibt es wenigstens ein Schubfach mit mehr als k Perlen.

Was kann man damit beweisen?

1. Unter 3 Personen haben mindestens 2 das gleiche Geschlecht.
    
2. Von 13 Personen haben 2 im gleichen Monat Geburtstag.

Nun aber (allmählich) steigernd:

1. Zeige, daß es zwei Deutsche mit der gleichen Anzahl von Haaren gibt!
    
2. Weil das Licht ausgefallen ist, mußt Du im Dunkeln in der Kommodenschublade zwei gleichfarbige Socken suchen. Deine Socken sind entweder schwarz oder weiß, und Du machst Dir nie die Mühe, die Socken zu Paaren zu rollen. Wieviele Socken mußt Du herausnehmen, um garantiert ein gleichfarbiges Paar zu haben? Wie viele Socken müßtest Du herausnehmen, wenn Du garantiert ein schwarzes Paar haben willst? [Lösung]
   Anmerkung: Um Socken entnehmen zu können, muß man wissen, daß Socken in der Schublade sind. Die Formulierung 'Schublade mit Socken' legt die Reichhaltigkeit nur scheinbar nahe. Um diese Interpretationsmöglichkeit auszuschalten, sei präzisiert, daß sich in der Sockenschublade je 5 Paar schwarze und weiße Socken befinden.
    
3. In jeder Gruppe von mindestens zwei Personen gibt es zwei, die die gleiche Anzahl von Bekannten innerhalb dieser Gruppe haben.[Lösung]
    
4. Unter 52 natürlichen Zahlen kann man zwei Zahlen auswählen, deren Summe oder deren Differenz durch 100 teilbar ist. Ist diese Behauptung auch für 51 Zahlen richtig?
    
5. Unter 9 Gitterpunkten der Ebene gibt es drei, deren Schwerpunkt ebenfalls ein Gitterpunkt ist. [Lösung]
    
6. Unter je fünf Punkten, die in einem Quadrat der Seitenlänge 4 liegen, gibt es zwei, die einen Abstand <= 3 haben.
    
7. Angenommen in einem Dorf leben 15 Männer und 10 Frauen. Jede Frau ist mit einer bestimmten Anzahl von Männern befreundet. Der König des Landes kommt in das Dorf, und bestimmt 10 Männer, die heiraten sollen.
   Warum sind mindestens 60 Freundschaften (zwischen Frauen und Männern) nötig, damit, egal welche 10 Männer ausgewählt werden, jede Frau einen Mann heiraten kann, mit dem sie auch befreundet ist?

Die Zahlentheorie kennt eine Reihe von Aussagen, die sich mit Hilfe des Schubfachprinzips beweisen lassen:

1. Ein Primzahl der Form 4n+1 ist Summe zweier Quadratzahlen.
    
2. Jede natürliche Zahl ist Summe von vier Quadratzahlen

Mehr über das S.P. und weitere interessante, gelöste Aufgaben:

1. von Robert Strich, Seite 11 ff [postscript],
   Ausschnitte daraus das S.P. betreffend bei math4u.de.
   [Beide Autoren widmen sich (gemeinsam) der Vorbereitung von Schülern für den Wettbewerb der Deutschen Mathematik Olympiaden, und ihre Seiten sind eine Schatztruhe voller mathematischer Geheimnisse und Tricks! Unter der Adresse math4u.de findet man 470+ Mathematik-Aufgaben zum Training in Vorbereitung auf Olympiaden und Wettbewerbe, mit ausführlichen Lösungen.

Lösung der Sockenaufgabe:
Wir teilen die Socken in zwei Kategorien (Schubfächer) ein, in die Kategorie der weißen und die der schwarzen Socken; das sind die 2 Schubfächer.

1. Wenn Du 3 Socken entnimmst, und sie in die 2 Schubfächer sortierst, dann kommen garantiert zwei Socken in die gleiche Schublade. Du hast entweder zwei weiße oder zwei schwarze Socken gefunden.
2. Wenn Du aber zwei Socken Deiner Lieblingsfarbe 'schwarz' suchst, so mußt Du im schlimmsten Fall 12 Socken ziehen, denn die ersten 10 könnten ja alle weiß sein.

Lösung des Bekanntenschaftsproblems:
Eine Person kommt in Schubfach i, wenn sie i Bekannte hat. Es gibt n Personen und n Schubfächer (nämlich 0, 1, ..., n-1). Aber die Schubfächer 0 und n-1 können nicht gleichzeitig besetzt sein.

Lösung Gitterpunkte:
Der Schwerpunkt von 3 Punkten x, y, z der Ebene errechnet sich als arithmetisches Mittel der Punktkoordinaten. Der Schwerpunkt ist dann ein Gitterpunkt, wenn die Summen x₁+y₁+z₁ und x₂+y₂+z₂ durch 3 teilbar sind.
Nun definiere Schubfächer und beschrifte sie mit (i,j), i,j Î{0,1,2}, den möglichen Resten bei Division durch 3. Das ergibt also 3² = 9 Schubfächer.
Als Perlen betrachte die Koordinatensummen von je 3 der 9 Gitterpunkte. Es gibt "9 über 3" = 84 Möglichkeiten diese Kombinationen zu bilden.
[Anm.: es ist nicht verlangt, daß die 9 Gitterpunkte alle verschieden sind. Sollten sich unter den 9 Punkten einige mehrfach befinden, dann unterscheide sie künstlich, etwa durch Zuordnung einer Farbe.]

Eine solche Perle kommt in Schubfach (i,j), wenn die Summe der ersten Koordinaten = i mod 3 und die Summe der zweiten Koordinaten = j mod 3 ist.

Verteile die 84 Perlen auf die 9 Schubfächer.
Wenn das Schubfach (0,0) nicht leer ist, dann sind wir fertig.

Nehmen wir also an, das Schubfach (0,0) sei leer und führen diese Annahme zu einem Widerspruch.

Dazu wieder eine Überlegung: Wenn 3 Punkte ein Dreieck bilden, dessen Schwerpunkt ein Gitterpunkt ist, dann ändert sich daran nichts, wenn man die Punktkoordinaten modulo 3 rechnet. Diese Aussage formulieren wir als

Lemma 1: Der Schwerpunkt des Dreiecks aus den Punkten x,y,z, mit x = (x1,x2), y = (y1,y2), z = (z1,z2), ist genau dann ein Gitterpunkt, wenn das für x'=r3(x), y'=r3(y), z'=r3(z) gilt. Dabei ist r3(x) die Abbildung von IR³->IR³, die einen Punkt x = (x1,x2) abbildet auf (x'1,x'2), wobei x'i der Divisionsrest von xi beim Teilen durch 3 ist.

Beweis: Zur Übung überlassen. ;-))

Wenn das Schubfach (0.0) leer ist, dann bedeutet das:

1. daß alle Schwerpunkte von Dreiecken aus den 9 Punkten keine Gitterpunkte sind,
2. daß es keine 3 gleichen unter den Gitterpunkten gibt.

Aus 2. folgert man, daß es mindestens 5 verschiedene Punkte geben muß. Das gilt für alle möglichen Wahlen von 9 Punkten. Es gilt - und darauf kommt es an - auch in {0,1,2}².

Nun benötigen wir ein weiteres

Lemma 2: Unter 5 Gitterpunkten der Ebene sind stets zwei, deren Verbindungslinie einen Gitterpunkt enthält. Insbesondere ist dieser Gitterpunkt der Mittelpunkt der Verbindungsstrecke.

Beweis: Mit dem Schubfachprinzip: Wir wählen beliebige 4 Gitterpunkte A, B, C, D in der Ebene. Nun füge diesen 4 Punkten A, B, C, D einen fünften Punkt P hinzu. Durch den neuen Punkt werden mit den 4 vorhanden Punkten 4 Verbindungslinien definiert.
Bilde (ähnlich wie oben) Schubladen (i,j) und lege eine durch 2 Punkte

x = (x₁,x₂) und
y = (y₁,y₂)

x₁ + y₁ = i mod 2 und
x₂ + y₂ = j mod 2.

Wenn die Klasse (0,0) nicht leer ist, dann sind wir fertig.

Ansonsten gibt es eine Klasse, die zwei Perlen enthält (verteile 4 Perlen auf 3 Schubfächer).
Die Perlen bedeutet zwei (ungeordnete) Punktepaare (P,A) und (P,B).
Da beide in der gleichen Klasse sind, gilt:

p₁ + a₁ = p₁ + b₁ mod 2
p₂ + a₂ = p₂ + b₂ mod 2

a₁ = b₁ mod 2
a₂ = b₂ mod 2

a₁ + b₁ = 0 mod 2
a₂ + b₂ = 0 mod 2

[Anmerkung: Die Verbindungsstrecke zweier zusammenfallender Punkte besteht nur aus dem Punkt. Ihr Mittelpunkt ist wiederum der Punkt selbst.]

Zurück zum Beweis für Schwerpunkte.
Sobald 5 verschiedene Punkte in der Ebene gewählt werden, ist der Mittelpunkt mindestens einer Verbindungsstrecke zweier Punkte ein Gitterpunkt.
Wir müssen aber in {0,1,2}² 9 mal einen Punkt auswählen, davon (mindestens) 5 verschiedene (wegen 1.).

Wenn wir genau 5 Punkte wählen, und kein Punkt dreifach ausgewählt wird (weil ja (0,0) leer ist), dann werden 4 Punkte doppelt und einer einfach gewählt.
Wir finden dann immer 3 Punkte (einen doppelt), die auf einer Geraden liegen.
Wählen wir 6 oder mehr Punkte, dann gilt das gleiche, aber möglicherweise sind dann die drei Punkte auf einer Geraden sogar verschieden.

In {0,1,2}² können wir folglich nicht umhin, mit der Wahl von 9 Punkten, darunter mindestens 5 verschiedene, mindestens drei Punkte auf einer Geraden zu wählen, in deren Mitte ein Gitterpunkt liegt. Dieser Gitterpunkt ist aber der Schwerpunkt von x', y', z'.
Dies steht im Widerspruch zum Lemma 1.
QED