Schubfachprinzip

aus Wikipedia, der freien Enzyklopädie

In der Mathematik ist das Schubfachprinzip 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.

Im Englischen wird dieses Prinzip pigeonhole principle („Taubenschlagprinzip“) genannt. Dieses Prinzip geht wahrscheinlich auf Dirichlet zurück, der es 1834 angewandt hat. Manchmal (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 soviele Objekte wie Schubfächer. Das steht aber im Widerspruch zur Annahme, 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 London mindestens zwei Personen gibt, die die gleiche Anzahl von Haaren auf dem Kopf haben. Beweis: Man teilt alle Bewohner Londons nach der Anzahl ihrer Haare in "Schubfächer" ein. Typischerweise hat der Mensch nicht mehr als 1 Million Haare, damit gibt es maximal eine Million Schubfächer. Da es aber über 7 Millionen Einwohner dort gibt, hat man mehr Einwohner als Schubfächer, damit landen in mindestens einem Schubfach zwei Personen. Diese haben nach Definition der Schubfächer die gleiche Anzahl Haare auf dem Kopf.

Etwas wissenschaftlicher wird dieses Prinzip oft in der diskreten Mathematik benutzt.

[Bearbeiten] Verwandte Themen

Mit kombinatorischen Verallgemeinerungen des Prinzips befasst sich die Ramsey-Theorie.