[Rätsel] Die blauäugigen Insulaner

xkcd hat das ganze auch:
http://www.xkcd.com/blue_eyes.html
(achtung, lösung):
http://xkcd.com/solution.html

ich bin ehrlich gesagt nicht drauf gekommen.

empgodot

SeppJ schrieb:

Angenommen, es gäbe einen Insulaner mit blauen Augen, dann wüsste er sofort, dass er es ist und müsste sich umbringen.

Angenommen, es gäbe zwei mit blauen Augen. Dann wüssten beide von ihnen, dass es noch einen anderen mit blauen Augen gibt und würden erwarten, dass dieser eine sich umbringen müsste. Da er es nicht tut, müssen sie folgern, dass sie selbst auch blaue Augen haben, da es zwei Blauäugige gibt und sie nur einen sehen können. Die Braunäugigen können zwei Blauäugige sehen und können daher nicht diesen Schluss ziehen.

Und so weiter mit 3.

Sicher, dass das nach dem gleichen Muster weitergeht? Bei 3 Leuten sieht ja der erste, dass es mindestens zwei Blauäugige gibt. Der dritte setzt aber für die Hypothese mit zwei blauäugigen Insulanern voraus, dass der erste sich umbrächte, wenn er merkte, dass er der einzige ist. Dafür müsste der erste aber davon ausgehen, dass es nur einen Blauäugigen gibt und das ist bei 3 Leuten nicht mehr der Fall.

SeppJ

empgodot schrieb:

SeppJ schrieb:

Angenommen, es gäbe einen Insulaner mit blauen Augen, dann wüsste er sofort, dass er es ist und müsste sich umbringen.

Angenommen, es gäbe zwei mit blauen Augen. Dann wüssten beide von ihnen, dass es noch einen anderen mit blauen Augen gibt und würden erwarten, dass dieser eine sich umbringen müsste. Da er es nicht tut, müssen sie folgern, dass sie selbst auch blaue Augen haben, da es zwei Blauäugige gibt und sie nur einen sehen können. Die Braunäugigen können zwei Blauäugige sehen und können daher nicht diesen Schluss ziehen.

Und so weiter mit 3.

Sicher, dass das nach dem gleichen Muster weitergeht? Bei 3 Leuten sieht ja der erste, dass es mindestens zwei Blauäugige gibt. Der dritte setzt aber für die Hypothese mit zwei blauäugigen Insulanern voraus, dass der erste sich umbrächte, wenn er merkte, dass er der einzige ist. Dafür müsste der erste aber davon ausgehen, dass es nur einen Blauäugigen gibt und das ist bei 3 Leuten nicht mehr der Fall.

Denk dran, dass alle Insulaner perfekte Logiker sind und alle wissen, dass alle perfekte Logiker sind:

1. Ist es ein Blauäugiger, weiß er am ersten Tag, dass er es ist, denn er sieht keine anderen Blauäugigen. Am zweiten Tag bringt er sich um.

2. Sind es zwei Blauäugige, so merken sie am zweiten Tag, dass sie beide blauäugig sind, denn da der jeweils andere sich am zweiten Tag nicht umgebracht hat, muss er noch mindestens anderen Blauäugigen sehen (sonst hätte er sich nach 1. heute umgebracht (da er perfekter Logiker ist)). Da man selber nur einen Blauäugigen sieht, muss man selbst der zweite Blauäugige sein. Sie bringen sich am dritten Tag um.

3. Sind es drei Blauäugige, so merken sie am dritten Tag, dass sie alle drei blauäugig sind, denn da die zwei anderen sich am dritten Tag nicht umgebracht haben, muss es noch mindestens anderen Blauäugigen geben (sonst hätten die beiden sich nach 2. heute umgebracht (da sie perfekte Logiker sind)). Da man selber nur zwei Blauäugige sieht, muss man selbst der dritte Blauäugige sein. Die drei bringen sich am vierten Tag um.

...

N. Sind es N Blauäugige, so merken sie am N. Tag, dass sie alle N blauäugig sind, denn da die N-1 anderen sich am N. Tag nicht umgebracht haben, muss es noch mindestens anderen Blauäugigen geben (sonst hätten die N sich nach N-1. heute umgebracht (da sie perfekte Logiker sind)). Da man selber nur N-1 Blauäugige sieht, muss man selbst der N. Blauäugige sein. Die N bringen sich am N+1. Tag um.

Perfekte Induktion. Der Reisende liefert dabei den Fixpunkt ab dem alle anfangen können zu zählen.

PRIEST

Hab ich was nicht verstanden? Was passiert wenn man was falsches sagt? Nix? Hab ich das überlesen?

Bashar

SeppJ schrieb:

Perfekte Induktion. Der Reisende liefert dabei den Fixpunkt ab dem alle anfangen können zu zählen.

Das mit dem Fixpunkt finde ich nicht überzeugend. Warum zählen sie nicht sowieso schon die ganze Zeit, wenn das solche perfekten Logiker sind?
Angenommen, der Reisende hätte zum Abschied etwas anderes gesagt, z.B. "Hier hat ja niemand rote Augen.", würde das nicht auch einen Fixpunkt setzen?

SeppJ

PRIEST schrieb:

Hab ich was nicht verstanden? Was passiert wenn man was falsches sagt? Nix? Hab ich das überlesen?

Du meinst wenn der Reisende sagt, dass es mindestens einen Grünäugigen gibt? Dann bringen sich am nächsten Tag alle um.

Ich glaube die Falschaussage soll bei der Aufgabenstellung aber dadurch ausgeschlossen werden, dass der Reisende das Vertrauen der Eingeborenen genießt. Außerdem ist die Aussage 'es gibt mindestens 1 Blauäugigen' für die Eingeborenen erwiesenermaßen richtig, denn sie alle sehen 99 oder 100 Blauäugige. Er liefert durch die Aussage nur einen gemeinsamen Bezugspunkt.

SeppJ

Bashar schrieb:

SeppJ schrieb:

Perfekte Induktion. Der Reisende liefert dabei den Fixpunkt ab dem alle anfangen können zu zählen.

Das mit dem Fixpunkt finde ich nicht überzeugend. Warum zählen sie nicht sowieso schon die ganze Zeit, wenn das solche perfekten Logiker sind?
Angenommen, der Reisende hätte zum Abschied etwas anderes gesagt, z.B. "Hier hat ja niemand rote Augen.", würde das nicht auch einen Fixpunkt setzen?

Diese Aussage alleine würde nichts verändern. Selbst wenn er sagen würde 'alle haben blaue oder braune Augen' würde sich nichts ändern. Die genaue Art der Aussage ist schon wichtig.

Und sie zählen nicht die ganze Zeit, weil sie keinen gemeinsamen Bezugspunkt haben. Es wird ja nie über Augenfarben gesprochen.

SeppJ schrieb:

FierFachF schrieb:

SeppJ schrieb:

P.S.: Hilft doch immer bei solchen Rätseln, die Extremfälle zu betrachten, dann fällt die Lösung oft leichter. Athars Bemerkung war auch hilfreich, auch wenn meine Interpretation genau gegenteilig ist .

Und wo ist jetzt ein Fehler, in Athars Argumentation oder in deiner?

Gute Frage, ich möchte ja mal Gregor abwarten, was er sich für eine Lösung denkt. Und ob dies zu meiner Lösung passt.

Aber so sehe ich das:
Athar sagte, es macht keinen Unterschied, da die Blauäugigen schon vorher wussten, dass es 99 oder 100 Blauäugige gibt und die Braunäugigen wussten schon vorher, dass es 100 oder 101 Blauäugige gibt. Und die Information, dass es mindestens 1 gibt, wäre daher nichts neues. Das ist auch richtig. Es ist aber der Unterschied zwischen dem Wissen der Blauäugigen und Braunäugigen den Athar hier nebenbei erwähnt hat, der mich auf die Lösung gebracht hat.
Die neue Information die der Reisende demnach gegeben hat ist, dass es 100 Tage nach seiner Abreise mindestens 100 Blauäugige geben muss, wodurch der Unterschied im Wissen der Blauäugigen und Braunäugigen auf einmal relevant wird.

Das ist mir, in Verbindung mit http://en.wikipedia.org/wiki/Common_knowledge_(logic), einigermaßen klar. Was mir immer noch nicht klar ist: Was ist der Wissensgewinn der Inselbewohner in dem Moment in dem der Besucher diesen Satz sagt? D.h. welche Aussage war vorher nicht sichergestellt, nachher aber schon?

Jeder wusste vorher, dass es einen Blauäugigen gibt.
Jeder wusste vorher, dass jeder wusste, dass es einen Blauäugigen gibt.
u.s.w., da jeder wusste dass es mehr als einen Blauäugigen gibt.

no_code

FierFachF schrieb:

D.h. welche Aussage war vorher nicht sichergestellt, nachher aber schon?

Jeder wusste, dass jeder wusste, dass es blauäugige gibt.

@edit wow 3* ist schon ein stück...

SeppJ

FierFachF schrieb:

D.h. welche Aussage war vorher nicht sichergestellt, nachher aber schon?

Ich würde es formulieren als: "Jeder wusste, dass ein einzelner Blauäugiger sich am Tag danach würde umbringen müssen". Das ist der Induktionsanfang. Daraus folgt dann mit Hilfe des Induktionsschrittes, dass bei N Blauäugigen diese sich am N. Tag danach umbringen müssen.

Vorher war zwar der Induktionsschritt bekannt (da er rein logisch ist), aber es gab keinen Anfang für die Induktionskette, da es keinen Grund für einen einzelnen Blauäugigen gab, sich umzubringen.

TyRoXx

Warum sollte sich da jemand umbringen, es hat doch niemand etwas Neues erfahren? Jeder konnte schon lange mehrere Blauäugige sehen und jetzt bringen sich plötzlich alle um, nur weil ein Reisender das Bekannte noch einmal erwähnt?

TyRoXx schrieb:

Warum sollte sich da jemand umbringen, es hat doch niemand etwas Neues erfahren? Jeder konnte schon lange mehrere Blauäugige sehen und jetzt bringen sich plötzlich alle um, nur weil ein Reisender das Bekannte noch einmal erwähnt?

jop. alles andere ist glaub ich ein typischer fall von überverkomplizierung.

Bashar

TyRoXx schrieb:

Warum sollte sich da jemand umbringen, es hat doch niemand etwas Neues erfahren? Jeder konnte schon lange mehrere Blauäugige sehen und jetzt bringen sich plötzlich alle um, nur weil ein Reisender das Bekannte noch einmal erwähnt?

Was jeder wusste:

Es gibt blauäugige.
Jeder weiß, dass es blauäugige gibt.
Jeder weiß, dass jeder weiß, dass es blauäugige gibt.
...
Jeder weiß, dass ... jeder weiß, dass es blauäugige gibt.

Was nicht jeder wusste:
100) Noch einmal "jeder weiß, dass" mehr.

Das ist die neue Information.

Bashar schrieb:

TyRoXx schrieb:

Warum sollte sich da jemand umbringen, es hat doch niemand etwas Neues erfahren? Jeder konnte schon lange mehrere Blauäugige sehen und jetzt bringen sich plötzlich alle um, nur weil ein Reisender das Bekannte noch einmal erwähnt?

Was jeder wusste:

Es gibt blauäugige.

Jeder weiß, dass es blauäugige gibt.

Jeder weiß, dass jeder weiß, dass es blauäugige gibt.
...

Jeder weiß, dass ... jeder weiß, dass es blauäugige gibt.

Was nicht jeder wusste:
100) Noch einmal "jeder weiß, dass" mehr.

Das ist die neue Information.

Wie kommst du darauf? Die Aussage des Besuchers impliziert in keinster weiße dass es nen neuen gibt. Für die Leute ist immernoch nicht bekannt wie viele blauäugige es gibt. Ein Blauäugiger sieht immernoch 99 andere mit blauen Augen, mit oder ohne der Aussage des Touristen. Da er weiß, dass die anderen genauso denken wie er, muss er sich auch nicht umbringen, da weder sie noch er selbst sich sicher sein können welche Augenfarbe sie haben, d.h. sie müssen sich nicht umbringen.

Stell dir vor du guggst durch nen Tunnel und am Ende siehst du 2 Autos, und du weißt dass die Möglichkeit besteht dass da draußen noch mehr Autos stehen, muss aber nicht so sein. Jetzt kommt ein Mann am Ende des Tunnels und sagt "Ui hier gibts ja Autos". Was hat sich jetzt geändert? nichts.

SeppJ

Vergesst die logischen Schlussfolgerungen nicht!

Jeder weiß:
Es gibt Blauäugige, denn jeder sieht sie.

Jetzt kommt "neue" Information:
Es gibt Blauäugige. Und dies weiß nun jeder, ob er welche sieht oder nicht.

Daraus folgt: Ein Einzelner Blauäugiger müsste sich nun umbringen.

Daraus folgt: Zwei Blauäugige müssten sich etwas später umbringen.

...

Daraus folgt 100 Blauäugige müssen sich gut drei Monate später umbringen.

TyRoXx

SeppJ schrieb:

Daraus folgt 100 Blauäugige müssen sich gut drei Monate später umbringen.

Aber dadurch weiß der Einzelne doch nicht, welche Augenfarbe er hat. Oder anders: 100 von 1000 sollten sich umbringen, aber keiner der 100 weiß, dass er gemeint ist. Sich bei 10%iger Erfolgswahrscheinlichkeit umzubringen klingt nicht so logisch.

Bashar

TravisG schrieb:

Bashar schrieb:

Was nicht jeder wusste:
100) Noch einmal "jeder weiß, dass" mehr.

Das ist die neue Information.

Wie kommst du darauf? Die Aussage des Besuchers impliziert in keinster weiße dass es nen neuen gibt.

neuen was? Ich hab nichts dergleichen behauptet.

Bashar

TyRoXx schrieb:

Aber dadurch weiß der Einzelne doch nicht, welche Augenfarbe er hat. Oder anders: 100 von 1000 sollten sich umbringen, aber keiner der 100 weiß, dass er gemeint ist. Sich bei 10%iger Erfolgswahrscheinlichkeit umzubringen klingt nicht so logisch.

Die 100 sind genau die, die nur 99 andere blauäugige sehen statt 100. Mit Wahrscheinlichkeit hat das nichts zu tun.

ipsec

Die neue Information ist mit 100 Blauäugige schwer nachvollziehbar, mit weniger wird es deutlicher.

Nehmen wir an, es gäbe 2 Blauäugige. Dann weiß jeder, dass es Blauäugige gibt. Nicht jeder weiß aber, dass jeder weiß, dass es Blauäugige gibt, denn jeder der Blauäugigen muss davon ausgehen, dass er keine blauen Augen hat, der andere damit der einzige wäre und somit nicht weiß, dass es Blauäugige gibt.

Nehmen wir an, es gäbe 3 Blauäugige. Dann weiß jeder, dass es Blauäugige gibt, jeder weiß auch, dass es jeder weiß (weil für jeden mindestens 2 andere blauäugig sind und man also weiß, dass jeder noch mindestens einen Blauäugige sehen muss), nicht jeder weiß aber, dass jeder weiß, dass jeder weiß, dass es Blauäugige gibt, denn jeder der 3 muss davon ausgehen, dass er nicht blauäugig ist, womit er sich nicht sicher sein kann, dass jeweils einer der beiden Verbliebenen weiß, dass der andere weiß, dass es Blauäugige gibt, weil das implizieren würde, dass man selbst blaue Augen hat, was man aber nicht weiß.

Entsprechend weiß bei 100 Blauäugige nicht jeder, dass jeder weiß, dass jeder weiß, ... (100 mal), dass es Blauäugige gibt.

Wenn jetzt ein Fremder kommt und sagt "Hier gibt es Blauäugige", weiß das jeder und jeder weiß, dass es jeder weiß, und jeder weiß, dass jeder weiß, dass es jeder weiß usw. usw.

Ist eventuell etwas verworren, abr wenn man sichs einmal vor Augen geführt hat, erschließt sichs.

Bashar schrieb:

SeppJ schrieb:

Perfekte Induktion. Der Reisende liefert dabei den Fixpunkt ab dem alle anfangen können zu zählen.

Das mit dem Fixpunkt finde ich nicht überzeugend. Warum zählen sie nicht sowieso schon die ganze Zeit, wenn das solche perfekten Logiker sind?

Hmm, hab ich mich auch gefragt. Ich verstehe die Gemeinsames-Wissen-Geschichte nicht, aber den Fixpunkt irgendwie schon:

Nehmen wir an, am Tag X wäre diese Einheimischenpopulation komplett erschaffen worden. Jeder kennt die Spielregeln via göttlicher Offenbarung. Selbst wenn es genau einen blauäugigen in der Population gibt, fängt die Induktion gar nicht erst an. (Er sieht eben genau so viele braune Augen, wie ein Braunäugiger an seiner Stelle.) Bei mehreren auch nicht.

Auch wenn man den Anfang der Population irgendwie anders definiert (zB. durch allwissende Babys) klappt die Induktion nicht, weil der Fall n=1 nicht klar wäre.

Ist die Argumentation falsch? Wozu braucht es das Konzept des gemeinsamem Wissens? Ist das nur, die durchpropagierte Aussage von dem, was ich oben hingeschrieben hab, oder steckt da mehr dahinter?