Schubfachprinzip

mathematischer Satz

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.

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

Das Prinzip

Bearbeiten

Das Prinzip kann informell folgendermaßen formuliert werden:

Falls man   Objekte auf   Mengen (mit  ) verteilt und   größer als   ist, dann wird mindestens eine Menge mehrere Objekte enthalten.[1]

bzw. äquivalent

Falls man   Objekte auf   Mengen verteilt und   kleiner als   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.

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

Bearbeiten

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.[2]

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

Bearbeiten

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

Verteilt man   Objekte auf   Mengen  , so gibt es mindestens eine Menge, in der sich zumindest   Objekte befinden  dabei bedeutet das Symbol   die kleinste ganze Zahl, welche größer oder gleich   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   Objekten.

Verwandte Themen

Bearbeiten

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

Bearbeiten

Einzelnachweise

Bearbeiten
  1. Albrecht Beutelspacher, Marc-Alexander Zschiegner: Diskrete Mathematik für Einsteiger: Bachelor und Lehramt. 5. erw. Auflage. Springer Fachmedien Wiesbaden, Wiesbaden 2014, ISBN 978-3-658-05781-7, S. 1–10.
  2. Manon Bischoff: Die fabelhafte Welt der Mathematik: Das einfachste Theorem der Welt. In: Spektrum.de. 3. März 2023, abgerufen am 6. August 2023.