Die Zahl der Bewerber für ein begehrtes Logikseminar übersteigt die Zahl der freien Plätze. Der Professor hält alle Bewerber für gleichermaßen hochbegabt und trifft eine Zufallsauswahl.
Für die endgültige Zulassung müssen die Kandidaten aber noch eine Prüfung bestehen. Er heftet allen Bewerbern einen Zettel auf den Rücken. Auf den Zetteln der Ausgewählten steht ein X und auf den anderen ein O. Keiner der Kandidaten weiß, ob er ausgewählt wurde oder nicht, aber er sieht all die anderen Zettel und er weiß folglich, welche der anderen Bewerber ausgewählt wurden.
Der Professor sagt den Bewerbern nicht, wie viele er insgesamt ausgewählt hat, aber wenigstens einer sei es ganz bestimmt. Er greift sich einen Gong und sagt: „Ich schlage jetzt etwa alle fünf Sekunden den Gong. Wer beim Gongschlag weiß, dass er ein X auf dem Rücken trägt, verlässt den Raum. Gibt er auch noch eine stichhaltige Begründung dafür, bekommt er einen Platz im Seminar.“ Damit beginnt er, den Gong zu schlagen. Tatsächlich verlassen alle Auserwählten gleichzeitig den Raum. Beim wievielten Gongschlag geschieht das?
Nachtrag
Die Teilnehmer dürfen sich während der Prozedur untereinander weder durch Wort noch Tat verständigen. Andernfalls wäre das Rätsel witzlos.
Wer Musterlösungen vermisst, der findet auf der Seite Denksport die Gründe dafür.
Weiter geht’s in den Kommentaren.
Für die Lösung des Rätsels Auf den Schlag muss ein den Kandidaten gemeinsames Wissen (Common Knowledge), alo ein Wissen, das über Aufgabenstellung und Logik hinausgeht, angenommen werden. Die folgende Aufgabenstellung mag noch rätselhafter erscheinen, doch reichen logische Schlüsse für das Auffinden der Lösung aus. Zusätzliches gemeinsames Wissen muss nicht unterstellt werden.
Einunddreißig Logiker aus verschiedenen Ländern nehmen an der jährlichen internationalen Logikkonferenz teil. Um sicherzustellen, dass nur Logiker teilnehmen, müssen die Teilnehmer an einem Test teilnehmen. Der Tagungsleiter erklärt, dass jeder der 31 Teilnehmer einen Farbpunkt auf die Stirn bekomme. Jeder könne die Farbpunkte der anderen sehen, seinen eigenen aber nicht. Jedwede Kommunikation zwischen den Teilnehmern sei untersagt. Jeder der Teilnehmer solle möglichst schnell herausfinden, welche Farbe sein Punkt hat. Er werde eine Glocke läuten und jeder, der zu diesem Zeitpunkt die Farbe des Punktes auf seiner Stirn erraten hat, müsse den Saal verlassen. Die Glocke werde er so oft wie nötig läuten. Er sei über die Farbpunkte vollständig informiert und wisse von jedem der Teilnehmer, zu welchem Zeitpunkt er den Raum verlassen muss (sofern er Logiker ist).
Einer der Teilnehmer meldet sich und fragt, ob es möglich sei, den Test zu bestehen – also die Farbe des Punktes auf der eigenen Stirn zu erraten. Der Tagungsleiter antwortet, dass er die Farben der Punkte so gewählt habe, dass jeder Teilnehmer die Farbe seines Punktes zur rechten Zeit schlüssig ermitteln könne.
Da keine weiteren Fragen kommen, beginnt der Test. Der Tagungsleiter platziert die Farbpunkte auf den Stirnen der Teilnehmer und gibt Gelegenheit, sich umzuschauen. Nach einer Weile läutet er die Glocke. Daraufhin verlassen vier Teilnehmer den Raum. Beim zweiten Läuten gehen alle Teilnehmer mit roten Punkten. Beim dritten Läuten rührt sich keiner. Beim vierten Läuten geht wenigstens einer hinaus. Erneutes Läuten. Jetzt geht der Teilnehmer, der die einzige Frage gestellt hat. Mit ihm gehen seine Schwester und weitere Teilnehmer. Der Fragesteller und seine Schwester haben verschiedenfarbige Punkte. Danach sind noch Teilnehmer im Raum.
Angenommen, alle Teilnehmer sind Logiker und verlassen den Raum zur rechten Zeit: Wie oft muss der Tagungsleiter läuten?
Die Lösung ist völlig klar. Beim ersten Gong. Denn es wurden offenbar keine einschränkenden Regeln erlassen. D. h. die Studenten schauen auf ihren Rücken oder nehmen den Zettel weg oder Fragen einen anderen Studenten.
Das Ergebnis: Die, die wissen, dass sie auserwählt wurden, verlassen den Raum, weil sie gewonnen haben, und die, die wissen, dass nicht nicht auswerählt wurden, verlassen den Raum, um nach Hause zu gehen.
Pablo, Sie haben Recht. Aber Denksportaufgaben machen unausgesprochen naheliegende Annahmen. Hier ist es die Annahme, dass die Bewerber sich nicht miteinander verständigen dürfen, auf welchem Weg auch immer. Das meinte ich durch die Formulierung „Keiner der Kandidaten weiß, ob er ausgewählt wurde“ abgedeckt zu haben. Jetzt dürfte dieser Punkt aber klar sein.
Für mich ergibt das dann nur Sinn, wenn nur einer ausgewählt wurde und folglich vor dem ersten Gong die Sache geklärt ist. Denn nur in dem Fall kann dann abgeleitet werden, wer auserwählt wurde und wer nicht. Sobald mehr als einer ausgewählt wurde, kann niemand wissen, ob er nicht doch noch zu den Außerwählten gehört.
@ Pablo
Meinen Studenten habe ich vor vielen Jahren (19.12.2015) einmal die folgende einfache Version des Rätsels aufgegeben – zum Eingewöhnen:
Zehn Logiker: Im Raum sind zehn Logiker und der Spielleiter. Der Spielleiter verbindet den Logikern die Augen und macht dann jedem von ihnen einen farbigen Punkt auf die Stirn. Dann nimmt er die Augenbinden ab und sagt: „Jeder von Ihnen hat einen farbigen Punkt auf der Stirn. Jeder von Ihnen kann mit vollkommener Sicherheit schließen, welche Farbe sein Punkt hat. Sobald jemand weiß, welche Farbe sein Punkt hat, verlässt er den Raum. Reden und Zeichengeben sind nicht erlaubt!“
Nachdem sich alle Logiker gegenseitig betrachtet haben, verlassen alle den Raum. Wie das? Gibt es mehrere Erklärungen?
An die Herren, gerade Pablo: wo ist die Tür? Nur scheinbar off topic, aber dringend.
https://www.spektrum.de/news/anthropozaen-mehr-beton-als-biomasse/1806368
Die im Artikel beschriebene Zulassungsprüfung für Logiker ist eine einfache Version des Rätsels der „31 Logiker“, so dachte ich. Da habe ich mich wohl geirrt. Denn diese Aufgabe setzt voraus, dass alle Beweber ein gemeinsames Vorwissen von etwas haben, das ich für eine Spielart der vollständigen Induktion halte.
Jedoch habe ich für dieses gemeinsame Wissen keine gute Begründung. Sogar Giuseppe Peano musste ja extra ein Induktionsaxiom postulieren: ”Enthält die Menge X die 0 und mit jeder natürlichen Zahl n auch deren Nachfolger n′, so bilden die natürlichen Zahlen eine Teilmenge von X.”
Eine Menge ist in diesem Zusammenhang gegeben durch eine Aussage oder eine Formel: Ist sie für ein n erfüllt, dann gehört dieses n zur Menge, andernfalls nicht. Beispiel für eine solche Aussage, die der vollständigen Induktion zugänglich ist: Die Summe aller Zahlen von 1 bis n ist gleich n(n+1)/2. Diese Aussage lässt sich im Prinzip für jedes gegebene n unabhängig von der vollständigen Induktion verifizieren.
Eine solche übergeordnete Aussage kann ich im Falle des Rätsels nicht erkennen. Wer kann helfen?
Ich habe den Verdacht, dass es sich um eine wirklich harte Nuss handelt, ähnlich der, die Edmund Landau in seinen Grundlagen der Analysis (1930) knackte. In seinem Vorwort für den Kenner macht er klar, dass die naive Übertragung der vollständigen Induktion auf die Definition der Addition natürlicher Zahlen zwar geübte Lehre ist, aber nicht funktioniert. In Kapitel 1 § 2 löst er das Problem. Aber er bleibt bei der Definition durch vollständige Induktion, die ansatzweise der Rekursion in der Informatik entspricht, meines Erachtens aber keinen Rückhalt in den Peano-Axiomen findet.
Die obige Frage:
n sei die Anzahl der Personen p. s mit 0<s<=n sei die Anzahl der ausgewählten Personen. Jede Person p weiß sofort, dass m_p oder m_p+1 Personen ausgewählt wurden, wobei m_p die Anzahl der für p sichtbar ausgewählten Personen entspricht. Jede Person weiß ja nur nicht, ob sie selbst ausgewählt wurde, die anderen sieht sie ja.
Antwort: Alle gewählten Personen gehen beim s-ten Gong.
Lösung durch Induktion:
n sei die Anzahl der Personen p. s mit 0<s Es gibt p mit m_p=0
-> p geht beim 1. Gong, da p niemand sonst ausgewählt sieht.
Bei den nächsten Gongs geht niemand mehr.
s=2: -> Beim 1. Gong geht niemand, da für alle p gilt m_p>0.
-> Es gibt Personen p und q mit m_p=1 und m_q=1.
-> p und q wissen, dass s=2, da s>3 unmöglich und bei 1. Gong niemand ging.
-> p und q gehen.
-> Danach geht niemand mehr, denn anderenfalls wären p und q ja nicht gegangen.
s=3: -> Beim 1. Gong geht niemand, da für alle p gilt m_p>1.
-> Beim 2. Gong geht niemand, da für alle p gilt m_p>1.
-> Es gibt Personen p,q,r mit m_p=2, m_q=2, m_r=2.
-> Diese wissen, dass s>2, denn sonst wären Personen bereits gegangen.
-> Dann bleibt nur noch s=3 und p,q,r gehen.
-> Danach geht niemand mehr, denn anderenfalls wären p,q,r ja nicht gegangen.
s=4: -> Beim 1. Gong geht niemand, da für alle p gilt m_p>2.
-> Beim 2. Gong geht niemand, da für alle p gilt m_p>2.
-> Beim 3. Gong geht niemand, da für alle p gilt m_p>2.
-> Es gibt Personen p,q,r,s mit m_p=3, m_q=3, m_r=3, m_s=3.
-> Diese wissen, dass s>3, denn sonst wären Personen bereits gegangen.
-> Dann bleibt nur noch s=4 und p,q,r,s gehen.
-> Danach geht niemand mehr, denn anderenfalls wären p,q,r,s ja nicht gegangen.
etc.
@ Feodor
Ich lese den Text als eine präzise Darstellung von Überlegungen, die zur Lösung des Rätsels führen.
Die Schlussfolgerungen zu s = 1 und s = 2 sind nahezu zwingend. Interessant wird es ab s = 3: Beim 1. und beim 2. Gong geht niemand, da für alle p gilt m_p>1. (Jeder kann wenigstens zwei X sehen.)
Das Verhalten wird also rekursiv definiert und auf das Verhalten für s = 1 und s = 2 zurückgeführt. Aber diese Situationen hat es ja gar nicht gegeben, sie werden nur imaginiert. Die Voraussetzungen sind erdacht.
Dass alle Kandidaten so denken, ist Gemeinsames Vorwissen. Dieses Vorwissen ist „nicht hinterfragbares Wissen, wie für uns das Wissen (oder der Glaube) um die Existenz der Welt“ (Christian Rieck, Spieltheorie, 2022, S.149). Insofern haben wir es mit einer ähnlichen, aber aus meiner Sicht interessanteren Lage, als bei der Realismus-Diskussion zu tun.
Im Grunde kann sich keiner ganz sicher sein, dass jeder der anderen genauso denkt wie er selbst und ebenfalls einen Schluss von s auf s+1 vornimmt oder ob er diesen gar für unzulässig hält.
Was ich hier problematisiere, nämlich den Unterschied von Induktions-Beweis und Rekursions-Definition, wird auch von berühmten Mathematikern als Problem gesehen:
B. L. van der Waerden: Algebra 1. 1971. § 3
Edmund Landau: Grundlagen der Analysis. 1930. Vorwort für den Kenner und Satz 4
Über das Problem, dass ich nicht weiß, was der andere weiß, schreibt Richard Elwes im ersten Kapitel seines Buches Das Chaos im Karpfenteich oder wie Mathematik unsere Welt regiert (2013). Danach geht er das im Artikel beschriebene Rätsel an.