Schubfachprinzip

Ein Taubenschlag mit $n=10$ Tauben in $m=9$ Sitzen: Weil 10 größer als 9 ist, besagt das Taubenschlagprinzip, dass auf mindestens einem Sitz mehr als eine Taube sitzt.

In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache, intuitive und oftmals hilfreiche Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip wird oft in der diskreten Mathematik verwendet.

Das Prinzip

Das Prinzip kann informell folgendermaßen formuliert werden:

Falls man $n$ Objekte auf $m$ Mengen (mit $m>0$) verteilt und $n$ größer als $m$ ist, dann wird mindestens eine Menge mehrere Objekte enthalten.

bzw. äquivalent

Falls man $n$ Objekte auf $m$ Mengen verteilt und $n$ kleiner als $m$ ist (und die Mengen disjunkt sind, also jedes Objekt nur einer Menge angehört), dann bleibt mindestens eine dieser Mengen leer.

Der Name kommt von einer bildhaften Vorstellung dieses Vorgangs: Falls man eine bestimmte Anzahl von Schubfächern hat, und man mehr Objekte in die Fächer legt als Fächer vorhanden sind, dann landen in irgendeinem Schubfach mindestens zwei Objekte.

Es geht wahrscheinlich auf Peter Dirichlet zurück, der es 1834 angewandt hat. In vielen Sprachen (z. B. Bulgarisch, Tschechisch, Dänisch, Isländisch, Kasachisch, Lettisch, Polnisch, Rumänisch und Russisch) wird es daher auch „Dirichlet-Prinzip“ genannt.

Beweis

Der Beweis dieses Prinzips ist trivial und kann zum Beispiel indirekt geführt werden: Falls das Prinzip nicht stimmt, dann enthält jedes Schubfach höchstens ein Objekt. Damit gibt es höchstens so viele Objekte wie Schubfächer. Das steht aber im Widerspruch zur Voraussetzung, dass es mehr Objekte als Schubfächer gibt.

Beispiele

Trotz seiner Einfachheit kann man mit dem Schubfachprinzip bestimmte Aussagen treffen, zum Beispiel die, dass es in München mindestens zwei Personen gibt, die exakt dieselbe Anzahl von Haaren auf dem Kopf haben. Beweis: Man teilt alle Bewohner Münchens nach der Anzahl ihrer Haare in „Schubfächer“ ein. Typischerweise hat der Mensch etwa 100.000 bis 200.000, jedoch sicher weniger als 1 Million Haare, damit gibt es maximal eine Million Schubfächer (von 0 bis 999.999). Da es aber etwa 1,4 Millionen Einwohner in München gibt, hat man mehr Einwohner als Schubfächer, damit landen in mindestens einem Schubfach zwei oder mehr Personen. Diese haben nach Definition der Schubfächer dieselbe Anzahl Haare auf dem Kopf. Das Schubfachprinzip sagt jedoch nichts darüber aus, welches Schubfach zwei oder mehr Personen enthält, es besagt nur, dass es ein solches Schubfach gibt.

Ein weiteres Beispiel ist die Aussage, dass in einer Gruppe von 13 Personen mindestens zwei im selben Monat Geburtstag haben (weil es nur 12 Monate gibt).

Ein weiteres, etwas komplexeres Beispiel, bei dem das Schubfachprinzip verwendet wird, ist folgendes: Wählt man zwölf paarweise verschiedene zweistellige Zahlen, so gibt es mindestens zwei unter ihnen, deren Differenz eine zweistellige Zahl ist, deren beide Ziffern gleich sind. Beweis: Die Darstellung einer zweistelligen Zahl, die ein Vielfaches von Elf ist, besteht aus zwei gleichen Ziffern. Nun überlegt man, welche Reste die Division einer Zahl durch 11 ergeben kann (siehe Restklasse). Es ergibt sich, dass die Zahlen 0 bis 10 die möglichen Reste sind. Wenn zwei Zahlen denselben Rest lassen, ist ihre Differenz ein Vielfaches von 11. Es gibt also 11 „Schubfächer“, aber 12 zweistellige Zahlen, die darauf verteilt werden. Nach dem Schubfachprinzip befinden sich in einem Fach also zwei Zahlen; wie oben erklärt, ist ihre Differenz ein Vielfaches von 11, hat also die gewünschte Form.

Verschärfung des Prinzips

Eine „schärfere“ Fassung des Schubfachprinzips lautet wie folgt:

Verteilt man $n$ Objekte auf $k$ Mengen $(n,k>0)$, so gibt es mindestens eine Menge, in der sich zumindest $\lceil {\tfrac {n}{k}}\rceil$ Objekte befinden $($dabei bedeutet das Symbol $\left\lceil {\tfrac {n}{k}}\right\rceil$ die kleinste ganze Zahl, welche größer oder gleich ${\tfrac {n}{k}}$ ist$)$.

Beispiel der Verschärfung:

Damit kann man jetzt beweisen, dass es mindestens 82 Einwohner Deutschlands mit gleicher Haaranzahl gibt, wenn man voraussetzt, dass es in Deutschland mindestens 81.000.001 Einwohner gibt und alle weniger als 1.000.000 Haare besitzen: Wir verteilen 81.000.001 Objekte (Einwohner) auf 1.000.000 Mengen (die die Haaranzahl ihrer Elemente [Objekte] wiedergeben), also gibt es mindestens eine Menge mit mindestens $\left\lceil {\tfrac {81.000.001}{1.000.000}}\right\rceil =\lceil 81{,}000\,001\rceil =82$ Objekten.

Verwandte Themen

Mit kombinatorischen Verallgemeinerungen des Prinzips befasst sich die Ramseytheorie, siehe z. B. Satz von van der Waerden.

Literatur und Weblinks

• Martin Aigner, Günter M. Ziegler: Das BUCH der Beweise, Berlin (Springer) 2002
• Pigeon Principle bei cut-the-knot (engl.; mit math. Beispielen)
• Daniel Schwenter: Zu erweisen daß es wol müglich/ja auch seyn müsse/daß vnter zweyen Menschen einer so viel Haar an seinem Leib habe/als der ander in Deliciæ physico-mathematicæ, Nürnberg 1636, S. 86