20: Die Mützenaufgabe 2018 / Hat Challenge 2018

  • Zunächst nenne ich die Wichtel ABC und die Farben 0 bis 4. Welche welche ist, sprechen die Wichtel natürlich vorher ab. Nun grenze ich zunächst N nach oben ab: A hat nur die Information über die beiden Farben, die B und C tragen, und sonst nichts. Er kann also (für sich) nichts Besseres machen, als zwischen den drei verbleibenden Farben zu raten, und wird zu 1/3 richtig liegen. Damit kann N nicht größer als 60/3=20 sein.


    Was A aber machen kann, ist, B und C einen Tipp zu geben, was sie auf dem Kopf haben. Nach ein wenig Herumprobieren habe ich folgende Taktik gefunden:

    A nimmt die beiden Zahlen von B und C, und addiert sie. Das Ergebnis wird modulo 5 genommen. Ist die Zahl nun gerade, wird durch zwei geteilt, ist sie ungerade, wird erst +5 gerechnet und dann durch 2 geteilt. Das Ergebnis dieser Rechnung, X, rät A.

    B und C kennen also X und können durch Umkehrung der obigen Rechnung (B+C)mod5 bestimmen. Da B aber C kennt, weiß er damit seine eigene Zahl, die er entsprechend rät.

    C kennt danach B und kann eben auch die eigene Zahl richtig erraten.


    Diese Taktik sorgt dafür, dass B und C immer richtig liegen. Was noch überprüft werden muss, ist, dass X immer ungleich B und C ist, denn sonst wäre der Tipp von A ja sicher falsch und nicht, wie oben behauptet, in 20 Fällen richtig. Das ist für alle Beispiele schnell nachgeprüft (genaugenommen habe ich die Taktik natürlich andersherum ausgearbeitet – erst alle Kombinationen von B und C aufgeschrieben, dann modulo 5 gruppiert, und dann geschaut, welche Zahl dabei jeweils nicht vorkommt. So ergab sich obige Rechnung, die man auch durch eine kleine Tabelle ersetzen kann, wenn einem das lieber ist.).

    Glücklicherweise kann man mit der Taktik direkt N=20 Fälle abdecken und ist damit fertig – am 20. habe ich mir danach erstmal einen

  • Atto musste als Erster raten. 3 Farben kamen in Frage, er hatte hierzu keine weiterführenden Hinweise. Die Wahrscheinlichkeit, dass er seine Farbe richtig erraten würde war 1/3, wie auch immer er sich entschiede.

    „1/3 ist also die nicht überschreitbare Obergrenze einer Gewinnwahrscheinlichkeit für die Gesamtstrategie“, grummelte er. D.h. N <= 20.

    Immerhin: für den Fall, dass Atto mit Glück die richtige Wahl treffen würde, hatten sich die drei Wichtel eine Strategie ausgedacht, der sie den Namen Farbensudoku-Strategie“ gaben. Mit dieser Strategie, so waren sie sich sicher, würden Chico und Bilbo ihre Mützenfarben richtig erraten. D.h. N = 20

    Sie dachten sich ein Farbensudoku-Rätsel aus, in dem die 5 Farben in der Diagonalen oben-links bis unten-rechts vorgegeben waren. (Im Folgenden steht das Wort Diagonale für genau diese Diagonale) Die übrigen Felder waren so mit einer Farbe auszufüllen, dass in jeder Zeile und in jeder Spalte jede der 5 Farben genau einmal vorkam.


    Für die drei Intelligenzwichtel war das Sudoku-Rätsel keine echte Herausforderung. Schnell hatten sie eine Lösung gefunden

    weiss rot blau schwarz gelb
    rot gelb schwarz weiss blau
    schwarz blau

    rot

    gelb weiss
    gelb schwarz weiss blau rot
    blau weiss gelb rot schwarz


    Auf Basis dieser Lösung definierten Sie folgende Gewinn-Strategie:

    Für die Erläuterung zu beachten: jede Zeile und jede Spalte hat genau ein Feld in der Diagonalen. (Felder, die fett und unterstrichen sind). Die Positionen dieser Felder bezeichnen wir im Folgenden als die eindeutigen Diagonalenpositionen einer Spalte bzw. einer Zeile.


    Regel für Atto: Suche in der Zeile mit Bilbos Farbe in ihrer Diagonalenposition das Feld mit Chicos Farbe. Wähle die Farbe in der Diagonalenposition der zu diesem Feld gehörigen Spalte.


    Regel für Bilbo: Suche in der Spalte mit Attos Farbe in ihrer Diagonalenposition das Feld mit Chicos Farbe. Wähle die Farbe in der Diagonalenposition der zu diesem Feld gehörigen Zeile.


    Regel für Chico: Wähle die Farbe des Feldes, für das gilt: Das Feld liegt in der Zeile mit Bilbos Farbe in ihrer Diagonalenposition und in der Spalte mit Attos Farbe in ihrer Diagonalenposition.

  • Oh, ich hatte einen komplett anderen Gedanken.

    Man stellt sich alle fünf möglichen Farben (seien hier A, B, C, D und E genannt) in einem Kreis vor, im Uhrzeigersinn angeordnet.

    Der hintere Wichtel sieht nun entweder zwei benachbarte Farben (z.B. A und B, oder A und E) oder mit einem Mindestabstand von 1 (z.B. A und D oder A und C).

    Sagt nun der hintere Wichtel die Farbe, aus deren Sicht die Farben der anderen Wichtel symmetrisch angeordnet sind (z.B. sagt er D, wenn er A und B sieht, oder B, wenn er A und C sieht), kommen für den zweiten Wichtel nur noch zwei Farbpaare in Frage. Und da er vor sich eine dieser beiden Farben sieht, weiß er, welches Paar und welche Farbe es ist. Der letzte Wichtel kennt damit das Paar und seine Farbe. Folge: nur der erste Wichtel muss raten, und das tut er mit einer Wahrscheinlichkeit von 1/3.


    Viele Grüße


    Martin

  • Ich habe die Farben auch im Kreis angeordnet, allerdings benötigt man zwei solche Kreise.

    Die Wichtel ordnen die fünf Farben in zwei Kreisen an. Die Farbpositionen sind so gewählt, dass jede mögliches Farbpaar in genau einem der beiden Kreise direkt nebeneinander positioniert sind.(diese "Kreise" lernen die Wichtel auswendig)

    z.B. (gegen den Uhrzeigersinn):


    Kreis 1: B ; G ; W ; S ; R

    Kreis 2: B ; S ; G ; R ; W

    Jetzt läuft das wie folgt:

    Beispiel: Atto sieht vor sich die Kombination (Bilbo) blau (Chico) rot

    Die beiden Farben sind im Kreis 1 benachbart. Er sagt die Farbe, die im selben Kreis der zweite Nachbar von blau ist (also grün). Er ist quasi der Grüne, denn der Grüne Punkt "sieht" das gleiche wie er vor sich.

    Was fängt jetzt Bilbo mit der Information grün an?

    Er hat noch vier Farbkombinationen zur Auswahl:

    aus Kreis 1 : blau und rot bzw. weiß und schwarz

    aus Kreis 2: schwarz und blau bzw. rot und weiß

    Er sieht aber, dass Chico rot hat, also weiß er die Farbkombination und kann sicher seine Mützenfarbe (hier blau) sagen.

    Chico hat auch die gleichen vier Farbkombinationen zur Auswahl. Er weiß aber, dass Bilbo garantiert seine richtige Mützenfarbe geannt hat und somit kennt er auch die richtige Farbkombination.

    Somit muss nur Atto Glück haben, dass er zufällig die richtige Farbe auf dem Kopf hat.

    die Wahrscheinlichkeit dafür ist 1/3. Somit ist auch die Wahrscheinlichkeit, dass alle drei die richtige Farbe nennen 1/3.

    1/3 von 60 sind 20.

    Also ist N = 20 die maximale Anzahl.

  • Ich habe auch eine komische Strategie: Die Farben seien mit 1 bis 5 bezeichnet.

    Dann baue ich eine Tabelle so auf:

    Addiere den Wert der Farben von Atto und Bilbo, bilde mod 3. Der neue Wert (für Chico) ist der Index in den verbleibenden Farben.


    Beispiel

    Atto 1, Bilbo 2: 1+2 = 3 mod 3 = 0 => Chicos Mützenfarbe ist Index 0 der verbleibenden Farben (3,4,5): 3 (Index nullbasiert)

    Atto 1, Bilbo 3: 1+3 = 4 mod 3 = 1 => Chicos Mützenfarbe ist Index 1 der verbleibenden Farben (2,4,5): 4


    Ich hatte das im Kopf gemacht, da ich auf Reisen war. Hat mich überrascht, dass es geklappt hat. :whistling:


    In jeder Zelle Jeweils die Farben von Atto Bilbo Chico (in dieser Reihenfolge), jeder Wichtel kennt nach Spielregel seine Farbe.


    1 2 3
    2 1 3
    3 1 2
    4 1 5
    5 1 2
    1 3 4
    2 3 5
    3 2 5
    4 2 1 5 2 4
    1 4 5
    2 4 1
    3 4 2
    4 3 2
    5 3 1
    1 5 2
    2 5 4
    3 5 1
    4 5 3
    5 4 3

  • Ich hab die Farben ebenfalls den Zahlen 0 bis 4 zugeordnet und die folgenden Rechnungen modulo 5 durchgeführt:


    Atto nennt das dreifache der Summe der Farben, die er sieht.

    Die anderen beiden Wichtel verdoppeln die von Atto genannte Farbe und subtrahieren die des jeweils anderen.

  • Ich denke die vermeintlich verschiedenen Lösungen liegen vom Prinzip her gar nicht so weit auseinander. Ich denke wir können uns auf Folgendes einigen:

    - Atto ist in einer vermeintlich fatalistischen Lage (kann eigentlich machen was ich will, die Erfolgswahrscheinlichkeit ist 1/3). Er muss aber seine Farbe gezielt so wählen, dass Bilbo und Chico die von Ihm genannte Farbe eindeutig auf ihre abbilden können unter Einbeziehung der Farbe des jeweils anderen (der beiden Chico oder Bilbo) als Abbildungs-Stellgröße.


    Die Matrix im Lösungsvorschlag hinter dem Link von pierrot hat Ähnlichkeit mit meinem Farbensudoku-Feld. Er schreibt da auch: in jeder roten Spalte (für Bilbo) und jeder roten Zeile (für Chico) dürfen keine gleichen Zahlen stehen.

    Wenn ich in meinen Farbauswahlregeln für Atto, Bilbo, Chico daraus hervorgehende Zahlencodes (Nummern 1-5) ermitteln würde, sähe das Sudokufeld in etwa so aus wie die Matrix bei pierrot.

  • Im Endeffekt werden hier alle Lösungen Variationen voneinander sein. Ich persönlich finde aber, dass das Finden einer guten Darstellung, die das Problem zugänglich oder sogar offensichtlich macht, maßgeblich zur "Schönheit" eines Beweises beiträgt. Und in der Hinsicht unterscheiden sich die verschiedenen Lösungsansätze dann doch. Gerade den Ansatz von shgt fand ich da sehr beeindruckend.

  • .... Gerade den Ansatz von shgt fand ich da sehr beeindruckend.

    Ja, sehr schöne Lösung "shgt" (für was steht eigentlich dein Name?). Die Kreisidee und dadurch sehr einfache Codierung ist super, da auf einen Blick ersichtlich. Mit Zahlen (etwa 0..4 im Kreis angeordnet) statt Buchstaben (A..E) wird es finde ich noch klarer.


    Generell codiert bei jeder möglichen Codierung jede Zahl (Farbe) 4 Fälle. 5 mal 4 = 20 Fälle insgesamt.


    Im Kreisschema von sght ist die Codierung maximal einfach einzusehen und daher hübsch!

    So codiert etwa die 0 hier folgende vier Fälle: 1,4 4,1 (Abstand 1) und 2,3 3,2 (Abstand 0).


    So betrachtet sollte man auch berechnen können, wie viele verschiedene mögliche Codierung insgesamt möglich sind:

    Betrachtet man eine einzelne Ziffer, so erkennt man 9 strukturell verschiedene Codierungsmöglichkeiten
    Hier die Auflistung der 9 Möglichkeiten, die von der 0 codiert werden können:


    14 41 ... die beiden hinteren ergeben sich automatisch: hier 23 und 32 (das ist die Codierung von sght)

    14 31 (dann 23 42)

    14 21 (dann 43 32)

    13 41 ...

    13 31

    13 21

    12 41

    12 31

    12 21


    Falls die Auswahl einer dieser 9 Codierung der Ziffer 0 die Codierung der anderen 4 Ziffern eindeutig festlegt, so gibt es genau 9 verschiedene mögliche Codierungen insgesamt (sprich neun verschiedene strukturelle tabellarische Zuordnungen, auf einige kommt man per Zuordnungsvorschrift: wie sght grafisch am Kreis, bzw Modulrechnung usw..., andere kann man wohl nur in Tabellenform angeben (wie meine Lösung (erster Beitrag hier). Bei den Zuordnungsvorschriften kann es sicherlich mehr als 9 geben, dann führen aber verschieden Zuordnungsvorschriften auf die strukturell gleiche tabellarische Zuordnung).


    Auf die Schnelle sehe ich erst mal keine Freiheitsgrade nach Festlegung der ersten Ziffer für die anderen... vielleicht hat ja jemand Lust dies genauer zu checken. Ist ja eigentlich eine echt interessante Frage. Wären es wirklich nur 9, so wären im Forum ja schon einige davon vorgestellt, die schönste bisher meiner Meinung nach von sght.


    P.S:

    Bei Kreisschema musste ich gleich an meine Favoriten-Aufgabe des Kalenders 2017 denken: Wer sie nicht kennt, unbedingt anschauen A13 "der beste Kartentrick aller Zeiten". Die einfache Codierung im 52ger Set läuft hier auch über die Anordnung der Karten im Kreis plus Abstände (max Abstand 6 bei 13 Karten). Wirklich interessant war dann aber die Codierung im Fall n=124 (es war zwar nur nach n max gefragt, das ging auch recht fix (Bijetkion), aber ich habe ewig nach einer Codierung gesucht. Es gibt tatsächlich eine wunderbare Codierung ohne Tabelle... einige Kalenderteilnehmer hatten sie einfach gegoogelt ;))


    Hier die Aufgabe: https://www.dropbox.com/s/33e5…13-Kartentrick-A.pdf?dl=0

  • also es gibt doch deutlich mehr als 9 verschiedene Codierungsmöglichkeite, da es doch Freiheitsgrade gibt. Wählt man für die erste Ziffer eine der neun Codierungsmöglichkeiten aus, so sind die anderen nicht alle automatisch festgelegt, aber bei weitem nicht beliebig kombinierbar (dann wären es 9 hoch 5). Vlt finde ich irgendwann mal die Zeit genauer darüber nachzudenken bzw ein Forumteilnehmer hat Lust + Zeit + eine entscheidende Idee...:)


    Mich würde schon interessieren, wie viele strukturell verschiedene Codierungsmöglichkeiten es gibt!

  • Ja, sehr schöne Lösung "shgt" (für was steht eigentlich dein Name?).


    ...


    Hier die Aufgabe: https://www.dropbox.com/s/33e5…13-Kartentrick-A.pdf?dl=0

    shgt = kürzeste Variation meines Nachnamens (mein erstes Unix-login anno 1993...)


    Und zur Aufgabe Kartentrick: Ich erinnere mich, die habe ich auch erst gelöst, als ich das Kreisschema entdeckt hatte.

    Viele Aufgaben dieses Jahr sind ja so, dass man öfter mal lange nachdenken und probieren muss, und irgendwann hat man es - oder auch nicht. Leider fehlte mir oft die Zeit, und beim intuitiven Raten bin ich nicht so gut gewesen...


    Viele Grüße

    Martin

  • Mich würde schon interessieren, wie viele strukturell verschiedene Codierungsmöglichkeiten es gibt!

    Um auf diese Frage nach der Anzahl verschiedener optimaler reiner (1 Strategien, also Tripel von 3 Funktionen X² -> X mit X = {0,1,2,3,4}, die genau 20 verschiedene Farbkombinationen treffen - zurückzukommen ...


    ... könnte umgekehrt als optimale Strategie auch jede 20-elementige Teilmenge A aus den 60 möglichen Farbkombinationen bezeichnet werden, solange sich daraus ein entsprechendes Funktionentripel ableiten ließe. Konkret hieße das:


    Sei A = { (ai,bi,ci) ∊ X³ mit i=1..20 und ai ≠ bi ≠ ci }. A ist genau dann Strategie, wenn es keine zwei verschiedenen i,j = 1..20 gibt, mit (ai,bi) = (aj,bj) oder (ai,ci) = (aj,cj) oder (bi,ci) = (bj,cj).


    Damit haben wir aber auch schon eine praktikable Konstruktionsvorschrift, die sich ohne große weitere gruppentheoretische Verrenkungen implementieren lässt, wir testen einfach die max. 95 möglichen Mengen { (ai,bi,c(ai,bi)) } auf diese Eigenschaft ( c(a,.): b->c(a,b) ist für jedes a ∊ X eine der von pierrot schon angesprochenen 9 möglichen fixpunktfreien Permutationen ).


    Folgendes Programm windet sich in 0.01s durch alle 48 (!?) verschiedenen solche Strategien.


    ----


    (1 Eine gemischte Strategie führt zu keiner höheren Gewinnwahrscheinlichkeit. Das lasse ich hier (unbewiesen) einfach mal so stehen, in der Aufgabe wurde so und so implizit von einer reinen Strategie ausgegangen.


    Anmerkung: Für N=5 hatte ich ein ähnliches Muster wie Martin (shgt). Nämlich eine arithmetische Folge A, B=A+X, C=A+2X (modulo 5). Seine "Symmetrie" entspricht gerade der arithmetischen Folge B,A,C mit A anstatt B als Mittelglied. So schön das auch ist, ein wenig schade ist nur, dass man dies bei geraden N so nicht konstruieren kann.

  • Eine gemischte Strategie führt zu keiner höheren Gewinnwahrscheinlichkeit. Das lasse ich hier (unbewiesen) einfach mal so stehen, in der Aufgabe wurde so und so implizit von einer reinen Strategie ausgegangen.

    Wenn deine konkrete Strategie die Gewinnwahrscheinlichkeit 1/3 besitzt, dann ist diese auch optimal.

    Denn ohne strategische Überlegungen ist von vorneherein klar, dass Atto seine eigene Mützenfarbe nur mit der Wahrscheinlichkeit 1/3 erraten kann. Durch eine noch so gute Strategie (die Strategie beeinflusst ja nur die Wahrscheinlichkeit, dass Bilbo und Chico ihre Mützenfarbe "erraten") kann man diese Wahrscheinlichkeit nicht steigern (spezieller Multiplikationssatz), man hat somit sofort eine obere Schranke für die Gewinnwahrscheinlichkeit. :)