Das Schubfachprinzip ist eine recht einfache mathematische Beweismethode, die auch auf eine Vielzahl von nicht-mathematischen Aussagen angewendet werden kann. Die Vorgehensweise des Prinzips ist denkbar einfach:
Das Schubfachprinzip
Werden n Objekte auf m Mengen verteilt, so enthält mindestens eine der Mengen mehr als ein Objekt, falls n > m gilt.
Eine anschauliche Erklärung lässt sich mit Hilfe des Namens geben:
Wenn n Objekte (z. B. Kugeln) auf m Schubfächer verteilt werden sollen, so enthält mindestens eines der Schubfächer mehr als eine Kugel, falls es mehr Objekte als Schubfächer gibt (n > m).
Der Beweis ist recht einfach beispielsweise per Reductio ad absurdum (Beweis durch Widerspruch) [Wikipedia] zu führen:
Beweis
Angenommen, das Schubfachprinzip wäre falsch. Bei der Verteilung von n Objekten auf m Mengen würde also in jeder Menge nur höchstens ein Objekt enthalten sein. Darauf folgt, dass es nur höchstens n Schubfächer geben kann. Dies ist ein Widerspruch zu der Aussage n > m, also muss das Schubfachprinzip richtig sein.
Die Anwendung ist wie gesagt vielzählig. So kann mittels Schubfachprinzip beispielsweise bewiesen werden, dass es in einem Dorf mit 200 Einwohnern mindestens 2 Einwohner gibt, die gleich alt sind. Die Anzahl der Schubfächer (= die Anzahl der verschiedenen Altersjahre) kann höchstens so groß sein wie das Alter des ältestesten Einwohners. Da es keinen Menschen gibt, der über 200 Jahre alt ist, muss es mehr Einwohner als Schubfächer geben und somit müssen zwei Einwohner gleich alt sein.
Genauso kann man zeigen, dass es unter 400 Menschen immer mindestens 2 gibt, die am selben Tag Geburtstag feiern. (m = 365, n = 400)
Der Leser ist herzlich dazu eingeladen, weitere Tatsachen zu suchen und finden, die sich mit Hilfe des Schubfachprinzips beweisen lassen und in einem Kommentar zu ergänzen.
Auch jegliche andere Art von Kommentaren ist wie immer gern gesehen.
Ich hätte noch ein weiteres Beispiel!
In der Stadt Berlin gibt es mehr Einwohner, als ein belieger Einwohner Haare auf dem Kopf hat (Es gibt keinen Einwohner mit 0 Haaren auf dem Kopf). Daraus kann man schließen, dass mindestens 2 Einwohner die selbe Anzahl an Haaren auf dem Kopf haben müssen!!!
ERKLÄRUNG mit SCHUBFACHPRINZIP:
Sagen wir mal es gibt 10 Einwohner in Berlin.
Schubfächer(m) = 9 [nämlich 1 Haar, 2 Haare, 3 Haare...9 Haare]
Objekte (n) = 10 [nämlivch die 10 Einwohner]
und da n > m ist muss es mindestens 2 Einwoner mit der gleichen Anzahl von Haaren geben, weil 10 Objekte auf 9 Schubfächer verteilt werden.
Habe absichtlich eine so kleine Zahl genommen. Natürlich hat Berlin viel mehr Einwohner und die Einwohner von Berlin auch weitaus mehr als 10 Haare oder weniger auf dem Kopf.
Hoffe es ist verständlich!!!!
Gruß Max
Hallo Max,
schönen Dank für dein Beispiel!
Die Erklärung ist richtig, du hast es genau verstanden.
Die Annahme, das es keinen Einwohner mit 0 Haaren auf dem Kopf gibt, kannst du sogar weglassen.
Dann wären die 9 Schubfächer die Anzahlen 0, 1, 2, …, 8 Haare.
Da die Einwohnerzahl Berlins mit über 3 Millionen (Quelle: http://de.wikipedia.org/wiki/Berlin) sehr viel größer ist, als die Anzahl der Haare eines Menschen (laut Wikipedia ungefähr 100.000 bis 150.000; http://de.wikipedia.org/wiki/Berlin) ist das ohne Probleme möglich.
Außerdem kann man, da die Einwohnerzahl so viel größer ist, sogar sagen, dass es mindestens 3 Menschen gibt, die gleichviele Haare auf dem Kopf haben. Übertreibt man das Ganze, erhält man sogar eine Mindestzahl von etwa 20 Menschen mit gleich vielen Haaren!
(3 Mio. geteilt durch 150000 ist 20)
Schöne Grüße,
Flo
Natürlich kannst du sagen es gibt auch Einwohner mit 0 Haaren. Nur dann
muss es nicht zwingend heißen, dass zwei Einwohner die selbe Anzahl an Haaren haben.
Lies dir noch einmal die Aufgabenstellung durch. Es soll mehr Einwohner geben als Haare auf dem Kopf eines beliebigen. Würde jetzt die 0 gelten, dann würde diese Ungleichung ja so aussehen:
10 > 0,1,2,3,4,5,6,7,8,9
Siehst du!!! rechts die 10 Einwohner und jeder eine andere Anzahl von Haaren. Desswegen habe ich die 0 ausgeschlossen und dann kann die Ungleichung ja nur so aussehen:
10 > 1,2,3,4,5,6,7,8,9,10
Diese stimmt aber nicht, denn 10 ist gleich der 10 auf der rechten Seite, aber es soll ja ungleich sein. Da kommt das SCHUBLADENPRINZIP in’s Spiel und die Ungleichung würde dann stimmen:
10 > 1,2,3,4,5,6,7,8,9,9
Hier kommt, es ist egal welche Zahl, zweimal vor.
Nun ja, klar kannst du 0 gelten lassen musst dann aber, wie oben erklärt die 8 als die höchste Anzahl an Haaren festlegen musst, damit man das SCHUBFACHPRINZIP anwenden kann!!!!!
Desswegen habe ich die 0 ausgeschlossen, weil ich sonst ja, wie du ja auch weißt und geschrieben hast, die 8 als ein Mximum hätte festlegen müssen!!!
Gruß,
Max
Hallo Max,
naja, die Ungleichungen sind formal nicht ganz richtig und ich kann nicht erkennen, was *genau* du damit meinst.
Trotzdem scheinst du verstanden zu haben, was ich meinte.
Welche Zahlen auf der linken Seite deiner Ungleichungen vorkommen ist vollkommen egal, es können ja schließlich auch andere (auch noch abstraktere) Objekte sein.
Worauf es ankommt ist einzig und allein die Anzahl der Dinge.
In diesem Fall sind das selbst Anzahlen, nämlich Anzahlen von Haaren auf dem Kopf.
Wenn du die 0 als Anzahl zulässt, dann ist die höchste Anzahl, die du zulassen kannst die 8, damit du 9 Objekte hast.
Wenn du die 1 nicht zulässt, sondern mit der 1 beginnst, dann erhöht sich die höchste mögliche Anzahl ebenso um 1, auf 9 nämlich.
Das macht jedoch in deinem Beispiel de facto keinen Unterschied, da – wie ich schon schrieb – die Anzahl der Einwohner nicht bloß um eins größer ist als die maximale Anzahl der Kopfhaare (was in dem Zahlenbeispiel der Fall ist), sondern zwanzigmal (!) so groß.
Grüße,
Flo
Hallo Florian,
wenn du nicht *genau* weißt was ich meine, dann möchte ich es nochmal
verdeutlichen, wie ich das meine.
Du hast bei Wikipedia herausgefunden, dass ein Mensch ca. 150.000
Haare hat. So, und was ist, wenn ich jetzt sage:,, Eine Stadt mit 150.000 Einwohnern…….”!?!?!
Hätte in dieser Stadt jeder eine unterschiedliche Anzahl an Haaren, dann müsste es 150.000 verschiedene positive ganze Zahlen geben, die kleiner sind als 150.000!!! Das ist natürlich NICHT möglich, es seidenn
die 0 wird mit einbezogen. Aus genau diesem Grund habe ich geschrieben,
dass es keinen Einwohner mit 0 Haaren gibt. Diesen Ansatz kann man auch als Rätsel verfassen, welches man mit dem Schubfachprinzip lösen kann. Das ist alles was ich meinte!!!
Gruß,
Max
Hallo Max,
danke für deine Erklärung, jetzt verstehe ich einigermaßen, was du sagen willst.
Natürlich kommt es auf die genaue Anzahl der Einwohner und die maximale Anzahl von Haaren an.
Wenn es 150.000 Einwohner sind und maximal 150.000 Haare, dann muss die Null (oder eine beliebige andere Zahl, die 0 scheint hier willkürlich) ausgeschlossen werden.
Das rechtfertigt jedoch keineswegs die Annahme, dass unter den 150.000 Einwohner keiner ist, der 0 Haare auf dem Kopf hat.
Außerdem hast du das Problem bei Ausschluß der 0 immernoch nicht gelöst; was, wenn ich dann sage: “Eine Stadt mit 149.998 Einwohnern… ” (oder gar nur 140.000)?
Gingest du weiter nach deinem Verfahren vor, dann wärest du gezwungen, noch eine Zahl auszuschließen, was ebenso wenig gerechtfertigt ist.
Würden wir weiter so fortfahren, erhieltest du am Ende vielleicht das Ergebnis, dass es in einer “Stadt” mit 2 Einwohnern, deren Haar-Anzahl genau 150.000 beträgt, mindestens 2 Einwohner gibt, die gleichviele Haare tragen.
Für diese Aussage muss nichteinmal das Schubfachprinzip angewandt werden.
Stattdessen könnte man auch einfach sagen, dass sich nicht beweisen lässt, dass es unter 150.000 Einwohner mindestens 2 mit gleicher Haar-Anzahl gibt.
Zurecht, denn es ist (bei wenigstens 0 und höchstens 150.000) durchaus möglich, dass unter 150.000 (und sogar bis zu 150.001) Einwohner keine sind, die dieselbe Anzahl an Haaren auf ihrem Kopf tragen.
Man sollte nicht zwanghaft versuchen, falsche Aussagen durch Einschränkungen beweisbar und richtig zu machen.
In deinem ersten Beispiel in dem es sich um Berlins Einwohner handelt, ist diese “Haarspalterei” ohnehin unnötig. Die Einwohnerzahl ist, wie schon erwähnt, genügend groß um die gewünschte Aussage treffen und beweisen zu können.
Du hast uns dennoch zu einer wichtigen Erkenntnis gebracht: Es lässt sich für nahezu jeden Schubfach-Beweis ein leicht abgewandeltes Beispiel finden, für das der Beweis und die Aussage ungültig sind.
Ändert man die Vorraussetzungen beliebig, so lassen sich alle Sätze und Beweise “widerlegen” – da es sich nicht mehr um den eigentlichen Fall handelt, sondern etwas ganz anderes.
Die Wahl deiner 150.000 Einwohner ist also recht willkürlich.
Grüße,
Flo
Hallo Florian,
alles was wir sagen ist richtig und es kommt nicht, wie du auch sagst,
auf eine gültige Aussage an, um das Schubfachhprinzip zu verdeutlichen.
Nur, dass ich diese beiden Einschränkungen gegeben habe liegt einzig und allein
daran, dass ich dies mal als ein Rätsel gelesen habe und
dort die Bedingung gegeben war, dass es mehr Einwohner als die max. Anzahl an
Haaren geben soll. Dies habe ich mit dem Schubfachprinzip gelöst, wenn man so
will.
Desswegen bin ich auch auf dieses Beispiel dafür gekommen.
In der Realität würde man natürlich nicht automatisch darauf schließen, da es
wie im Beispiel Berlin ca. 3 Mio. Einwohner gibt.
Auch bei einem Ort mit 150.000 Einwohnern würde man in der Realität nicht
automatisch darauf schließen können, weil ein Mensch ja höchsten 150.000 Haare
besitzt.
Wir haben uns also schon verstanden. Hoffe ich zumindest!!!
Ich habe ein weiteres Beispiel liefern können, wenn es auch in der Rubrik
Rätsel in deinem Blog erscheinen könnte (Auf Grund der Einschränkungen) :)
Grüße,
Max