20: Noch eine knackige Mützenaufgabe / Another Tricky Hat Challenge

  • Herrlich, ich liebe diese Mützenrätsel, einmal mehr: dickes Dankeschön an Aart Blokhuis und Gerhard Woeginger.

    Wenn man die Lösung hat (14 Wichtel dürfen Kaffee und Kuchen essen), ist sie in der Rückschau gar nicht so kompliziert wie zunächst vermutet.


    Hier eine Lösungsvorschlag zur knackigen Mützenaufgabe 2020 mit Erklärungsansatz, wie man auf die Strategie kommen kann:

    https://www.dropbox.com/s/gwh4…Knackige_Muetzen.JPG?dl=0

  • Meine Lösung:


    Die Wichtel bilden 2 Gruppen a 8, in jeder Gruppe 4 Paare.


    In der ersten Gruppe wählt immer der erste eines Paares rot, der zweite blau. Wenn einer als 8. der Gruppe gewählt wird, wählt er davon abweichend auch rot.

    Die zweite Gruppe verfährt analog mit vertauschten Farben.


    Wenn Quibo 8 rote Mützen sieht, wählt er die beiden Paare mit identischen Mützen aus.

    Sieht er 9 rote Mützen, wählt er die 4 rotbemützten aus der 2. Gruppe. Sieht er 7 rote Mützen, wählt er die 4 blaubemützten aus der ersten Gruppe.

    In jedem Fall stellt er die anderen 12 auf die sichere Seite und die ausgewählten zufällig (oder zuerst den mit dem hungrigsten Blick) auf. Diese 12, Wichtel X und er selbst bekommen sicher Kuchen, die anderen 3 ausgewählten nur mit etwas Glück.


    Ob es besser geht? Keine Ahnung! Aber zum Glück lautet die letzte Option 'M>=14'.

  • Herrlich, ich liebe diese Mützenrätsel, einmal mehr: dickes Dankeschön an Aart Blokhuis und Gerhard Woeginger.

    Wenn man die Lösung hat (14 Wichtel dürfen Kaffee und Kuchen essen), ist sie in der Rückschau gar nicht so kompliziert wie zunächst vermutet.


    Hier eine Lösungsvorschlag zur knackigen Mützenaufgabe 2020 mit Erklärungsansatz, wie man auf die Strategie kommen kann:

    https://www.dropbox.com/s/gwh4…Knackige_Muetzen.JPG?dl=0

    Habe dieselbe Strategie, mir direkt alles in 0 und 1 übersetzt und dann bildet sich bei 16 eine 4x4-Matrix. Die ersten drei der Gruppe 1, die letzte Person 0.


    1 1 1 0

    1 1 1 0

    1 1 1 0

    1 1 1 x


    x ist dann für den Santa bei 0 nimmt man die Wichtel der Spalte und stellt sie nach links, beliebige Reihenfolge und bei 1 hat Santa in der Zeile gepfuscht.


    Gerade Quadratzahlen sind immer ein Indiz für solche schönen Formen. Lässt sich für 26 oder 37 Wichtel:innen analog zeigen, dass nur sqrt(n-1)-1 schlimmstenfalls leer ausgehen.

  • Mist, das hatte ich genauso auch, habe dann auch Quibo hinzugefügt, aber Wichtel X vergessen, nachdem eine Zeile oder Spalte rausgeschmissen wird!


    Also 12 + 1 = 13 = falsch... In der Klausur wären es noch 15,5 von 16 Punkten, weil der Lösungsweg ja prinzipiell vollkommen richtig war...

  • Herrlich, ich liebe diese Mützenrätsel, einmal mehr: dickes Dankeschön an Aart Blokhuis und Gerhard Woeginger.

    Wenn man die Lösung hat (14 Wichtel dürfen Kaffee und Kuchen essen), ist sie in der Rückschau gar nicht so kompliziert wie zunächst vermutet.


    Hier eine Lösungsvorschlag zur knackigen Mützenaufgabe 2020 mit Erklärungsansatz, wie man auf die Strategie kommen kann:

    https://www.dropbox.com/s/gwh4…Knackige_Muetzen.JPG?dl=0

    Sehr schöne Lösung resp. Strategie. Und erstaunlich einfach. (Warum nur bin ich nicht darauf gekommen? :().

    Die Vermutung liegt nahe, dass eine bessere Strategie nicht existiert. Aber wie beweisen? Vielleicht gibt's ja im Lösungsheft einen Hinweis.

    (Ist natürlich für die Lösung hier im Kalender ohne Belang.)

  • /edit: Meine Strategie funktioniert nicht.


    Meine Strategie war, dass die Personen außer Quibo von 1 bis n (n=16 laut Aufgabe) nummeriert werden. Die k-te Person (mit Zahl j) in der vom Weihnachtsmann festgelegten Reihenfolge wählt eine Mütze nach den folgenden Kriterien:

    - k und j sind ungerade: rot

    - k ungerade und j gerade: blau

    - k und j gerade: blau rot

    - k gerade und j ungerade: rot blau

    Quibo kann nun bei n-2 Personen sicher sagen, ob sie die Mütze ausgewählt haben.

    Leider habe ich keinen Beweis, aber ich habe die Strategie per Programm bis n=9 getestet. Aber beim manuellen Testen der Strategie für n=3 und n=4 ist mir folgendes aufgefallen (Ich hoffe man kann erkennen, was ich meine.):

    Wenn man die letzte Person in der vom Weihnachtsmann festgelegten Reihenfolge ignoriert, kann man jede von der Strategie erzeugte Kombination K 2 Kombinationen L und M zuordnen. Wobei L und M aus der Menge N aller 2^n Möglichkeiten ist, wie die Personen generell eine Mütze wählen können. Dabei gilt nun für jede Kombination aus N, dass alle ihr aus der Strategie zugeordneten Kombinationen sich nur in 2 Personen unterscheiden.

  • Ich denke, dass deine Strategie nicht immer zum Ziel führt. Hier ein Gegenbeispiel: Wenn der Weihnachtsmann für k >= 2 immer j = k - 1 wählt und zum Schluss dem Wichtel mit k = 1 eine Mütze aufsetzt. Dann setzen alle 15 Wichtel, die selbst entscheiden dürfen eine blaue Mütze auf, denn wenn k gerade ist, dann ist j ungerade und umgekehrt. Wenn jetzt der Weihnachtsmann dem Wichtel k = 1 auch noch die letzte blaue Mütze aufsetzt, dann kann Quibo gar nichts entscheiden, da alle Wichtel eine blaue Mütze tragen. (Das ist auch so, wenn er z.b. zyklisch vorgeht und mit k = 4 beginnt (also j = k - 3) und am Schluss dem Wichtel k = 3 die letzte blaue Mütze aufsetzt.

  • Ich denke, dass deine Strategie nicht immer zum Ziel führt. Hier ein Gegenbeispiel: Wenn der Weihnachtsmann für k >= 2 immer j = k - 1 wählt und zum Schluss dem Wichtel mit k = 1 eine Mütze aufsetzt. Dann setzen alle 15 Wichtel, die selbst entscheiden dürfen eine blaue Mütze auf, denn wenn k gerade ist, dann ist j ungerade und umgekehrt. Wenn jetzt der Weihnachtsmann dem Wichtel k = 1 auch noch die letzte blaue Mütze aufsetzt, dann kann Quibo gar nichts entscheiden, da alle Wichtel eine blaue Mütze tragen. (Das ist auch so, wenn er z.b. zyklisch vorgeht und mit k = 4 beginnt (also j = k - 3) und am Schluss dem Wichtel k = 3 die letzte blaue Mütze aufsetzt.

    Keine Ahnung, wie ich das übersehen konnte...

  • Man kann die Vier-Vierergruppen-Strategie so erweitern, dass der zeitlich erste jeder Vierergruppe die freie Farbwahl hat und dadurch 1 Bit an Information mitteilen kann. Die beiden Nachfolger jeder Gruppe nehmen die Farbe des Vorgängers, der letzte die andere Farbe.

    Am Ende ist wie bisher entweder in vier Gruppen der jeweils letzte zu erkennen, oder in genau einer Gruppe ist dies nicht der Fall.