TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 23

From VoWi
Jump to navigation Jump to search

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.

Hilfreiches[edit]

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[Bearbeiten, WP]
  1. Induktionsanfang (IA)
  2. Induktionsschritt (IS): Induktionsvoraussetzung (IV) \Rarr Induktionsbehauptung (IB)

Lösungsvorschlag von samuelp[edit]

Zuerst muss klargestellt werden wie der Beweis genau funktioniert.

Induktionsanfang n=1[edit]

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[edit]

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[edit]

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 auch 2 blond sein muss.