Schubfachprinzip

Schubfachprinzip

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 wird oft in der diskreten Mathematik benutzt. Es beschreibt eigentlich eine Selbstverständlichkeit.

Inhaltsverzeichnis

Das Prinzip

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

Beweis

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.

Beispiel

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.

Verschärfung des Prinzips

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

Verteilt man n Objekte auf k Mengen (n,k > 0) und ist dabei n > k, so gibt es mindestens eine Menge, in der sich mehr als \tfrac{n - 1}{k} Objekte befinden.

Beispiel der Verschärfung

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

Verwandte Themen

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

Literatur und Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно решить контрольную?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mathematische Beweismethode — Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit oder auch Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man… …   Deutsch Wikipedia

  • Mathematischer Beweis — Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit oder auch Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man… …   Deutsch Wikipedia

  • Mathematisches Beweisen — Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit oder auch Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man… …   Deutsch Wikipedia

  • Ramsey-Theorie — Die Ramseytheorie (nach Frank Plumpton Ramsey) ist ein Zweig der Kombinatorik innerhalb der Diskreten Mathematik. Sie behandelt die Frage, wie viele Elemente aus einer mit einer gewissen Struktur versehenen Menge ausgewählt werden müssen, damit… …   Deutsch Wikipedia

  • Beweis (Mathematik) — Ein Beweis ist in der Mathematik die als fehlerfrei anerkannte Herleitung der Richtigkeit oder auch Unrichtigkeit einer Aussage aus einer Menge von Axiomen, die als wahr vorausgesetzt werden, und anderen Aussagen, die bereits bewiesen sind. Man… …   Deutsch Wikipedia

  • Satz von Van der Waerden — Der Satz von Van der Waerden (nach Bartel Leendert van der Waerden) ist ein berühmter Satz aus der Kombinatorik, genauer aus der Ramseytheorie. Er besagt, dass für alle natürlichen Zahlen r und l eine natürliche Zahl N(r,l) existiert, so dass… …   Deutsch Wikipedia

  • Pigeonhole principle — A photograph of pigeons in holes. Here there are n = 10 pigeons in m = 9 holes, so by the pigeonhole principle, at least one hole has more than one pigeon: in this case, both of the top corner holes contain two pigeons. The principle says nothing …   Wikipedia

  • Additionssatz — Das Prinzip von Inklusion und Exklusion (auch Prinzip der Einschließung und Ausschließung oder Einschluss/Ausschluss Verfahren) ist eine hilfreiche Technik zur Bestimmung der Mächtigkeit einer Menge. Sie findet vor allem in der Kombinatorik und… …   Deutsch Wikipedia

  • Berry-Paradox — Das Berry Paradoxon (auch: Berry Paradox) ist ein selbstreferenzierendes Paradoxon, das sich aus dem Ausdruck „die kleinste ganze Zahl, die nicht durch eine gegebene Anzahl von Wörtern definierbar ist“ ergibt. Bertrand Russell, der sich als… …   Deutsch Wikipedia

  • Dirichletscher Schubfachschluss — 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 wird oft in der diskreten Mathematik …   Deutsch Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”