Lösung Aufgabe 18

[Anonymous]

Frohes Neues zusammen,

hier meine Lösung:

Wir bezeichnen die Farben einfach als Zahlen 0,1,2 und nennen einen Vektor mit vier Einträgen dieser Zahlen eine Konfiguration, die Einträge stellen die Farben der Mützen der Wichtel dar, z.B. heißt (0,0,2,1), dass Atto und Bilbo eine rote (0), Chico eine gelbe (2) und Dondo eine blaue (1) Mütze auf haben. Wir nennen zwei Konfigurationen benachbart, wenn sie sich in nur einem Eintrag unterscheiden, zum Beispiel sind (0,0,2,1) und (0,2,2,1) benachbart.
Jede Konfiguration ist also zu 8 anderen Konfigurationen benachbart, da an vier Positionen jeweils zwei andere Optionen eingefügt werden können.

Eine Strategie gewinnt nichts durch zufällige Entscheidungen, wenn also eine Entscheidung getroffen werden muss, dann können wir davon ausgehen, dass die Strategie festlegt, wie jeder Wichtel sich verhält. Das ist gegeben, da bei einer zufälligen Entscheidung keine Garantie gegeben werden kann, dass eine bestimmte Konfiguration zu Kaffee und Kuchen führt, was ja aber das Ziel ist. (Das gleiche würde aber auch gelten, wenn es uns lediglich um eine Gewinnwahrscheinlichkeit ginge).

Wir sagen, dass eine Strategie eine Konfiguration löst, wenn in dieser Konfiguration Kaffee und Kuchen für die Wichtel garantiert werden.
Wenn eine Strategie eine bestimmte Konfiguration löst, dann muss in ihr im ersten Schritt einer der Wichtel ohne Information über seine Mütze ein Schild hochhalten, das nicht alle Farben zeigt. Das heißt aber auch, dass der Wichtel die selbe Information sagt, wenn nur sein eigener Hut eine andere Farbe hat, insbesondere also auch, wenn er eine Farbe auf hat, die nicht auf seinem Schild abgebildet ist. Insgesamt bedeutet das, dass jede Konfiguration, die von einer Strategie gelöst wird, auch zu einer Konfiguration benachbart sein muss, die nicht gelöst wird, also in der die Wichtel verlieren.
Aber jede Konfiguration, die nicht gelöst wird ist nur zu maximal acht gelösten Konfigurationen benachbart, es müssen also bei jeder Strategie mindestens 1/9 aller Konfigurationen nicht gelöst werden, also können maximal 72 Konfigurationen gelöst werden – das ist unsere obere Schranke.

In dieser Argumentation sehen wir, dass es schlecht ist, wenn eine gelöste Konfiguration zu zwei ungelösten benachbart ist, denn dadurch überdecken die zwei nicht gelösten Konfigurationen zusammen nur noch maximal 15 statt 16 gewinnende Konfigurationen, und mehr als 1/9 aller Konfigurationen müssen verloren werden. Wir suchen also nach einer Menge an ungelösten Konfigurationen, so dass der kürzeste Pfad über benachbarte Konfigurationen mindestens zwei gelöste Konfigurationen enthält. Mit systematischem Vorgehen kommen wir zum Beispiel auf die Liste:

(0,0,0,0)
(0,1,2,2)
(0,2,1,1)
(1,0,2,1)
(2,0,1,2)
(1,2,0,2)
(2,1,0,1)
(1,1,1,0)
(2,2,2,0)

Es ist einfach zu verifizieren, dass sich je zwei Konfigurationen in der Liste an genau drei Stellen unterscheiden. Das bedeutet, dass jede andere Konfiguration zu genau einer dieser benachbart sein muss (da sich die Mengen der Nachbarn alle unterscheiden müssen, also 8*9=72 verschiedene Konfigurationen benachbart zu diesen sind).

Wenn diese Wichtel sich einig sind, dass sie in diesen Konfigurationen verlieren, dann kann damit eine Strategie konstruiert werden, die alle anderen Konfigurationen löst:

Jeder Wichtel zeigt die Farben auf seinem Schild, die nicht zu einer der verabredeten verlorenen Konfigurationen führt. Wenn die Konfiguration also keine verabredet verlierende war, gibt es genau einen Wichtel, der nur zwei Farben nennt. Alle anderen wissen also, dass die nicht gezeigte Farbe zu einer verlierenden Konfiguration führen würde, wissen also auch, welche Farbe ihre Mütze haben muss, da die Kombination aus den zwei Farben, die sie sehen und der einen, die auf dem Schild fehlt, nur mit einer ihrer Farben zu einer verbotenen Konfiguration führen kann (da sich verbotenen Konfigurationen immer an drei Stellen unterscheiden).
In der folgenden Runde kann also jeder Wichtel, der nicht “geraten” hat, nur seine richtige Farbe zeigen, der ratende wiederholt sein Schild und die Wichtel haben gewonnen.

72 Konfigurationen können also als gewinnend garantiert werden.

Als kleine Notiz an Rande – die Wichtel schlagen die intuitive 2/3 (Es muss ja einer raten) da sich die falsch geratenen alle überschneiden (wenn einer falsch rät, dann raten gleich alle falsch), aber wenn einer richtig rät, treffen die anderen gar keine Aussage.

@Aart Blokhuis: Thank you so much for this wonderful task. It was such a pleasure to solve!

[Anonymous]

Sehr sehr schöne Lösung Murks, Bravo!!!

[Anonymous]

Man könnte noch ergänzen, wie man diese 9 Konfigurationen systematisch findet:
{(x,x-y,x+y,y) | x,y = 0,1,2 mod (3)}.
Man sieht sofort, dass man aus je zwei Koordinaten die beiden anderen berechnen kann, woraus alle gewünschten Eigenschaften folgen.

[Anonymous]

Meine Lösung ist letztendlich natürlich die gleiche wie bei murks, aber mein Gedankengang war wohl ein bisschen anders. Ich schreib es mal auf.

Ich habe die 81 Farbenkombinationen betrachtet, die sich ergeben, wenn man die volle Information betrachtet, also “wer hat welche Farbe auf”. Nur die Anzahlen zu betrachten, ist zu grob. RRGG ist also etwas anderes als GGRR oder RGRG.

Ich habe mir zuerst angeschaut, was passiert, wenn kein Wichtel etwas sagt (Tafel 7). Dann sagt keiner etwas falsches, was gut ist, aber trotzdem müssen alle nach Hause. Also muss einer etwas sagen. Wenn z.B. Atto xRRR sieht, und eine Aussage macht, die zwei Farben für ihn zulässt, dann werden zwei Kombinationen “gut” (die Wichtel kommen eine Runde weiter), und eine Kombination schlecht.

Insbesondere: Wenn Atto “G oder B” sagt, wird RRRR schlecht.
Analog können die anderen Wichtel verfahren: Wenn sie RxRR bzw. RRxR bzw. RRRx sehen, antworten sie mit “G oder B”. Jeder macht damit 2 weitere Kombinationen gut, und eine Kombination schlecht – aber das ist immer die gleiche Kombination! Also insgesamt 8 gute Kombinationen, 1 schlechte Kombination. (Besser geht nicht!)

Wenn man das 9 mal hinbekommt, hat man 9 schlechte Kombinationen und 72 gute. Dafür dürfen diese 9 Kombinationen paarweise nur in einer Stelle übereinstimmen, da man sonst Überlappungen der guten Kombinationen bekommt.

Also z.B.: Wenn ein Wichtel in Runde eins sieht, dass es eine der folgenden 9 Kombinationen sein könnte, dann macht er eine Aussage, so dass diese Kombination schlecht ist (sonst sagt er nichts, also Tafel 7):

RRRR
RGGG
RBBB
GRGB
GGBR
GBRG
BRBG
BGRB
BBGR

In Runde 2 wissen die 3 Wichtel, die Tafel 7 hochgehoben haben, ihre eigene Farbe.

Bemerkung 1: Die Farben sind eine schöne Nebelkerze. Wenn die Mützen Zahlen hätten, die pro Wichtel unterschiedlich sind (Atto = 1, 2, 3, Bilbo 4, 5, 6, Chico 7, 8, 9, Dondo 10, 11, 12), dann wäre macher vielleicht leichter darauf gekommen, dass man mit Farbanzahlen nicht zum Ziel kommt (da bin ich über 60 nicht hinausgekommen).

Bemerkung 2: Die Wichtel, die in Runde 1 Tafel 7 hochheben, wissen schon vor dem Tafelheben, dass sie gewinnen.

[Anonymous]

Hier war ich zu grob. Die Lösung von Linsen mit Spätzle gefällt mir sehr gut. Darauf wäre ich nicht gekommen, weil ich die Idee nicht kannte. Ich kam mit der groben Variante auf 54 und fand das auch schon cool 😉

[Anonymous]

Eine Nachfrage habe ich noch:
Das mit paarweise in einer Stelle übereinstimmen erreichst du durch das R, korrekt?

Erinnert mich sofort an das Spiel Dobble 😉

[Anonymous]

Anonymous wrote:

Eine Nachfrage habe ich noch:
Das mit paarweise in einer Stelle übereinstimmen erreichst du durch das R, korrekt?

Erinnert mich sofort an das Spiel Dobble 😉

Nein, das R alleine reicht nicht, das eine R in allen unteren sorgt nur dafür, dass alle anderen mit dem ersten nur in einer Stelle übereinstimmen.
Bei den unteren mit einem R an gleicher Stelle müssen die anderen Einträge komplementär sein, und dann kommt man schnell mit etwas rumtüfteln auf die Menge. Oder man überlegt sich eben eine Konstruktionsvorschrift, die das garantiert, so wie es Matheschlumpf getan hat.

[Anonymous]

Guten Morgen,

in der ersten Runde muß doch mindestens einer eine (höchstens) 2-farbige Tafel zeigen.
Damit kommt man aber nur in 54 Fällen weiter (wenn seine Mützefarbe dazu passt).
Was habe ich an der Aufgabe falsch verstanden? Könnte jemand mir da weiterhelfen?

[Anonymous]

Anonymous wrote:

Guten Morgen,

in der ersten Runde muß doch mindestens einer eine (höchstens) 2-farbige Tafel zeigen.
Damit kommt man aber nur in 54 Fällen weiter (wenn seine Mützefarbe dazu passt).
Was habe ich an der Aufgabe falsch verstanden? Könnte jemand mir da weiterhelfen?

Das habe ich ganz an Ende in meinem Post erwähnt – du hast Recht, wenn genau ein Wichtel ausgewählt wird, um etwas zu sagen. In der optionalen Strategie sagen alle Wichtel etwas falsches, wenn einer etwas falsches sagt, aber alle von diesem falschen aus erreichbaren richtigen (wenn sich die Mützenfarbe eines einzigen Wichtels ändert) werden gelöst, und je nachdem, welche Mütze sich ändert, trifft ein unterschiedlicher Wichtel eine Aussage, dadurch geht das.

[Anonymous]

Danke. Mir leuchtet noch nicht ganz ein, wie man diese neun “genialen” kodierten Mützenkombis findet.

[Anonymous]

Also ich bin wie folgt vorgegangen:
Da das ganz höchst symmetrisch ist, kann ich eine beliebige erste Kombination wählen und nehme (0,0,0,0). Jetzt weiß ich, dass alle anderen genau eine 0 beinhalten müssen. Wiederum wegen Symmetrie wähle ich für (0,x,x,x) einfach (0,1,1,1). Ich brauche noch einen zweiten mit 0 an erster Stelle, da müssen alle anderen dann eine zwei haben – (0,2,2,2). Jetzt brauche ich zwei mit 0 an der zweiten Stelle, wegen Symmetrie darf ich sie erste Stelle beliebig wählen, die letzten beiden Stellen müssen verschieden sein, damit sie nicht zu viele gleiche Positionen mit den vorherigen haben – z.B. (1,0,1,2) und (2,0,2,1).
Jetzt ergibt sich alles weitere Recht direkt, wenn die 0 an dritter Stelle und eine 1 an erster Stelle ist, muss die letzte eine 1, und dann die zweite eine 2 sein – (1,2,0,1) und (2,1,0,2).
Wenn für 0 hinten eine 1 vorne steht, müssen der zweite eine 1 und der dritte eine 2 sein – (1,1,2,0) und (2,2,1,0).

Es gibt also insgesamt ein paar Stellen, an denen aus Symmetriegründen die Wahl egal ist, danach steht der Rest fest, um Abstand zu wahren.

Ich bin darauf gekommen, indem ich mit den Graphen veranschaulicht habe. Der ist so ähnlich wie der Würfelgraph Q4, aber wo der Würfelgraph eine Kante hat, hat dieser ein Dreieck. Konstruiert wird das, indem in einem Kreis der Länge 3 alle Knoten durch einen Kreis ersetzt werden, dann nochmal und nochmal – C3*C3*C3*C3.

Ebenso kann man die Konfiguration als eine robuste Kodierung von 9 verschiedenen Nachrichten in Worte der Länge vier mit drei Buchstaben auffassen – diese Worte übertrage ich, und wenn höchstens ein Buchstabe falsch übertragen wird, kann die Nachricht noch erfolgreich rekonstruiert werden.

[Anonymous]

Anonymous wrote:

Ebenso kann man die Konfiguration als eine robuste Kodierung von 9 verschiedenen Nachrichten in Worte der Länge vier mit drei Buchstaben auffassen

Toller Vergleich!

[Anonymous]

Ich bin auf folgende Strategie gekommen:

Erst werden den Mützenfarben die Werte 0,1 und 2 zugeordnet.
Dann bekommt jeder Wichtel einen 2-dimensionalen Vektor zugeordnet (1,0), (0,1), (1,1) und (1,2).
Jetzt multipliziert man jeweils den Vektor des Wichtels mit dem Farbenwert seiner Mütze und berechnet die Summe modulo 3.
Man erhält hier 9 mögliche Ergebnisse: (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1) oder (2,2).

Die Strategie ist nun ganz einfach. Die Wichtel einigen sich, dass sie (0,0) ausschließen. Wenn ein Wichtel also die Summe der anderen drei Mützenfarben nach obiger Regel bestimmt hat und feststellt, dass es möglich ist, dass die Summe (0,0) ergibt, wenn er eine bestimmte Farbe hat, schließt er diese aus und verwendet die entsprechende Tafel.

Tatsächlich gibt es, wenn die Summe nicht (0,0) ist, immer genau einen Wichtel, der durch Wechsel seiner Mützenfarbe die Summe auf (0,0) ändern könnte (der hebt dann nicht Tafel 7). Wenn die Summe (0,0) ist, werden alle Wichtel ihre tatsächliche Farbe ausschließen und alle gleichzeitig falsch liegen. Dies geschieht aber nur in einem von neun Fällen.

[Anonymous]

Eine mögliche „M=72-Strategie“ wurde ja bereits schön und ausführlich beschrieben. Eben lese ich eine Variation von Jewi – teste ich nachher gleich… Hier noch ein paar weitergehende Überlegungen (insbesondere zu Taktiken unterhalb von 72) zu dieser wirklich wunderbaren Mützen-Aufgabe:

Man kann den Zufall natürlich nicht austricksen: Ein Wichtel, der ein 2-Farben-Schild hochhält, liegt zu einem Drittel daneben – das kann man nicht ändern: Mit der simplen Taktik : „Atto codiert Bilbos Mützenfarbe mit einem 2 Farbenschild (inverse Farben)“ verliert man natürlich 81*1/3= 27 Fälle, da Atto in allen 81 Kombinationen ein 2-Farbenschild hochhält.

Mit oben bereits beschriebener Taktik (siehe Beiträge von „murks und „Linsen_mit_Spätzle“) teilen sich die 4 Wichtel die 81 Kombinationen geschickt auf: Jeder Wichtel zeigt nur noch in einem Drittel aller Fälle (27) ein 2-Farben-Schild, sprich pro Wichtel fallen dann nur noch 81 * 1/3 * 1/3 = 9 Kombinationen raus. Durch geschicktes Festlegen auf diese 9 Kombinationen im Vorfeld, sind diese 9 „schlechten“ Kombinationen bei allen 4 Wichteln dieselben (quasi aufeinander geschoben), die 18 „guten“ Kombinationen aber bei allen 4 Wichteln unterschiedlich: 4*18=72 Kombinationen gehen durch.

Ein schönes Beispiel für Schwarmintelligenz: Ausnutzen der Info/ Verschränkung im Gesamtsystem. Gruppentaktik schlägt Individualtaktik.

Beim Festlegen von 9 „schlechten“ Kombinationen (paarweise Übereinstimmung an genaue einer Stelle) gefällt mir auch der Weg von Matheschlumpf recht gut, nur würde ich die Reihenfolge verändern, dann erkennt man die Systematik etwas besser: {(x,y,x+y,x-y) | x,y = 0,1,2 mod (3)} – liefert systematisch (man beachte die 4 Spalten)

0000
0112
0221

1011
1120
1202

2022
2101
2210

Spalte 1: 000 111 222
Spalte 2: 012 012 012
Spalte 3: 012 120 201 (Dreiergruppen-Anfang 0.. 1.. 2.. dann aufsteigend in mod 3)
Spalte 4: 021 102 210 (Dreiergruppen-Anfang 0.. 1.. 2.. dann absteigend in mod 3)

Ich persönlich hing lange in der „M=60-Theorie“ fest – war sozusagen funktional fixiert:
Info im Gesamtsystem: „Farbkonstellation“ (Die Wichtel achten nur auf Anzahl verschiedener Farben, die sie sehen) – Da geht natürlich viel Info über das Gesamtsystem (81 verschiedene Kombinationen!) verloren– passender Kommentar von Linsen_mit_Spätzle: „Nebelkerze“

In dieser Blase (man achtet nur auf Anzahl verschiedener Farben, die die Wichtel sehen), ist 60 tatsächlich optimal! Bleibt man in ihr hängen (funktionale Fixierung), wird man 60 nicht überbieten können – ich hatte für die 60ger Taktik vier verschiedene Strategien gefunden:

Vier 60ger-Strategien:
https://www.dropbox.com/s/ygpw2h3u2ac37qu/18_nichtopt_Muetzen_Blokhuis.JPG?dl=0

Für mich persönlich gehört diese Mützenaufgaben in die Top-Drei der kniffligsten Mützenaufgaben ever (ist natürlich Ansichtssache): Wer die anderen nicht kennt und Spaß an der diesjährigen hatte, muss sie sich unbedingt im Archiv anschauen (ohne in der Lösung zu spickeln! ☺) Noch einmal vielen Dank an Aart Blokhuis – suuuuper Aufgabe!!!!

Top Drei “kniffligste Mützen” (andere waren auch sehr schön, aber einfacher)
23.12.2015 „Mützen und Zahlen“ Blokhuis & Woeginger
17.12.2016 „Mützen“ Blokhuis & Woeginger
18.12.2021 „Die Mützenaufgabe 2021“ Blokhuis

[Anonymous]

Hi.
Ich finde das wirklich faszinierend. Ich frage mich allerdings, wie man auf diese Vorschrift kommt.

[Author]

Posts