TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2023W/Beispiel 23

Wo steckt der Fehler im Induktions-”Beweis“ der folgenden Behauptung:

Ist in einer Gruppe von Personen eine Person blond, so sind alle blond.

Beweis:

a) $n=1$: Hier stimmt die Behauptung trivialerweise.

b) Die Behauptung gelte für Gruppen der Größe $n$. Nun sei von $n+1$ Personen eine blond. Man betrachte diese Person zusammenmit $n-1$ weiteren. Dann sind nach Induktionsannahme diese $n-1$ Personen auch blond. Folglich ist in der Gruppe dieser $n-1$ Personen zusammen mit der noch nicht betrachteten Personen wieder wenigstens eine blond, woraus folgt, daß auch diese letzte Person blond sein muss.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Hilfreiches

Das Beispiel ist eine Variante des "All horses are the same color"-Paradoxon. Sehr anschaulich hier erklärt: [1]

Vollständige Induktion

Vollständige Induktion

1. Induktionsanfang (IA)
2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) $\Rightarrow$ Induktionsbehauptung (IB)

Lösungsvorschlag von samuelp

Zuerst muss klargestellt werden wie der Beweis genau funktioniert.

Induktionsanfang $n=1$

Der Beweis meint, dass die Behauptung trivialerweise stimmt. Für $n=1$ bedeutet die Aussage, dass wenn eine Person bei einer Gruppe mit einer Person blond ist, dann alle blond sind. Das ist richtig, weil eben nur die eine Person in der Gruppe ist.

Induktionsschritt $n-1\rightarrow n$

Induktionshypothese: Falls eine Person in einer Gruppe von $n$ blond ist, dann sind alle blond

Induktionsbehauptung: Falls eine Person in einer Gruppe von $n+1$ blond ist, dann sind alle blond

Wir geben jeder der $n+1$ eine Nummer. Wir dürfen voraussetzen, dass eine Person blond ist. Diese bekommt die Nummer 1.

Die Induktionshypothese können wir auf jede Gruppe der Größe $n$ anwenden in der mindestens eine blonde Person ist.

Der Beweis geht in zwei Schritten vor.

1) Wir betrachten Personen mit Nummer 1 bis $n$. Auf diese Gruppe ist Induktionshypothese anwendbar. Diese besagt, dass alle Personen blond sind.

2) aus dem vorigen Schritt wissen wir das Person $n$ blond sein muss. Wir betrachten die Gruppe von Personen mit den Nummern 2 bis $n+1$. Da Person $n$ in dieser Gruppe ist und blond ist, kann die Induktionshypothese auf auf diese Gruppe angewendet werden.

Problem in diesem Beweis

Intuitiv schlägt der Beweis für $n+1=2$ (bzw. $n=1$) fehl.

Das einzige Problem mit dem Beweis oben ist die Aussage, dass Person mit der Nummer $n$ in der Gruppe der Personen 2 bis $n+1$ ist. Diese Gruppe enthält nur Person $n+1$ ($=2$) und Person $n$ ($=1$) eben nicht. Daher kann in dem Fall $n=1$ die Induktionshypothese im Schritt 2 nicht verwendet werden und es ist nicht möglich zu schießen, dass Person 2 auch blond sein muss.