Blog

Dies ist eine Auflösung, auf die vermutlich keiner von euch gewartet hat. Gebt es doch zu!

Es geht um diese Rätsel vom vergangenen August.

Es gab keine Lösungsvorschläge oder Einsendungen, also habe ich die selbstgebackenen Kekse, die ich euch schenken wollte, alle selbst verfuttert, danke dafür. 😉

Speziell möchte ich aber heute das Interessanteste, nämlich das 3., Rätsel auflösen. Zur Wiederholung:

8 Teilnehmer (die als Team antreten) einer ostasiatischen Gameshow stehen hintereinander vor einer Wand, keiner darf sich umdrehen.

Dann bekommt jeder Teilnehmer zufällig einen Hut mit einer Zahl 1-9 aufgesetzt, jeden Hut gibt es nur einmal. Jeder Teilnehmer sieht alle Hüte vor sich, aber nicht seinen eigenen. In beliebiger Reihenfolge dürfen die Teilnehmer die Zahl auf ihrem eigenen Hut raten (und hierbei keine Information außer einer Zahl von 1-9 weitergeben, angenommen sie raten nicht durch Rufe sondern durch Knopfdruck nach einer fest vorgegebenen Zeit), aufgelöst wird erst, nachdem alle eine Zahl geraten haben.

Als besondere Tücke galt in diesem Rätsel noch zusätzlich die Regel, dass eine Zahl nicht nur nicht doppelt vorhanden sein darf, sondern auch nicht doppelt geraten werden darf!

Das Team gewinnt umgerechnet Euro Preisgeld, wenn Teammitglieder ihren Hut richtig geraten haben. Der Hauptgewinn beträgt demnach 10 Millionen Euro, wenn alle die Zahl auf ihrem Hut richtig raten!

Was ist für das Team die beste Strategie und wie viel Gewinn kann mit ihr garantiert werden?

Wir beschränken und in dieser Auflösung auf den „Worst Case“, eine Betrachtung des statistischen Erwartungswerts wäre unnötig mathematisch und liefert keinen Mehrwert. 😉

Für alle, die das Rätsel noch nicht gekannt haben, hier ist für euch noch mal die letzte Gelegenheit, anzuhalten und selbst zu knobeln!

Es handelt sich bei dieser Variante um mein absolutes Lieblings-Matherätsel, nutzt also die Gelegenheit es selber zu lösen wenn ihr könnt!

Lösung 1: Eine gute Strategie

Das gleiche Rätsel, jedoch ohne die Einschränkung, dass keine Zahl doppelt geraten werden darf, habe ich bereits hier aufgelöst.

Im obigen Fall konnte ein Gewinn von einer Million garantiert werden. Kurze Wiederholung:

Das hinterste Teammitglied zählt die Zahlen auf allen Hüten, die er oder sie vor sich sieht, zusammen, teilt das Ergebnis durch 9 und rät den Rest. Details siehe obige Auflösung, aber an dieser Stelle noch mal ganz kurz zusammengefasst:

Alle anderen Teammitglieder zählen die Hüte zusammen, die sie selbst sehen und/oder kennen und können aus dem Tipp des letzten Teilnehmers ermitteln, was ihr eigener Hut sein muss, der in der Summe noch fehlt.

Eigentlich nicht schwer, oder?

Naja, fast. Die hier vorgestellte Regeländerung macht bei dieser Strategie nämlich schon ein kleines Problem. Angenommen, die Hüte haben, von hinten nach vorne, folgende Verteilung:

9 8 7 6 4 3 2 1 – Hut Nummer 5 ist nicht im Spiel.

Der hinterste Teilnehmer (mit der Hutnummer 9, die er natürlich selber nicht weiß) zählt die Hüte vor sich zusammen und kommt zum Ergebnis . Bei Division durch 9 bleibt in diesem Fall ein Rest von 4, also rät er Hutnummer 4.

Da er Hut Nummer 4 vor sich sieht, weiß er natürlich, dass das für ihn persönlich nicht stimmen kann, aber bei dieser Strategie geht es dem letzten Teilnehmer nur um Informationsweitergabe.

Jetzt raten die Teilnehmer (von vorne gezählt) 7 bis 5 alle mit der oben vorgestellten Methode richtig ihren Hut, aber der 4. Teilnehmer von vorne hat ein Problem. Er weiß jetzt die Nummer seines Hutes mit der obigen Methode, es ist die Nummer 4.

Aber da der hinterste Teilnehmer die Nummer 4 bereits geraten hat, darf er diese nicht mehr nennen!

Es ist noch schlimmer. Nach obiger Strategie muss er jetzt eine Zahl 1-9 raten, die noch nicht geraten wurde – und damit würde er seinen Vorderleuten eine falsche Information weitergeben, mit der sie auch ihren Hut falsch raten. Wie retten?

Ich habe damals, als ich dieses Rätsel selbst gestellt bekommen habe, lange an einem Mechanismus überlegt, um diesen Fehler mit möglichst wenig Verlust zu beheben, mir ist jedoch nichts Besseres eingefallen als die folgende Variante:

Der Teilnehmer mit der Nummer 4 rät stattdessen den Hut des vordersten Teilnehmers, in diesem Fall also die Nummer 1. Da er und die anderen Teilnehmer vor ihm den Hut mit der Nummer 1 selber sehen, wissen sie, dass er dies aus der Not heraus getan hat und eigentlich die Nummer des Letzten, in diesem Fall also die 4, hätte raten wollen (aber dies nicht durfte).

Hiermit könnten immerhin auch die Teilnehmer 3 und 2 noch ihren Hut richtig berechnen. Nummer 1 hätte natürlich auch in diesem Szenario keine Chance, seinen Hut zu erraten, weil die Nummer 1 ja schon geraten wurde (er oder sie könnte beispielsweise die nicht vorhandene 5 raten oder einfach passen).

Ergebnis wäre in diesem wie in jedem anderen Fall (mindestens) 5 richtig geratene Hüte, was einem Gewinn von 10.000 Euro entspricht.

Das ist gut und diese Strategie hätte auch einen Preis von mir verdient. Aber geht es noch besser?

Hier noch eine letzte Chance zum Grübeln, an dieser Stelle aber vielleicht ausdrücklich nur für die Mathematiker oder Mathematikfreunde unter euch zu überlegen…

Lösung 2: Eine geniale Strategie

Disclaimer: Auf diese Lösung bin ich selbst damals nicht gekommen, was mich im Nachhinein sehr ärgert, müsste das zugrunde liegende Prinzip doch jedem, der eine Algebravorlesung besucht hat, sehr bekannt sein.

Gibt es irgend eine Information, die wir in der oben vorgestellten Lösungsstrategie nicht benutzt haben?

Wenn man genauer überlegt, gibt es die. Der hinterste Teilnehmer hat die Hüte der anderen „codiert“, indem er die Summe gebildet hat und benutzt, dass sein Vordermann die gleichen Hüte (bis auf seinen eigenen) auch sieht.

Was jedoch nicht benutzt wurde, ist die Reihenfolge, in der die Hüte stehen. (Die Reihenfolge ist für die Summe egal, Mathematiker kennen das unter Kommutativität)

Es schien auch mir damals völlig absurd, dass der hinterste Teilnehmer auch noch diese Information gewinnbringend verschlüsseln könnte, zumal ihm ja nur so wenige Vokabeln zur Verfügung stehen. Aber es geht!

Ich benutze folgendes Beispiel zur Illustration, Blick aller Teammitglieder wie immer nach rechts gerichtet:

? 9 6 5 4 3 2 1

Die ersten 6 Hüte stehen bereits in der „richtigen“, geordneten, Reihenfolge. Die Hüte, die der letzte Teilnehmer (nennen wir ihn Peter) nicht sieht, haben die Nummern 7 und 8. Ich habe Peters Hut bewusst nicht in die Aufstellung geschrieben, denn keiner (inklusive natürlich Peter selbst) kann seinen Hut sehen und er tut für die Strategie nichts zur Sache.

Wir stellen uns vor, dass ganz hinten noch ein weiteres Teammitglied steht, nennen wir sie Sabine. (den Namen Thomas benutze ich als Platzhalter schon viel zu oft und ich muss dringend für Geschlechtergerechtigkeit sorgen!) Sabine sagt nichts und spielt auch nicht mit, aber wir stellen uns vor, Sabine würde ganz hinten stehen und den fehlenden Hut (die einzige Nummer, die nicht im Spiel ist) tragen. Keiner sieht sie und dementsprechend ändert ihre Anwesenheit nichts an der Strategie, aber sie hilft der Vorstellung ungemein.

Peter weiß jetzt, dass er und Sabine die Nummern 7 und 8 tragen, nur nicht in welcher Reihenfolge. Jetzt folgt ein Gedankenspiel:

Angenommen, die Teilnehmer inklusive Sabine würden sich jetzt umsortieren, sodass die Zahlen danach genau in der richtigen Reihenfolge stehen, Nummer 1 vorne und Nummer 9 hinten. Jedes Mal, wenn hierbei 2 Teilnehmer aneinander vorbei laufen, schütteln sie sich die Hand aber, weil das in Corona-Zeiten nicht erlaubt ist, geben sie sich den Ellenbogengruß:

Was passiert nun, sollte Peter den Hut mit der Nummer 7 tragen? In dem Fall hat Sabine hinter ihm die Nummer 8 und der einzige Teilnehmer, der „falsch“ steht, wäre der unmittelbar vor ihm mit der Nummer 9. Damit sich die Hüte sortieren, müsste dieser Teilnehmer theoretisch ganz nach hinten laufen, an Peter und Sabine vorbei, und beiden einen Ellenbogengruß geben.

Insgesamt gäbe es in diesem Szenario also 2 Ellenbogengrüße.

Jetzt angenommen, Peter hätte den Hut mit der Nummer 8 und dementsprechend Sabine die 7. Wieder müsste der Teilnehmer mit der Nummer 9 ganz nach hinten laufen an Peter und Sabine vorbei, aber diesmal stehen auch Peter und Sabine selbst in der falschen Reihenfolge, müssen also aneinander vorbei laufen und sich dabei einen Ellenbogengruß geben. In diesem Szenario gebe es also insgesamt 3 Ellenbogengrüße.

Ihr fragt euch vielleicht, ist das nicht alles völlig willkürlich und hängt davon ab, wie die Teilnehmer theoretisch laufen würden, um sich zu sortieren? Was, wenn alle gleichzeitig kreuz und quer laufen und sich im Vorbeilaufen abschlagen?

Zum Teil ja, willkürliches Durcheinanderlaufen führt zu unterschiedlichen Ergebnissen. Allerdings gibt es, wenn man sich das genauer überlegt, eine wichtige Einschränkung:

Wenn Peter und Sabine (oder 2 beliebige andere Teilnehmer aus der Reihe) in der richtigen Reihenfolge standen, also der mit der niedrigeren Zahl von beiden vorne und die beiden sich irgendwann im Vorbeilaufen abklatschen, stehen sie danach auf jeden Fall falsch. Und umgekehrt, wenn sie vorher falsch standen stehen sie danach richtig.

Wenn Peter und Sabine am Anfang in der richtigen Reihenfolge zueinander standen, müssen sie sich demnach immer eine gerade Anzahl oft abklatschen, um auch am Ende wieder in der richtigen Reihenfolge zu stehen. Wenn Peter und Sabine am Anfang in der falschen Reihenfolge standen, müssen sie sich hingegen eine ungerade Anzahl oft abklatschen.

Die gleiche Überlegung gilt nicht nur für Peter und Sabine, sondern auch für 2 beliebige andere Teilnehmer aus der Reihe. Man kann jetzt aber einfach berechnen, wie viele Ellenbogengrüße es insgesamt geben muss, ganz einfach indem man die erforderliche Anzahl für jedes einzelne Paar von Teilnehmern addiert. Und wir können mit Sicherheit sagen, ob diese Summe gerade oder ungerade sein wird – völlig unabhängig davon, wie die Leute tatsächlich laufen, um sich zu sortieren. Ob die Zahl an Ellenbogengrüßen gerade oder ungerade ist, ändert sich auch nicht, wenn alle gleichzeitig vogelwild durcheinander laufen, vorausgesetzt, alle halten sich auch brav an die Corona-Höflichkeitsregeln und begrüßen sich jedes Mal, wenn sie sich treffen. 🙂

Und was zum Henker hat das jetzt alles mit der Strategie zu tun??

Nun, die ist jetzt nach all den Vorüberlegungen erstaunlich einfach. Die Teilnehmer einigen sich nämlich im Vorfeld auf Folgendes:

Rate von 2 Möglichkeiten immer diejenige, die eine gerade Anzahl von Ellenbogengrüßen erfordern würde, um alle in die richtige Reihenfolge zu bringen.

Oder alle einigen sich auf eine ungerade Anzahl, wichtig ist nur, dass alle die gleiche Entscheidungsstrategie benutzen.

Zurück zum obigen Beispiel: Hat Peter den Hut mit der Nummer 7, würden 2 Grüße ausreichen, um alle in die richtige Reihenfolge zu bringen, eine gerade Zahl. Hätte Peter stattdessen den Hut mit der Nummer 8, würden 3 Grüße ausreichen, das ist jedoch eine ungerade Zahl. Also rät Peter für sich die Hutnummer 7.

Ob Peter damit Recht hat, weiß niemand von den Teilnehmern (Sabine spielt ja in Wahrheit gar nicht mit und niemand kennt Peters Hut). Aber für die Teilnehmer vor Peter lichtet sich wie von Zauberhand auf einmal das Dickicht:

Betrachten wir die Teilnehmerin unmittelbar vor Peter, die den Hut mit der Nummer 9 trägt, nennen wir sie einfach mal Lisa:

Lisa sieht vor sich die Hüte 1-6 alle bereits in der richtigen Reihenfolge. Peter hinter ihr hat die Nummer 7 geraten, für Lisa bleiben also nur die Nummern 8 und 9. Der jeweils andere Hut gehört Sabine, die sich auch Lisa ganz hinten vorstellt.

Wenn Lisa den Hut mit der Nummer 8 hätte, wäre Sabine bereits am richtigen Platz und nur Lisa und Peter müssten die Plätze tauschen, einmal abklatschen. 1 ist jedoch eine ungerade Zahl.

Wenn Lisa aber den Hut mit der Nummer 9 hat, müsste sie theoretisch ganz nach hinten und mit Peter und Sabine abklatschen. Sie geht davon aus, dass Peter tatsächlich die von ihm geratene Hutnummer 7 hat, dementsprechend wären 2 Ellenbogengrüße nötig, das ist eine gerade Zahl.

Also rät Lisa für sich den Hut mit der Nummer 9.

Wir sehen am obigen Beispiel, in dem Lisa tatsächlich die Nummer 9 trägt: Unabhängig davon, ob Peter mit seiner Zahl recht hatte oder nicht – Lisa hat auf jeden Fall recht!

Angenommen, vor Lisa steht Christopher mit der Hutnummer 6 – auch er muss sich zwischen den Nummern 6 und 8 entscheiden (er geht von der 9 bei Lisa und der 7 bei Peter aus). Da wir jedoch schon bei Lisa berechnet haben, dass die Verteilung wie im Beispiel mit der 6 bei Christopher und der 7 bei Peter funktioniert, gilt die gleiche Berechnung auch für Christopher und er entscheidet sich, völlig richtig, für die Nummer 6.

Wenn alle durch die Reihe nach vorne richtig rechnen (und dabei bei allen Personen hinter sich den Hut annehmen, den die Person geraten hat), raten alle vor Peter ihren Hut richtig. Ob Peter in Wahrheit den Hut mit der 7 oder 8 hatte, wissen nur der liebe Gott und der Showmaster, es ist allerdings für den Spielverlauf irrelevant.

Wenn Peter in obigem Beispiel tatsächlich die Nummer 7 auf seinem Hut hatte, geht das Team mit dem Hauptgewinn von 10 Millionen nach Hause, wenn er die 8 hatte (Worst Case), bleibt aber immer noch ein Trostpreis von einer Million Euro!

Für den Gewinn lohnt es sich doch, eine etwas ungewöhnliche Rechnung zu betreiben oder nicht? 🙂

Ich gebe zu, die Berechnung, ob eine bestimmte Verteilung eine gerade oder ungerade Zahl an Ellenbogengrüßen erfordern würde, ist bei einer zufälligen Verteilung aller Hüte nicht ganz einfach, aber machbar und wir haben ja nicht umsonst angenommen, dass alle Teammitglieder über gute Logikfähigkeiten verfügen. 🙂

Zum Schluss ein paar Ergänzungen für die Mathematiker unter euch:

Erstens: Es fehlt oben ein Beweis, dass die Strategie für alle Teammitglieder immer eindeutig ist. Das ist jedoch nicht allzu schwer nachzuvollziehen:

Lisa kennt, sobald sie an der Reihe ist, die Position von 7 Hüten und muss nur raten, welcher von den verbleibenden beiden ihr und welcher Sabine gehört. Sie rät eine Möglichkeit und berechnet, wie viel Ellenbogengrüße nötig wären, um alle Teilnehmer zu sortieren.

Für die andere Möglichkeit müssen nur sie und Sabine ganz am Ende in der sortierten Reihe ihre Position tauschen. Alle Personen, die Lisa dabei abklatscht, muss auch Sabine abklatschen und umgekehrt. Zusätzlich begegnen sich Lisa und Sabine einmal, also ist die Zahl an zusätzlichen Grüßen von der Form und damit ungerade.

Das ist wichtig, weil es bedeutet, wenn die eine Möglichkeit eine gerade Zahl an Grüßen erfordert, um die Hüte zu sortieren, ist die andere Möglichkeit auf jeden Fall ungerade und umgekehrt. Somit liefert die Strategie, immer die gerade Variante zu wählen, für jedes Teammitglied ein eindeutiges Ergebnis.

Zweitens: Die Tatsache, dass die Strategie auch im Worst Case für alle Teammitglieder bis auf den Letzten funktioniert, ist ein Musterbeispiel dafür, wie sich 2 Fehler gegenseitig aufheben können.

Sollte im obigen Beispiel Peter die 8 haben, erfordert die wahre Verteilung eine ungerade Anzahl an Ellenbogengrüßen. Mit der Annahme, die Zahl wäre gerade wie in der Strategie vereinbart, liegen also alle falsch.

Allerdings geht Lisa, sobald sie dran ist, zusätzlich davon aus, Peter hinter ihr hätte die 7 richtig geraten, ebenfalls ein Fehler. Lisa weiß nicht, dass sie sich mit beiden Annahmen irrt, trotzdem rät sie ihre Hutnummer (in diesem Fall die 9) richtig – ein Lehrbuchbeispiel für Minus mal Minus gleich Plus im übertragenen Sinne!

Drittens: Die Menge aller möglichen Reihenfolgen, in denen die Zahlen von 1 bis zu einer gewissen Grenze auftreten können, bezeichnet man in der Mathematik als Permutationen. Unsere Anzahl an Grüßen, die zur Sortierung notwendig ist, bestimmt, ob eine Permutation gerade oder ungerade ist.

Die geraden Permutationen bilden eine Untergruppe, mit anderen Worten, wenn eine Verteilung der Hüte eine gerade Anzahl an Grüßen erfordert darf ich auch eine beliebige gerade Anzahl von Teilnehmern vorher aneinander vorbeigehen lassen, die entstandene Permutationen wird als Summe zweier gerader Zahlen immer noch gerade sein.

In unserem Fall lautet die Strategie also, wähle immer die Permutation aus der Untergruppe der geraden Permutationen.

Fun Fact: Die Tatsache, dass gerade Permutationen sich ab 5 Teammitgliedern schon nicht mehr „einfach“ beschreiben lassen führt dazu, dass es eine „Mitternachtsformel“ für Funktionen vom Grad 5 (die aus der Oberstufe war Grad 2) gar nicht geben kann und sei sie auch noch so kompliziert. Nach einer solchen Formel haben die Mathematiker jahrhundertelang gesucht – bis der Norweger Niels Henrik Abel im Jahr 1824 den Spaßverderber spielte und zeigte, dass es diese Lösungsformel gar nicht geben kann.

Seid ihm dankbar, dass ihr nie eine solch grausame Formel lernen musstet und werdet müssen! 🙂