Wenn mich nicht alles täuscht, funktioniert hier der "übliche" Trick - der erste stellt sich irgendwo hin, der zweite stellt sich links oder rechts vom ersten, je nachdem, ob er eine gerade oder ungerade Zahl von blauen Hüten sieht. Dann wissen der erste sowie der 3. bis 9., welchen Hut sie aufhaben. Nun muss nur noch der zweite Wichtel seine Hutfarbe herausfinden. Das teilt ihm der dritte Wichtel mit, indem er sich rechts, bzw. links vom zweiten stellt. Wo sich dann Wichtel 4 bis 9 hinstellen, ist wurscht.
Oder hab ich was falsch verstanden?
Frohes Neues an alle und vielen Dank für den Rätselspaß! ???
Meine Lösung sieht so aus:
Der Elf 1 stellt sich irgendwo auf die Linie. Der Elf 2 codiert die Hutfarbe von Elf 1 (z.B. links von 1 bedeutet rot und rechts von 1 bedeutet blau). Anschließend codiert Elf (k+1) die Hutfarbe von Elf k indem er sich ebenfalls entweder links oder rechts von Elf k hinstellt. Somit können die Elfen 1 bis 8 ihre Hutfarbe erfahren, allerdings Elf 9 nicht. Damit Elf 9 seine Hutfarbe kennt, muss Elf 8 (außer der Hutfarbe von Elf 7) auch die Hutfarbe von Elf 9 codieren. Dies muss daher Elf 8 sein, da nur Elf 8 weiß, wer Elf 9 ist (bis auf den Weihnachtsmann natürlich, der weiß das auch). Elf 8 codiert daher, ob Elf 7 und Elf 9 die gleiche Hutfarbe oder eine unterschiedliche Hutfarbe haben, indem er sich z.B. direkt links oder rechts von Elf 1 aufstellt. Da Elf 7 die Hutfarbe von Elf 9 (und umgekehrt) kennt, kennt er auch seine eigene Hutfarbe. Somit kennen alle 9 Elfen ihre Hutfarbe.
Dieses Prinzip funktioniert auch mit n Elfen (also auch z.B. mit n = 42) .
Habe ich fast genauso. Sehr coole Aufgabe. Das Ganze funktioniert auch im Kreis.
PHP-Code:
Wir teilen die rechte und linke Seite der roten Linie so ein, dass, wenn man eine ungerade Anzahl an roten Mützen sieht, man nach rechts geht, andernfalls geht man nach links. Da alle Mützen bis auf die eigene gesehen werden, wissen alle, außer die Person, die sich nach rechts oder links stellt, welche Mützenfarbe sie aufhaben. Stellt sich dann die zweite Person auf eine Seite, weiß auch die erste Person seine Mützenfarbe. Sodann können alle ihre Mützenfarbe richtig raten (und das nach zwei Zügen) ?. Wir vollziehen abschließend noch ein Beispiel: Angenommen es sind 4 rote und 5 blaue Mützen verteilt worden. Die Person mit einer blauen Mütze stellt sich sodann nach rechts. Die Personen mit der roten Mütze sehen drei rote Mützen, die Personen mit blauen Mützen sehe 4 rote. Da die Person 1 sich nach rechts gestellt hat, ist die Anzahl an roten Mützen für die Person gerade. Die drei Personen mit roter Mütze, die nur drei rote Mützen sehen, wissen sodann, dass ihre Mütze rot sein muss. Die anderen Personen mit blauer Mütze, die 4 rote Mützen sehen, wissen sodann, dass ihre Mützen blau sind. Einzig die erste Person kennt ihre Mützenfarbe noch nicht. Stellt sich nun die Person mit einer blauen Mütze, die ja vier rote Mützen sieht nach rechts, so weiß Person 1, die ja auch vier rote Mützen sieht, dass ihre Mütze blau ist. Stellt sich nun eine Person mit roter Mütze nach links, so weiß die erste Person auch, dass ihre Mützenfarbe blau sein muss. Dahinter steckt die Kodierungsstrategie.
Das geht auch einfacher/naheliegender. Das Ziel ist, dass alle roten Mützen sich nach links stellen und die blauen nach rechts. Jeder neu hinzukommende Wichtel stellt sich zwischen den am weitesten rechts stehenden Wichtel mit roter Mütze und den am weitesten links stehenden Wichtel mit blauer Mütze. (Wenn es keinen roten Wichtel gibt, dann halt ganz nach links -- und symmetrisch wenn es keinen blauen gibt ganz nach rechts.)
(01-01-2024, 03:43 PM)ukleinek schrieb: Das geht auch einfacher/naheliegender. Das Ziel ist, dass alle roten Mützen sich nach links stellen und die blauen nach rechts. Jeder neu hinzukommende Wichtel stellt sich zwischen den am weitesten rechts stehenden Wichtel mit roter Mütze und den am weitesten links stehenden Wichtel mit blauer Mütze. (Wenn es keinen roten Wichtel gibt, dann halt ganz nach links -- und symmetrisch wenn es keinen blauen gibt ganz nach rechts.)
So hatte ich auch erst überlegt - aber dann weiß der letzte Wichtel seine Mützenfarbe leider noch nicht.
Aber Wichtel Nr. 2 kann eine Information für den letzten Wichtel übermitteln, indem er sich abhängig von der Zahl an roten bzw. blauen Mützen (gerade / ungerade), die er sieht, links oder rechts von Wichtel Nr. 1 aufstellt.
Dadurch wissen alle außer Wichtel Nr. 2 ihre Farbe - und wenn man soweit schon ist, kann auch Wichtel Nr. 3 nach dem gleichen Prinzip verfahren, dann weiß auch Wichtel Nr. 2 Bescheid und die Aufstellung nach Farben ist gar nicht mehr nötig.
(Also wie in #1 beschrieben.)
Oh, wie ärgerlich, da hab ich nicht genau genug gelesen. Ich hatte auch den Klassiker "stell dich immer an die Farbgrenze" im Kopf, da ich die Elfen immer direkt platziert hatte, wenn sie ihre Mütze bekommen haben. Dass ein Elf, der sich auf die Linie stellt, zu diesem Zeitpunkt die Mützen aller anderen Elfen kennt und nicht nur die derjenigen, die schon auf der Linie stehen, macht natürlich einen entscheidenden Unterschied...
Es ändert zwar nix an der Antwort... Aber bisher scheinen mir die Lösungen falsch. Wir wissen nicht, ob es ein rechts/links auf der Linie gibt... Dazu müsste man wissen, dass alle Wichtel auf derselben Seite der Linie stehen. Außerdem wissen wir nicht, ob die Wichtel eine Vorder- und Rückseite haben (man könnte sie sich als Punkt oder Stab vorstellen), denn nur dann könnte man mit sich vor oder hinter einem Wichtel stellen argumentieren.
Insgesamt muss daher davon ausgegangen werden, dass die ersten beiden Wichtel keinerlei Informationen auf einer Linie vermitteln können. Erst der dritte Wichtel kann sich in verschiedenen Positionen (3 Stück) stellen in Relation zu den ersten beiden... Etwa:
Zwischen den ersten beiden, wenn er eine gerade Anzahl an roten Mützen sieht.
Nicht zwischen den ersten beiden, wenn er eine ungerade Anzahl an roten Mützen sieht.
Alle weiteren Wichtel können sich so hinstellen in Bezug auf den ersten beiden Wichteln (es genügt eigentlich, wenn der vierte dem dritten noch eine Info gibt). Auch hier finden alle ihre Mützenfarbe heraus.
Auf einem Kreis könnten sogar die ersten drei Wichtel keinerlei Information vermitteln. 4 und 5 schaffen es dann aber, damit jeder seine Mützenfarbe kennt:
Wichtel 4 und 5 stellen sich jeweils zwischen 1 und 2 auf demselben Kreissegment wie Wichtel 3 bei einer geraden Anzahl roter Mützen, ansonsten nicht auf demselben Kreissegment wie Wichtel 3.
Zusatzannahmen wie es geben ein rechts und links auf der Linie sollte man nicht treffen für eine korrekte Lösung, da dies vor allem bei kleiner Wichtelanzahl einen Einfluss auf die richtige Lösung hat.
(01-02-2024, 11:34 AM)Feles schrieb: Es ändert zwar nix an der Antwort... Aber bisher scheinen mir die Lösungen falsch. Wir wissen nicht, ob es ein rechts/links auf der Linie gibt... Dazu müsste man wissen, dass alle Wichtel auf derselben Seite der Linie stehen. Außerdem wissen wir nicht, ob die Wichtel eine Vorder- und Rückseite haben (man könnte sie sich als Punkt oder Stab vorstellen), denn nur dann könnte man mit sich vor oder hinter einem Wichtel stellen argumentieren.
Insgesamt muss daher davon ausgegangen werden, dass die ersten beiden Wichtel keinerlei Informationen auf einer Linie vermitteln können. Erst der dritte Wichtel kann sich in verschiedenen Positionen (3 Stück) stellen in Relation zu den ersten beiden... Etwa:
Zwischen den ersten beiden, wenn er eine gerade Anzahl an roten Mützen sieht.
Nicht zwischen den ersten beiden, wenn er eine ungerade Anzahl an roten Mützen sieht.
Alle weiteren Wichtel können sich so hinstellen in Bezug auf den ersten beiden Wichteln (es genügt eigentlich, wenn der vierte dem dritten noch eine Info gibt). Auch hier finden alle ihre Mützenfarbe heraus.
Auf einem Kreis könnten sogar die ersten drei Wichtel keinerlei Information vermitteln. 4 und 5 schaffen es dann aber, damit jeder seine Mützenfarbe kennt:
Wichtel 4 und 5 stellen sich jeweils zwischen 1 und 2 auf demselben Kreissegment wie Wichtel 3 bei einer geraden Anzahl roter Mützen, ansonsten nicht auf demselben Kreissegment wie Wichtel 3.
Zusatzannahmen wie es geben ein rechts und links auf der Linie sollte man nicht treffen für eine korrekte Lösung, da dies vor allem bei kleiner Wichtelanzahl einen Einfluss auf die richtige Lösung hat.
Rein mathematisch betrachtet ist die Linie eine Gerade (wenn man mal von der Endlichkeit des Raumes absieht). Wenn man einen Punkt (Elf 1) auf diese Gerade stellt, dann definiert dieser Punkt den Anfangspunkt von zwei Halbgeraden (Strahlen). Ob man das nun "links" und "rechts" oder "42" und "nicht 42" nennt, ist völlig egal. Elf 2 kann sich entschieden auf welche Halbgerade er sich stellt. Elf 2 "sieht" die Mützenfarbe von Elf 1 (und alle anderen 7 Elfen auch), somit "definiert" Elf 2 welcher der "blaue Strahl" bzw. "rote Strahl" ist. Elf 1 bekommt dann spätestens, wenn Elf 3 sich auf den entsprechenden Strahl stellt, welcher der "blaue" und "rote" Strahl ist und kennt somit auch seine Farbe.
So sehe ich es auch. Auch wenn ich davon ausgegangen bin, das alle links und rechts unterscheiden können (auf einer endlichen Linie), so war mir klar, dass spätestens nach Person 3 alles klar ist, wenn sie es nicht können^^
Angenommen die Linie geht mitten durch die Menge der Wichtel und einer steht schon drauf... Was ist dann links und was rechts vom ersten Wichtel? Nach welcher Teilmenge der Wichelt soll man dann gehen xD
.