Schubfachprinzip

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

Das Prinzip kann informell folgendermaßen formuliert werden:

Falls man n Objekte auf m Mengen (n, m > 0) verteilt, und n größer als m ist, dann gibt es mindestens eine Menge, in der mehr als ein Objekt landet.

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 dieser Objekte.

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

Beweis[Bearbeiten]

Der Beweis dieses Prinzips ist beinahe trivial und kann zum Beispiel indirekt geführt werden: Falls das Prinzip nicht stimmt, dann landet in jedem 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[Bearbeiten]

Trotz seiner Einfachheit kann man mit dem Schubfachprinzip interessante 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,3 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.

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 zwei unter ihnen, deren Differenz eine zweistellige Zahl ist, deren beide Ziffern gleich sind. Beweis: Die Darstellung einer 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[Bearbeiten]

Eine „schärfere“ Fassung des Taubenschlagprinzips 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.

Beispiel der Verschärfung[Bearbeiten]

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

Verwandte Themen[Bearbeiten]

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

Literatur und Weblinks[Bearbeiten]