Wie löst ihr folgendes Rätsel?
Bitte lesen.
Hallo, ich würde gerne wissen, welche Methoden ihr anwendet, um das Rätsel zu lösen, welches ich gleich stelle. Stellt bitte eure ganze Lösung vor. Ich bitte euch, auch wenn ihr das Rätsel nicht löst, eure Ansätze hier aufzuschreiben. Bitte füllt auch danach die Umfrage aus.
Das Rätsel lautet wie folgt
"In einem Kloster leben Mönche, die einer ganz strengen Religion folgen. Diese Religion besagt, dass die Mönche untereinander in keinster Weise kommunizieren dürfen.
Eines Tages bricht der Abt jedoch das Schweigen und verkündet:
'In unserem Kloster ist eine Krankheit ausgebrochen, die sich dadurch bemerkbar macht, dass jeder Infizierte einen Schwarzen Punkt auf der Stirn trägt. Wenn jemand herausfindet, dass er infiziert ist, soll er sich gleich darauf um Mitternacht erhängen. Wer nicht infiziert ist, soll am Leben bleiben'.
Es gibt keinen Weg, wie sich die Mönche selber sehen können. Alle Mönche wollen die Anweisung des Abts erfüllen. Was wird passieren?"
Es folgt noch eine Umfrage.
Dieses Experiment soll dazu dienen, zu untersuchen, wie weit kreatives und analytisches Denken bei verschiedenen Menschen ausgeprägt sind. Ich halte dieses spezielle Rätsel aufgrund seiner mittelmäßigen Schwierigkeit für geeignet, eine hinreichend große, aber überschaubare Menge an Personen zu erreichen.
Vielen Dank.
Das Ergebnis basiert auf 25 Abstimmungen
20 Antworten
Ausgangslage: Es gibt Mönche mit schwarzem Punkt auf der Stirn. Die sollen sich erhängen. Ein Mönch, der nur Mönche sieht, die keinen schwarzen Punkt auf der Stirn tragen, weiß, dass er einen schwarzen Punkt auf der Stirn haben muss. Also erhängt er sich in der näcshte Nacht.
Sieht ein Mönch noch genau einen Mönch mit schwarzem Punkt, und dieser bringt sich nicht um, dann erhängt er sich ebenfalls, gemeinsam mit dem anderen. Weil beide wissen, dass sie infiziert sein müssen.
Sieht ein Mönch mehrere Mönche mit schwarzem Punkt, erhängt er sich nicht sondern wartet ab.
Ich kannte das Rätsel bis heute nicht. Induktion kenne ich aus der Philosophie und der Logik. Bin aber nicht sicher ob Du dasselbe meinst.
Sieht ein Mönch noch genau einen Mönch mit schwarzem Punkt, und dieser bringt sich nicht um, dann erhängt er sich ebenfalls, gemeinsam mit dem anderen. Weil beide wissen, dass sie infiziert sein müssen.
Wieso sollte sich hier der erste Mönch umbringen? Er sieht den anderen Mönch mit dem schwarzen Punkt, der sich bei dir als zweites umbringt, ja auch. Wieso sollte der erste also davon ausgehen, dass er einen schwarzen Punkt auf der Stirn hat?
Der andere brächte sich um, sähe er nur noch Mönche ohne Punkt. Da er aber einen Mömch mit Punkt sieht, bringt er sich zunächst nicht um. Da sich aber der Mönch mit Punkt ebenfalls nicht umbringt, wissen beide, dass der jeweils andere einen Punkt haben muss. Also bringen sie sich gemeinsam um.
Der andere brächte sich um, sähe er nur noch Mönche ohne Punkt. Da er aber einen Mömch mit Punkt sieht, bringt er sich zunächst nicht um. Da sich aber der Mönch mit Punkt ebenfalls nicht umbringt, wissen beide, dass der jeweils andere einen Punkt haben muss. Also bringen sie sich gemeinsam um.
Nach dieser Logik müssten sich allerdings dann alle im Kloster umbringen. Alle sehen mindestens einen Mönch mit Punkt. Da sich dieser oder diese mit Punkt ebenfalls nicht umbringen, wissen alle, dass sie jeweils einen Punkt haben müssen. Also bringen sich alle gemeinsam um.
Nein, es geht nicht darum, mindestens einen Mönch mit Punkt zu sehen. Es geht darum, genau einen Mönch mit Punkt zu sehen. Und aus seinem Verhalten zu schließen, dass man selber einen Punkt hat, weil er sich nicht umbrachte.
Ich bin von selbst nicht auf die Lösung gekommen, wobei ich finde, dass noch nicht wirklich klar ist, was passiert, wenn mehr als 2 Mönche infiziert sind.
Weiterhin funktioniert das Rätsel nur aus mathemathischer/logischer Sicht, also wenn man alles psychologische weglässt, außer eben die Fähigkeit, sich in andere hineinzuversetzen (theory of mind). Denn ich frage mich z.B., ob ein Mönch, der feststellt, dass nur einer der anderen Mönche einen schwarzen Punkt hat, sich wirklich sicher sein kann, dass er selbst auch infiziert ist. Also ob er wirklich diesen Rückschluss zieht, nur weil der andere sich nach der ersten Nacht noch nicht umgebracht hat. Denn es könnte ja sein, dass der andere einfach nicht den Mut findet, sich umzubringen, oder er dem Abt nicht traut...oder...oder...
die Vorgabe war "Wenn jemand herausfindet, dass er infiziert ist, soll er ..." - nicht wenn er infiziert IST oder wenn einer einen infizierten sieht usw.
= wenn alle sich streng an die Regeln halten, findet es keine raus (kann sich nicht sehen, darf nicht komm.)
dass die Krankheit sich - außer im Punkt - auswirkt stand nirgends = nach ner Weile gibt es ("ausgebrochen" deutet auf infektiös...) ein Kloster mit gepunkteten Mönchen...
Disney hat das mitbekommen und 101 Dalmatiner draus gemacht...
Da der Abt bereits die goldene Regel des Nicht-Sprechens gebrochen hat und er als höchste Instanz im Kloster gilt, ist diese Regel aufgelöst und die Mönche können sich gegenseitig darauf aufmerksam machen, ob sie den Schicksalspunkt auf der Stirn haben.
Der Abt sortiert die Mönche nach "betroffen" und "nicht betroffen", indem er die mit einem schwarzen Punkt auf der Stirn auf einer Seite und die ohne schwarzen Punkt auf der Stirn auf der anderen Seite platziert. Die, die einen schwarzen Punkt auf der Stirn haben, sehen auf ihrer Seite nur Mönche, die auch einen schwarzen Punkt auf der Stirn haben, während sie auf der anderen Seite nur Mönche sehen, die keinen schwarzen Punkt auf der Stirn haben und können so schnell schlussfolgern, dass sie betroffen sind und sich umbringen sollten.
Der Mönch kann nicht schlussfolgern, ob der Abt die anderen Mönche tatsächlich nach "betroffen" und "nicht betroffen" sortiert hat, es könnte ja sein, dass ein einziger Mönch ein Gegenbeispiel darstellt. Da der Abt nichts sagt und ihm nicht die Information vermitteln kann, wie er die Leute einteilt, wird nie jemand erfahren, ob er selbst ein Gegenbeispiel ist oder nicht.
Außerdem lässt sich eine Aufteilung nur durch Kommunikation mit den Mönchen herstellen.
Deine Lösung ist leider inkorrekt.
Der Mönch kann nicht schlussfolgern, ob der Abt die anderen Mönche tatsächlich nach "betroffen" und "nicht betroffen" sortiert hat, es könnte ja sein, dass ein einziger Mönch ein Gegenbeispiel darstellt. Da der Abt nichts sagt und ihm nicht die Information vermitteln kann, wie er die Leute einteilt, wird nie jemand erfahren, ob er selbst ein Gegenbeispiel ist oder nicht.
Das ist lächerlich. Wieso sollte genau ein Mönch ohne Punkt in Mitten von Mönchen mit Punkt sortiert werden. Das ist Quatsch.
Außerdem lässt sich eine Aufteilung nur durch Kommunikation mit den Mönchen herstellen.
Die Mönche in eine Formation schubsen ist Kommunikation?
Deine Lösung ist leider inkorrekt.
Du scheinst den Sinn von Rätseln nicht verstanden zu haben. Ein Rätsel, das eine vorbestimmte Lösung hat, ist ein schlechtes Rätsel und die Zeit ohnehin nicht wert.
Mein erster Teil ist nicht lächerlich, sondern ein formales Gegenbeispiel dafür, dass deine Idee immer funktioniert. Es mag zwar intuitiv unwahrscheinlich erscheinen, dass es genau ein Gegenbeispiel gibt, aber es ist möglich und daher kann dein Ansatz formal nicht richtig sein.
Die Mönche in eine Formation zu schubsen ist zwar nicht notwendigerweise Kommunikation, aber wie garantierst du, dass die Mönche sich nicht einfach zerstreuen, bevor der Abt seine Einteilung beendet hat? Es mag zwar seltsam wirken, aber solche Möglichkeiten müssen in Betracht gezogen werden, weil sie immer noch den Voraussetzungen des Rätsels genügen würden, welche in diesem Fall das einzige sein können, woran man sich orientieren kann, um eine formal korrekte Lösung zu erhalten.
Wenn ich eine Lösung als inkorrekt bezeichne, dann heißt das nicht, dass das Rätsel eine vorbestimmte Lösung hat, es ist zum Teil auch meine Absicht zu sehen, ob Leute dieses Rätsel auf eine andere, kreativere Weise lösen können.
Mein erster Teil ist nicht lächerlich, sondern ein formales Gegenbeispiel dafür, dass deine Idee immer funktioniert. Es mag zwar intuitiv unwahrscheinlich erscheinen, dass es genau ein Gegenbeispiel gibt, aber es ist möglich und daher kann dein Ansatz formal nicht richtig sein.
Aber wenn das gesamte Kloster danach strebt das Problem zu lösen, wird doch der Abt nicht auf die Idee kommen ein Gegenbeispiel in die Menge zu werfen. In welcher Welt ergibt das Sinn?
Die Mönche in eine Formation zu schubsen ist zwar nicht notwendigerweise Kommunikation, aber wie garantierst du, dass die Mönche sich nicht einfach zerstreuen, bevor der Abt seine Einteilung beendet hat? Es mag zwar seltsam wirken, aber solche Möglichkeiten müssen in Betracht gezogen werden, weil sie immer noch den Voraussetzungen des Rätsels genügen würden, welche in diesem Fall das einzige sein können, woran man sich orientieren kann, um eine formal korrekte Lösung zu erhalten.
Weil hier wieder der Punkt ist: Das Kloster strebt danach das Problem zu lösen. Wieso sollte also die Formation gebrochen werden, wenn diese doch zur Lösung des Problems hilft?
Vielleicht solltest du das also in deinem Rätsel ergänzen, dass die Mönche zwar bereit sind sich umzubringen, zum Lösen des Problems allerdings nicht beitragen wollen. Sonst würde meine Antwort nämlich Sinn ergeben.
Wenn ich eine Lösung als inkorrekt bezeichne, dann heißt das nicht, dass das Rätsel eine vorbestimmte Lösung hat, es ist zum Teil auch meine Absicht zu sehen, ob Leute dieses Rätsel auf eine andere, kreativere Weise lösen können.
Offenbar hast du dir allerdings deine Wunschantwort ja schon überlegt, was irgendwie den Sinn verfehlt. So lässt du im Endeffekt nur die Antwort zu, die du haben willst..
Wie bereits erläutert, triffst du viel zu viele zusätzliche Annahmen.Weshalb sollte es im Interesse des Abts liegen, dass die Mönche diesen Auftrag ausführen können? Das wäre eine common sense - Vermutung, weil der Abt ja den Auftrag erteilt hat, aber der gesamte Clou ist ja, sich nur an die gegebenen Voraussetzungen zu halten und anhand derer eine Lösung zu finden, auch wenn es intuitiv nicht richtig scheint, gewisse scheinbar offensichtliche Zusatzannahmen nicht zu treffen.
Das gilt auch für deine Annahme, dass die Mönche sich nicht zerstreuen würden. Woher weißt du das? Die Mönche wissen nicht, was der Abt vorhat und sie könnten nur mutmaßen auf der vagen Idee, dass der Abt ihnen ja vielleicht helfen wollen könnte.
Ich habe mir immer noch keine Wunschantwort überlegt, sondern eine Antwort, die formal korrekt ist, d.h. alle Voraussetzungen und nur die Voraussetzungen erfüllt.
Wie bereits erläutert, triffst du viel zu viele zusätzliche Annahmen.
Du triffst zusätzliche Einschränkungen, ohne diese in dem Rätsel darzulegen. Wie gesagt, beim nächsten Mal sag am Anfang, dass die Mönche nicht bereit sind zur Lösung des Problems beizutragen.
Weshalb sollte es im Interesse des Abts liegen, dass die Mönche diesen Auftrag ausführen können?
In dem Rätsel wird gesagt "Alle Mönche wollen die Anweisung des Abts erfüllen." Wenn dem so ist, wieso wollen sie dann plötzlich nicht, dass der Abt dabei hilft das Problem zu lösen?
Das gilt auch für deine Annahme, dass die Mönche sich nicht zerstreuen würden. Woher weißt du das?
Sie sind bereit sich aufgrund der Anweisung des Abts umzubringen, aber nicht dazu bereit in eine Formation zu gehen? Wenn du das jetzt noch logisch begründen kannst, können wir weiter reden.
Die Mönche wissen nicht, was der Abt vorhat und sie könnten nur mutmaßen auf der vagen Idee, dass der Abt ihnen ja vielleicht helfen wollen könnte.
Und sicherlich vertrauen sie dem nicht, für den sie sich umbringen würden... Ist klar.
Ich habe mir immer noch keine Wunschantwort überlegt, sondern eine Antwort, die formal korrekt ist, d.h. alle Voraussetzungen und nur die Voraussetzungen erfüllt.
while(die Mönche sehen mindestens einen Mönch mit schwarzem Punkt auf der Stirn) {
Alle Mönche gelten als unsortiert.
Zwei Mönche stellen sich voreinander und gelten als sortiert.
while(es gibt mindestens einen unsortierten Mönch) {
Ein unsortierter Mönch guckt sich die sortierten Mönche an und stellt sich zwischen die beiden Mönche, von denen der eine einen schwarzen Punkt auf der Stirn hat und der andere nicht und gilt als sortiert. Haben alle einen schwarzen Punkt oder alle keinen schwarzen Punkt auf der Stirn, geht der Mönch an ein beliebiges Ende und gilt als sortiert.
}
if(ein Mönch ist an einem Ende der Kette und sieht, dass nur noch Mönche ohne schwarzen Punkt außer ihm übrig sind oder sein direkter Nachbar einen schwarzen Punkt auf der Stirn hat) {
Der Mönch bringt sich um.
} else {
Alle Mönche gucken sich ihre direkten Nachbarn (vorne und hinten) an. Haben beide Nachbarn eines Mönchs einen schwarzen Punkt, wissen sie, dass sie auch einen schwarzen Punkt haben und bringen sich in der Nacht um. In allen anderen Fällen bringt er sich nicht um.
}
}
Formal und geht auf.
EDIT: Das erste if muss anders lauten. Es reicht hier zu sagen "if(ein Mönch ist an einem Ende der Kette und sieht, dass nur noch Mönche ohne schwarzen Punkt außer ihm übrig sind". Dafür muss dann im else folgende Ergänzung vorgenommen werden: "else { Alle Mönche gucken sich ihre direkten Nachbarn (vorne und hinten) an. Haben beide Nachbarn eines Mönchs einen schwarzen Punkt, wissen sie, dass sie auch einen schwarzen Punkt haben und bringen sich in der Nacht um. In allen anderen Fällen bringt er sich nicht um. Hat ein Mönch nur einen Nachbarn (ist also an einem Ende der Kette) und dieser hat einen schwarzen Punkt bringt er sich um."
Was man jetzt noch hinzufügen sollte, ist eine weitere Abbruchbedingung am Anfang, dass wenn nur zwei Mönche da sind und der Algorithmus läuft (also mindestens einer einen Punkt hat) bringt sich der um, der bei dem anderen keinen Punkt sieht.
Ich habe mehrfach versucht, dir zu erklären, was Voraussetzungen bei einem Rätsel bedeuten und was demzufolge eine Lösung im Sinne des Rätsels ist. Wir drehen uns allerdings im Kreis.
Mit "formal" ist nicht gemeint, dass du deine Gedanken von der natürlichen intuitiven Sprache in einen Pseudocode umwandeln sollst. Mit formal ist eine vollständige Lösung im Sinne aller Annahmen gemeint. Ein nicht-formaler Ansatz könnte beispielsweise eine intuitive Methode sein, die nicht auf alles achtet, aber eine Grundidee vermittelt.
Deine Strategie beruht hier auf der Grundannahme, dass die Mönche sich irgendwie auf dieses Verfahren geeinigt haben. Wie hätte das von statten gehen sollen?
Nochmal neu und in schön:
while(die Mönche sehen mindestens einen Mönch mit schwarzem Punkt auf der Stirn) {
Alle Mönche gelten als unsortiert.
if(es sind noch genau zwei Mönche da) {
Sieht einer der beiden übrigen Mönche, dass der andere keinen Punkt hat, bringt dieser sich um.
return;
}
Zwei Mönche stellen sich voreinander und gelten als sortiert.
while(es gibt mindestens einen unsortierten Mönch) {
Ein unsortierter Mönch guckt sich die sortierten Mönche an und stellt sich zwischen die beiden Mönche, von denen der eine einen schwarzen Punkt auf der Stirn hat und der andere nicht und gilt als sortiert. Haben alle einen schwarzen Punkt oder alle keinen schwarzen Punkt auf der Stirn, geht der Mönch an ein beliebiges Ende und gilt als sortiert.
}
if(ein Mönch ist an einem Ende der Kette und sieht, dass nur noch Mönche ohne schwarzen Punkt außer ihm übrig sind) {
Der Mönch bringt sich um.
} else {
Alle Mönche gucken sich ihre direkten Nachbarn (vorne und hinten) an. Haben beide Nachbarn eines Mönchs einen schwarzen Punkt, wissen sie, dass sie auch einen schwarzen Punkt haben und bringen sich in der Nacht um. In allen anderen Fällen bringt er sich nicht um. Hat ein Mönch nur einen Nachbarn (ist also an einem Ende der Kette) und dieser hat einen schwarzen Punkt bringt er sich um.
}
}
Deine Strategie beruht hier auf der Grundannahme, dass die Mönche sich irgendwie auf dieses Verfahren geeinigt haben. Wie hätte das von statten gehen sollen?
Weil die Mönche schlau sind und wissen, dass dies die einzige Methode ist das Problem zu lösen, weil keiner der Mönche auf deine Wunschlösung kommt. Alternativ spricht der Abt, der das Kommunizierverbot ohnehin schon gebrochen hat, diesen Algorithmus an.
Mit "formal" ist nicht gemeint, dass du deine Gedanken von der natürlichen intuitiven Sprache in einen Pseudocode umwandeln sollst.
Zu faul einen Pseudocode zu lesen?
Nein, nicht zu faul einen Pseudocode zu lesen, sondern nicht Sinn des Wortes "formal".
Fairer Weise hast du in deiner Frage nicht nach einer formalen Lösung gefragt.
Das ist selbstverständlich, eine vollständige Lösung des Rätsels kann nur eine formale Lösung sein.
Das ist selbstverständlich, eine vollständige Lösung des Rätsels kann nur eine formale Lösung sein.
Der Pseudocode für einen Algorithmus ist aber eine vollständige Lösung (außer es ist anders gefordert).
Wenn die Grundidee deines Algorithmus nicht die Voraussetzungen des Rätsels verletzen würde, dann wäre es eine vollständige Lösung.
Nebenbei mal ein paar Fragen zu deinem Algorithmus:
- Die letzte if-Schleife, in der ein Mönch am Ende einer Kette nur noch Leute ohne Punkte sieht und sich umbringt, ist bei dir Teil der ersten while-Schleife. Setzt diese aber nicht voraus, dass jeder Mönch mindestens einen anderen mit Punkt sieht?
- Ganz zum Schluss, weshalb sollte sich ein Mönch am Ende einer Kette umbringen, wenn er jemanden mit schwarzem Punkt vor sich sieht? Er könnte ja im Sinne der Ordnung der einzige sein, der keinen Punkt hat.
Falls ich etwas offensichtliches übersehen habe, sage es mir bitte, es könnte durchaus sein, weil ich seit ca. 30 Stunden nicht mehr geschlafen habe.
Wenn die Grundidee deines Algorithmus nicht die Voraussetzungen des Rätsels verletzen würde, dann wäre es eine vollständige Lösung.
Auch hier gilt: Fairer Weise steht in dem Rätsel nicht, ob der Abt nun das Schweigen weiter bricht oder ab dem Moment auch wieder in Schweigen verfällt.
Die letzte if-Schleife
If ist eine Verzweigung, keine Schleife.
in der ein Mönch am Ende einer Kette nur noch Leute ohne Punkte sieht und sich umbringt, ist bei dir Teil der ersten while-Schleife. Setzt diese aber nicht voraus, dass jeder Mönch mindestens einen anderen mit Punkt sieht?
Alles ist Teil der ersten while-Schleife. Die Formulierung ist vielleicht etwas schlecht gewählt, ja. Es sollte wohl besser lauten "Es gibt mindestens einen Mönch mit schwarzem Punkt auf der Stirn".
Ganz zum Schluss, weshalb sollte sich ein Mönch am Ende einer Kette umbringen, wenn er jemanden mit schwarzem Punkt vor sich sieht? Er könnte ja im Sinne der Ordnung der einzige sein, der keinen Punkt hat.
Ups, das ist tatsächlich ein Fehler, ja. Besser wäre da "Hat ein Mönch nur einen Nachbarn (ist also am Ende der Kette) und dieser hat einen schwarzen Punkt, bringt er sich um, außer alle Mönche, die er sehen kann, haben einen schwarzen Punkt".
Du solltest dringend schlafen und weniger auf gutefrage sein ^ ^
Zwei weitere Dinge:
- Sofern mich hier nichts täuscht, funktioniert der Algorithmus nicht in dem Fall, dass alle Leute einen schwarzen Punkt haben. Dann bleiben am Ende zwei Bepunktete übrig, die nicht wissen, was sie machen sollen.
- In deinem letzten else-Teil sollte ein Bepunkteter übrigbleiben, der sich nicht umbringt, nämlich der, der einen unbepunkteten Nachbar hat.
Sofern mich hier nichts täuscht, funktioniert der Algorithmus nicht in dem Fall, dass alle Leute einen schwarzen Punkt haben. Dann bleiben am Ende zwei Bepunktete übrig, die nicht wissen, was sie machen sollen.
Du müsstest recht haben. Man könnte noch einfügen, wenn nur noch zwei übrig sind, der Algorithmus noch läuft und sich in einer Nacht keiner von beiden umgebracht hat, sich beide umbringen.
In deinem letzten else-Teil sollte ein Bepunkteter übrigbleiben, der sich nicht umbringt, nämlich der, der einen unbepunkteten Nachbar hat.
Im Falle, dass es nur noch zwei Mönche sind, wurde sich um diesen Bepunkteten schon am Anfang gekümmert. Sollten es mehr als zwei Mönche sein und noch ein Bepunkteter bleibt übrig, sollte sich
"if(ein Mönch ist an einem Ende der Kette und sieht, dass nur noch Mönche ohne schwarzen Punkt außer ihm übrig sind) {
Der Mönch bringt sich um."
darum kümmern.
2: Dann würden sich doch haufenweise Unbepunktete umbringen, weil fast alle am Ende einer Kette stehen werden und sehen, dass nur noch Unbepunktete übrig sind.
Beispiel: k Bepunktete , n Unbepunktete
Die Fälle für hinreichend kleine n, k sind durchgespielt.
Alle n+k Mönche sind geordnet. k-1 Bepunktete bringen sich sofort um.
Es bleiben übrig: Ein Bepunkteter am Ende einer Kette und n Unbepunktete.
Der Bepunktete bringt sich nach der if-Bedingung um.
Es bleiben übrig: n Unbepunktete
2 Unbepunktete bringen sich nach der if-Bedingung um (beide sehen, dass nur noch Mönche ohne Punkte übrig sind.
Je nach Parität von n bleibt ein Unbepunkteter oder keiner über.
Es bleiben übrig: n Unbepunktete
2 Unbepunktete bringen sich nach der if-Bedingung um (beide sehen, dass nur noch Mönche ohne Punkte übrig sind.
In dem Fall hört der Algorithmus allerdings doch schon auf zu laufen, weil die while Bedingung nicht länger erfüllt ist, dass es noch Mönche mit Punkt gibt.
Woher wissen die Mönche, dass der Algorithmus nicht mehr läuft?
Zu meinem vorigen Kommentar: Ich habe nicht bedacht, dass sich alle Mönche ihre beiden Nachbarn anschauen, somit sind alle Mönche bis auf den ersten Unbepunkteten und dem letzten Bepunkteten sicher. Man kann ja davon ausgehen, dass jeder Mönch jeden anderen sehen kann, da du in deinem letzten else-Teil davon sprachst, dass der Mönch am Ende der Kette sich alle anderen Mönche ansieht.
Woher wissen die Mönche, dass der Algorithmus nicht mehr läuft?
Wenn mindestens ein Mönch einen schwarzen Punkt bei einem anderen Mönch sieht, wird dieser mit der Kette anfangen.
Zu meinem vorigen Kommentar: Ich habe nicht bedacht, dass sich alle Mönche ihre beiden Nachbarn anschauen, somit sind alle Mönche bis auf den ersten Unbepunkteten und dem letzten Bepunkteten sicher. Man kann ja davon ausgehen, dass jeder Mönch jeden anderen sehen kann, da du in deinem letzten else-Teil davon sprachst, dass der Mönch am Ende der Kette sich alle anderen Mönche ansieht.
Ja, genau. Ich meine, ich habe offensichtlich nicht alle Fälle mitbedacht, als ich den Pseudocode runtergeschrieben habe, aber ein paar Fälle sind mit drin ^ ^
Zu deiner ersten Bemerkung: Ich meine nicht, dass das funktioniert.
Nach einigen Operationen haben wir folgenden Zustand:
Ein Bepunkteter steht am Ende einer Kette und sieht k Unbepunktete vor sich und bringt sich nach der if-Bedingung um.
Es bleiben nur noch k Unbepunktete, von denen k-1 wissen, dass sie Unbepunktet sind. Am einen Ende der Kette weiß einer nicht, dass er Unbepunktet ist, nämlich genau der, dessen bepunkteter Nachbar sich gerade umgebracht hat.
Er könnte sich aufgrund der if-Bedingung umgebracht haben oder aber aufgrund der else-Bedingung (Er hat vor sich einen Bepunkteten gesehen und alle anderen waren unbepunktet ==> Er hat sich umgebracht).
Dein Argument, dass die Mönche eine neue Kette bilden würden, funktioniert nicht, denn die Kette ist in diesem Zustand immer noch geordnet. Du müsstest eine Neuordnung in deinen Algorithmus einbauen. Zum Beispiel: Wenn nur noch Unbepunktete übrig sind, stellt sich einer, der von sich weiß, dass er Unbepunktet ist (von denen gibt es k-1) hinter denjenigen, der nicht weiß, dass er Unbepunktet ist. Danach passiert nichts.
Das Problem ist, dass dieser Fall nicht mehr in der while-Schleife ist, die Ordnung aber nur innerhalb dieser Schleife ausgeführt wird, daher müsste die Ordnung da raus und die while-Schleife davon unabhängig ausgeführt werden.
Edit: Außerdem hätte man dann zwei then-Befehle bei der gleichen if-Voraussetzung.
Anmerkung: Nur, weil die Diskussion sich jetzt auf den Algorithmus an sich verschoben hat, ist das Grundsatzproblem dieses ganzen Gesprächs noch nicht aufgelöst: Der Algorithmus an sich kann keine Lösung des Rätsels sein, weil die Mönche diesen unter sich kommunizieren müssten, was den Voraussetzungen widerspricht. Man kann hier auch nicht mit Eindeutigkeit argumentieren.
Kurz gesagt: Der Mönch, der nicht weiß, dass er Unbepunktet ist, weiß nicht, ob der Algorithmus beendet ist oder nicht, also weiß er nicht, ob er sich an die if-Bedingung halten muss. Man könnte sagen, in solch einem Fall wartet der Unwissende ab, ob jemand die Ordnung verändert, ansonsten bringt er sich um.
Hast du das Rätsel nur mit eigenen Mitteln gelöst oder kanntest du es schon vorher?
Warst du vor diesem Rätsel mit dem Konzept der "mathematischen Induktion" vertraut?