Diskussion:Schubfachprinzip

Mathematisches Beispiel

Das anschauliche Beispiel mit München ist ja nicht schlecht. Wie wäre es denn aber, wenn man etwas mathematisches damit beweist? Jobu0101 12:02, 19. Mär. 2008 (CET)

Was meinst du denn damit? Ich hätte folgendes Beispiel zu bieten:

Unter den Verbindungsstrecken zwischen fünf Punkten der Ebene mit ausschließlich ganzzahligen Koordinaten gibt es mindestens eine, deren Mittelpunkt ebenfalls ausschließlich ganzzahlige Koordinaten besitzt.

Beweis: Die Punkte der Ebene lassen sich in vier Mengen partitionieren:

$M_{1}=\left\{(x,y)|{\text{x und y sind gerade}}\right\}$

$M_{2}=\left\{(x,y)|{\text{x und y sind ungerade}}\right\}$

$M_{3}=\left\{(x,y)|{\text{x ist gerade und y ist ungerade}}\right\}$

$M_{4}=\left\{(x,y)|{\text{x ist ungerade und y ist gerade}}\right\}$

Nach dem Schubfachprinzip liegen in mindestens einer der vier Mengen mindestens zwei der fünf betrachteten Punkte. Seien also $P_{1}(x_{1},y_{1}),P_{1}(x_{2},y_{2})$ zwei dieser Punkte, die in der gleichen Menge liegen. Der Mittelpunkt der Strecke $P_{1}P_{2}$ hat dann die Koordinaten $\left({\frac {x_{1}+x_{2}}{2}},{\frac {y_{1}+y_{2}}{2}}\right)$. Da $x_{1}$ und $x_{2}$ entweder beide gerade oder beide ungerade sind, ist $x_{1}+x_{2}$ gerade und folglich ${\frac {x_{1}+x_{2}}{2}}$ ganzzahlig. Da dies analog auch für die y-Koordinate gilt, sind beide Koordinaten des Mittelpunktes ganzzahlig.

Was hältst du davon? Die Formulierung ist sicherlich noch verbesserungswürdig. --Daniel Mex 20:48, 19. Mär. 2008 (CET)

Ein anderes Beispiel: Gegeben sind 12 natürliche Zahlen n > 9 > 100. Zu beweisen ist: Darunter gibt es mindestens zwei Zahlen, deren Differenz aus 2 gleichen Ziffern besteht. BEWEIS: Man verteilt die 12 Zahlen auf 11 mögliche Restklassen, da die Differenz durch 11 teilbar sein soll. Dann haben mindestens zwei Zahlen dieselbe Restklasse (für mindestens 2 Zahlen n1 und n2 gilt: n1 mod 11 = n2 mod 11). Und es gilt: a =b(c) <=> c|(a-b). Daraus folgt: c = 11; c ist Teiler von a - b (bzw. hier n1 - n2 oder n2 - n1).

Grundsätzlich gerne. --217.224.163.32 17:36, 28. Jan. 2009 (CET)

n > 9 > 100? --Jobu0101 22:05, 13. Feb. 2012 (CET)

Warum kein richtiger Beweis?

Ich finde es etwas billig, hier und überall zu behaupten, der Beweis des Schubfachprinzips sei "trivial". Man definiert natürliche Zahlen ganz kunstvoll durch Verschachtelung von Mengenklammern und Benutzung der leeren Menge, aber beim Schubfachprinzip verzichtet man auf jede Rückführung auf "axiomatischere" Aussagen. Konkret: Das Schubfachprinzip wird regelmäßig nur indirekt bewiesen und gilt nicht ohne weiteres für unendliche Mengen (ob abzählbar oder überabzählbar). Ich finde diese Eigenheiten Anlass genug, einen formalen direkten Beweis anzugeben. Lässt sich in der Literatur denn so rein gar nichts finden? Ich kann das nicht glauben. --Stefan Neumeier (Diskussion) 11:28, 9. Jul. 2019 (CEST)

Der "triviale Beweis" ist strenggenommen auch gar keiner, da er rein anschaulich argumentiert. Einen formalen Beweis findet man z.B. in diesem Skript auf Seite 8. Das Schubfachprinzip findet sich übrigens auf der Liste der zum Induktionsprinzip äquivalenten Aussagen (neben z.B. dem Prinzip vom kleinsten Element oder der Methode des unendlichen Abstiegs). --80.187.100.205 21:48, 9. Apr. 2022 (CEST)