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

    Ok, jetzt ich ...


    Eine Strategie besteht doch darin, für jeden denkbaren Verlauf des "Spiels" (das der W._Mann spielt) festzulegen, wie reagiert wird, in diesem Falle, welche Farbe (hier 0 oder 1) gewählt werden soll.


    Gehen wir von 4 Wichteln A,B,C und D aus.


    Wenn ich nur die allererste Wahl des W.-Manns betrachte: er kann A,B,C oder D wählen, 4 Möglichkeiten. Eine Strategie legt nun fest, welche Farbe A nehmen soll, wenn er gewählt wird, entsprechend für die drei anderen. D.h., die Strategie bildet die Menge {A,B,C,D} auf {0,1} ab. Und wie viele solcher Abbildungen gibt es?

    Das ist einfach: 4 * 2 = 8


    Male von jedem Wichtel je einen Pfeil auf 0 und 1: Das ergibt insgesamt 8 Pfeile.

    D

    Georg J. aus D. schrieb:

    Das ist einfach: 4 * 2 = 8


    Male von jedem Wichtel je einen Pfeil auf 0 und 1: Das ergibt insgesamt 8 Pfeile.

    8 Pfeile, richtig. Nur: jeder einzelne Pfeil ergibt noch keine Strategie, denn er verbindet ja nur einen Wichtel mit einer Farbe, was ist mit den drei anderen?

    Eine Strategie - nur für diesen ersten "Zug" - bestünde darin, jeden Wichtel mit genau einer Farbe zu verbinden. Und die Anzahl solcher Zuordnungen ist 24.

    Ich glaube für n = 3 lässt sich das noch am einfachsten aufdröseln. Die 48 Möglichkeiten sind keine Strategien. Es gibt 48 Möglichkeiten, wie sich die 3 Wichtel der Reihe nach in verscheidenen Hutvariationen aufstellen können. Aber beim 3. Wichtel haben sie gar keine Wahl mehr, das wird vom Weihnachtsmann bestimmt und dafür können sie keine Strategie wählen.


    Und der zweite Wichtel, der vom Weihnachtsmann ausgewählt wird, hat nicht nur 2 sondern 4 mögliche Strategien (nicht Wahlmöglichkeiten!). Er kann seine Farbwahl von seinem Vorgänger (A1 oder B1) und der Wahl seines Vorgängers abhängig machen, also für f(A1=0) muss er eine Strategie haben, genau so für f(A1=1), f(B1=0) und f(B1=1). Es gibt also 2 x 2 x 2 x 4 x 4 x 4 verschiedene Strategien.


    Ergänzung: sorry, ihr schreibt viel schneller als ich. Ich bin immer noch bei n=3, wollte aber euren Gedankenfluss mit n=4 nicht durcheinander bringen.

    RüdiJ schrieb:

    Ich glaube für n = 3 lässt sich das noch am einfachsten aufdröseln. Die 48 Möglichkeiten sind keine Strategien. Es gibt 48 Möglichkeiten, wie sich die 3 Wichtel der Reihe nach in verscheidenen Hutvariationen aufstellen können. Aber beim 3. Wichtel haben sie gar keine Wahl mehr, das wird vom Weihnachtsmann bestimmt und dafür können sie keine Strategie wählen.


    Und der zweite Wichtel, der vom Weihnachtsmann ausgewählt wird, hat nicht nur 2 sondern 4 mögliche Strategien (nicht Wahlmöglichkeiten!). Er kann seine Farbwahl von seinem Vorgänger (A1 oder B1) und der Wahl seines Vorgängers abhängig machen, also für f(A1=0) muss er eine Strategie haben, genau so für f(A1=1), f(B1=0) und f(B1=1). Es gibt also 2 x 2 x 2 x 4 x 4 x 4 verschiedene Strategien.


    Ergänzung: sorry, ihr schreibt viel schneller als ich. Ich bin immer noch bei n=3, wollte aber euren Gedankenfluss mit n=4 nicht durcheinander bringen.

    Ja, so in etwa. Kleine Ergänzung resp. Korrektur: die Farbe, die Wichtel m aufgrund der vereinbarten Strategie wählt, hängt von m und allen vorher gewählten Wichteln ab, wobei die Reihenfolge der Auswahl wichtig ist. Sie hängt nicht ab von den vorher gewählten Farben.


    In anschaulichen Beschreibungen einer Strategie kann das natürlich sein, z.B. "falls die Anzahl der bisher rot gewählten ungerade ist ...".

    Das ändert aber nichts an den oben gemachten Feststellungen, da man jede, auch anschaulich definierte, Strategie immer in der oben beschriebenen Form angeben kann.

    Ich kann jetzt eure 29 Strategien für 3 Wichtel nachvollziehen.

    Ich hatte mich in Hinblick auf Phase 2 auf die möglichen Ergebnisse, die aus allen Reihenfolgen der Wichtel und allen Farbwahlen der Mützen (inkl. der Wahl der letzten Mützenfarbe durch den Weihnachsmann) entstehen können, beschränkt. Das hatte ich fälschlicherweise als Strategie bezeichnet.

    MATH+ schrieb:

    Wäre eine weitere Verbesserung wohl möglich, wenn nur die beiden ersten Gruppenersten eine rote Mütze wählen und beide letzte Gruppenerste eine blaue?

    Mir ist es leider nur gelungen, deine Angaben für n=3 in einer Tabellenkalkulation nachzustellen. n=4 gelingt mir so nicht.

    Gute Idee. Daran hatte ich noch nicht gedacht. Wenn ich Zeit habe, werde ich es mal durchrechnen.
    Für n = 3 habe ich alle 9! Permutationen von 9 Wichteln (ohne Wiederholung) durchlaufen.

    Für n = 4 habe ich alle 16!/4!4 Permutationen von 4 Gruppen (mit Wiederholung) durchlaufen:

    1. Gruppe: 12612600

    2. Gruppe: 13759200

    3. Gruppe: 15724800

    4. Gruppe: 20966400

    Summe: 63063000

    pierrot schrieb:

    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

    Geniale Strategie - da wär ich NIE drauf gekommen! Chapeau!