Schubfachprinzip

aus Wikipedia, der freien Enzyklopädie

In der Mathematik ist das Schubfachprinzip (engl. pigeonhole principle, daher auch Taubenschlagprinzip) eine einfache und effiziente Methode, um gewisse Aussagen über eine endliche Menge zu machen. Das Prinzip kann folgendermaßen formuliert werden:

Schubfachprinzip: 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. Im Russischen wird es daher auch „Dirichlet-Prinzip“ genannt.

Der Beweis dieses Prinzips ist beinahe trivial und kann zum Beispiel mittels Widerspruch 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.

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 nicht mehr als 1 Million Haare, damit gibt es maximal eine Million Schubfächer. 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 Personen. Diese haben nach Definition der Schubfächer dieselbe Anzahl Haare auf dem Kopf.

Dieses Prinzip wird oft in der diskreten Mathematik benutzt.

[Bearbeiten] Verwandte Themen

Mit kombinatorischen Verallgemeinerungen des Prinzips befasst sich die Ramseytheorie.