Induktionsbeweis Schubfachprinzip (einfacher Fall)

Question

\(n+1\) Kugeln auf \(n\) Fächer verteilen. Dann gibt es einfach mit mindestens \(2\) Kugeln.

Allgemein (mit Induktion) zeigen (kein Widerspruchsbeweis, weil man die Induktion nicht hinbekommt).

Danke.

Comments

Dann gibt es 1 fach mit mindestens 2 kugeln.

Eine Existenzbehauptung schreit nach einem indirekten Beweis.

---

und meine frage schreit nach einem induktionsbeweis.,

---

Du musst die Sache erst mal in einen formalen Rahmen packen. Sonst faellt es schwer, ueberhaupt zu erkennen, was bewiesen werden soll. Denn eigentlich ist die Sache sonnenklar.

Vorschlag: Modelliere das Verteilen der Kugeln auf die Faecher durch eine Funktion \(f:\{1,2,\ldots ,n+1\}\to\{1,2,\ldots,n\}\). Die Behauptung lautet dann: \(f\) ist für kein \(n\) injektiv. Das kannst Du jetzt beweisen, wie Du magst.

---

(keine Widerspruchsbeweis, weil man die induktion nicht hinbekommt)

Man nimmt hier einen indirekten Beweis, weil es einer der schnellsten und einfachsten Wege ist. Warum bestehst du hier auf diese unsinnige Induktion? Welche zusätzliche Erkenntnis erwartest du dir davon denn bitte?

---

Ich stimme meinen Vorrednern zu: Das mit Induktion beweisen zu wollen ist vergleichbar mit den bekannten Kanonen, mit denen man auf Spatzen schießt. Du kannst notfalls den Gedankengang von Fakename aufgreifen und damit weiterarbeiten.

PS: Es hilft nicht unbedingt, ehrenamtlichen Helfer mit Worten wie

Kriegs Du denn den einfachen fall mit induktion hin?

zu begegnen!

Answer 1

Induktion geht auch recht einfach. Im Induktionsschritt haetten wir eine Funktion \(\widetilde{f}:\{1,2,\ldots,n+1,n+2\}\to\{1,2,\ldots,n,n+1\}\) zu untersuchen. Man kann annehmen, dass es hoechstens ein \(x\in\{1,2,\ldots,n+1,n+2\}\) mit \(\widetilde{f}(x)=n+1\) gibt, denn sonst waere \(\widetilde{f}\) nicht injektiv und nichts weiter zu beweisen. Weiterhin kann man o.B.d.A. annehmen, dass \(x=n+2\) ist (sonst wuerde man halt umnummerieren). Es bleibt dann noch, eine Funktion \(f:\{1,2,\ldots,n+1\}\to\{1,2,\ldots,n\}\), \(x\mapsto\widetilde{f}(x)\) zu betrachten. Und auf die kann man die Induktionsvoraussetzung anwenden. \(f\) ist nicht injektiv und \(\widetilde{f}\) also auch nicht.