n Personen im Raum : Gegenbeweis einer vollständigen Induktion

28.10.2009, 20:14

Induktionsherd

n Personen im Raum : Gegenbeweis einer vollständigen Induktion

Hallo Leute,

folgende Aufgabe kennt ihr bestimmt alle schon:

Zitat:

Wir beweisen mittels vollständiger Induktion: Sind n Personen in einem Raum, so haben alle dasselbe Geschlecht. Da dies wohl nicht sein kann, besteht Ihre Aufgabe darin, den Fehler im folgenden Beweis zu finden. Beweis: Induktionsanfang n = 1 ist klar. Induktionsschritt n ! n + 1 : Die Aussage sei wahr fuer n. Sind nun n + 1 Personen in einem Raum, so wähle eine Person aus und schicke sie hinaus. Nach Induktionsvoraussetzung haben die im Raum gebliebenen n Personen alle das gleiche Geschlecht. Wir holen die hinausgegangene Person wieder herein und schicken eine andere Person hinaus. Dann hat (wieder nach Induktionsvoraussetzung) die zuerst hinausgeschickte Person dasselbe Geschlecht wie alle anderen im Raum befindlichen Personen. Da dies nach dem ersten Beweisschritt auch fuer die als zweite hinausgesandte Person zutrifft, haben also alle n+1 Personen dasselbe Geschlecht.

Ich knoble jetzt schon eine Weile rum, aber komme einfach nicht drauf, wie man diese Aussage logisch begründen kann.

Der Induktionsanfang ist mir auch klar.
Wähle nun $\begin{eqnarray*} n = 1 \end{eqnarray*}$ , würde das ja heißen, ich habe $\begin{eqnarray*} n + 1 = 2 \end{eqnarray*}$ Personen in einem Raum. Eine davon geht hinaus, die übrige hat dann "ihr" Geschlecht, klar. (siehe Induktionsvorraussetzung). Die Person, die draußen war, kommt wieder rein, die andere geht raus, dann hat die Person im Raum wieder dasselbe Geschlecht aller anderen Personen im Raum (also sein Eigenes). Das ist auch logisch. (Oder nicht??)

Beim Streifzug durchs WWW habe ich aber schon mehrfach gelesen, dass der Schluss von $\begin{eqnarray*} n \end{eqnarray*}$ auf $\begin{eqnarray*} n+1 \end{eqnarray*}$ nur für $\begin{eqnarray*} n\geq 2 \end{eqnarray*}$ gilt.

Das ist mir aber nicht ganz so logisch. Kann mir vielleicht jemand weiterhelfen? Oder mir einen Tipp geben?

Tausend Dank!

29.10.2009, 00:04

gonnabphd

Auf diesen Beitrag antworten »

Das Problem ist, dass du beim Induktionsschritt verwendest, dass 2 verschiedene Personen aus dem Raum entfernt werden. Das ist jedoch nur möglich, wenn $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ ist.

Also hilft der Induktionsanfang für n=1 nicht weiter. Es müsste für n=2 bewiesen werden.
Also: Wenn zwei Personen in einem Raum sind, so haben beide das gleiche Geschlecht. Und dies ist offensichtlich falsch.

29.10.2009, 00:10

gonnabphd

Auf diesen Beitrag antworten »

Um's evtl. noch ein bisschen besser verständlich zu machen:

Zitat:

Original von Induktionsherd
Eine davon geht hinaus, die übrige hat dann "ihr" Geschlecht, klar. (siehe Induktionsvorraussetzung). Die Person, die draußen war, kommt wieder rein, die andere geht raus, dann hat die Person im Raum wieder dasselbe Geschlecht aller anderen Personen im Raum (also sein Eigenes). Das ist auch logisch. (Oder nicht??)

Hier benutzt du, dass für n=1 die Aussage stimmt + den Induktionsschritt, um n=2 zu beweisen. Was wie oben gesagt, unzulässig ist.

29.10.2009, 07:28

tmo

Auf diesen Beitrag antworten »

Genau dassselbe nur mit Außerirdischen Augenzwinkern

http://www.matheboard.de/thread.php?threadid=399494

29.10.2009, 08:47

Induktionsherd

Auf diesen Beitrag antworten »

Zitat:

Original von gonnabphd
Das Problem ist, dass du beim Induktionsschritt verwendest, dass 2 verschiedene Personen aus dem Raum entfernt werden. Das ist jedoch nur möglich, wenn $\begin{eqnarray*} n \geq 2 \end{eqnarray*}$ ist.

Also hilft der Induktionsanfang für n=1 nicht weiter. Es müsste für n=2 bewiesen werden.
Also: Wenn zwei Personen in einem Raum sind, so haben beide das gleiche Geschlecht. Und dies ist offensichtlich falsch.

Dankeschön. Lansgam wird's mir klarer, aber der endgültige Aha-Effekt fehlt leider noch.

Wenn ich n = 1 Personen im Raum habe, dann sei diese Person, Person A, dann stimmt die Induktionsvorraussetzung.

Wenn ich nun n = 2 Personen im Raum habe, dann seien das Person A und Person B.

Ich schicke Person B raus, A verbleibt, und lt. Induktionsstart hat sie dasselbe Geschlecht (klar). Wenn B wieder rein kommt, un A rausgeht, dann stimmt der Induktionsstart wiederum. Also ist n + 1 bewiesen.

Das stimmt, oder? Aber wenn ich "weniger" Personen hab, wirds laut euren Antworten nicht mehr klappen, oder? Hm :-/ Ich versteh's grad echt nicht.

Vielleicht noch ein Tipp mit Anleitung für Deppen ;-))

Dank!

29.10.2009, 10:21

Manus

Auf diesen Beitrag antworten »

Das Problem ist folgendes:

Mal angenommen die Aussage gilt für n=2 und wir wollen sie jetzt für n=3 zeigen.

Es stehen also 3 Leute im Raum. Eine wird herausgeschickt (Person a), die restlichen haben jetzt nach Voraussetzung das gleiche Geschlecht. Die Person a kommt wieder herein und eine andere (Person b) geht raus. Wieder 2 Leute wieder alle das gleiche Geschlecht.

Und damit haben alle 3 das gleiche Geschlecht, denn Person a hat das gleiche Geschlecht wie Person c (die immer im Raum verbleibende) und Person b hat das gleiche Geschlecht wie Person c. Also alle 3 das gleiche Geschlecht. Der Schritt funktioniert also, weil wir eine Mittelsperson (c) im Raum haben, über die wir das Geschlecht der Personen, die nicht zusammen im Raum waren vergleichen können.

Von 1 auf 2 funktioniert der Schritt aber nicht, denn wir haben immer nur eine Person im Raum und können so die Geschlechter beider Personen gar nicht in Beziehung setzen.

29.10.2009, 13:13

Induktionsherd

Auf diesen Beitrag antworten »

Zitat:

Original von Manus
Das Problem ist folgendes:

Mal angenommen die Aussage gilt für n=2 und wir wollen sie jetzt für n=3 zeigen.

Es stehen also 3 Leute im Raum. Eine wird herausgeschickt (Person a), die restlichen haben jetzt nach Voraussetzung das gleiche Geschlecht. Die Person a kommt wieder herein und eine andere (Person b) geht raus. Wieder 2 Leute wieder alle das gleiche Geschlecht.

Und damit haben alle 3 das gleiche Geschlecht, denn Person a hat das gleiche Geschlecht wie Person c (die immer im Raum verbleibende) und Person b hat das gleiche Geschlecht wie Person c. Also alle 3 das gleiche Geschlecht. Der Schritt funktioniert also, weil wir eine Mittelsperson (c) im Raum haben, über die wir das Geschlecht der Personen, die nicht zusammen im Raum waren vergleichen können.

Von 1 auf 2 funktioniert der Schritt aber nicht, denn wir haben immer nur eine Person im Raum und können so die Geschlechter beider Personen gar nicht in Beziehung setzen.

Wow, danke! Das hat mir sehr weitergeholfen!

Wäre auch dieser Ansatz richtig?

Ich teste meine Aussage für n = 2.
Ich habe 2 Personen in einem Raum, eine geht raus, Rest hat "gleiches" Geschlecht. Jetzt kommt die eine Person wieder rein, aber ich darf die Person, die immer im Raum war nicht rausschicken, weil sonst meine Vorrassetzung nicht mehr gilt (die Person im Raum entspricht quasi meinem "n").
Also muss ich wieder die zweite Person, die schon draußen war, rausschicken und das widerspricht ja meinem Beweis.

Deshalb brauche ich mind. 2 Personen, um meinen Beweis verifizieren zu können.

Habe ich aber 2 Personen als n, so lautet meine neuer Induktionsanfang
"Sind 2 Personen in einem Raum, so haben alle dasselbe Geschlecht."

Und das ist ja ganz offensichtlich falsch.

So hab ich mir das ausgedacht, wobei, wenn ich deinen Vorschlag lese, dieser wesentlich logischer klingt. Aber Not (und Abgabefristen!!) machen eben erfinderisch ;-)

Danke nochmal!

Neue Frage »

Antworten »

n Personen im Raum : Gegenbeweis einer vollständigen Induktion

Verwandte Themen