Mützenaufgabe ?

[Fanbusfahrer]

Man vereinbart die Sichtrichtung des ersten Wichtels (also aus seiner Sicht; und er stellt sich entsprechend hin) als allgemeine Sichtrichtung. Dann ist das Problem aus der Welt ;-)

[Feles]

Die Wichtel stehe auf einer Plattform. Und unter dieser ist die Linie auf einer rotierenden Ebene 
#ProblemWiederHergestellt

Ist ja wurscht, ob man jetzt ein rechts/links der Linie oder vor/hinter Wichteln annehmen kann - auch ohnrdiese Annahme klappt es bei 9 Wichteln.

[Mathe Juergen]

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

Es ist doch völlig egal, ob der Elf 1 schon auf der Linie steht oder ob der Weihnachtsmann ihn erst dazu auffordert auf die Linie zu gehen. Elf 2 definiert die "Farbe" der beiden Halbgeraden und nicht Elf 1. 

[Feles]

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

Es ist doch völlig egal, ob der Elf 1 schon auf der Linie steht oder ob der Weihnachtsmann ihn erst dazu auffordert auf die Linie zu gehen. Elf 2 definiert die "Farbe" der beiden Halbgeraden und nicht Elf 1. 

Aber woher sollen die anderen Wichtel wissen, ob Wichtel 2 mit seiner Wahl den roten oder den blauen Strahl (oder die plus oder die minus Richtung oder wie auch immer du es nennen magst) definiert? Sie wissen ja nicht, wie viele Mützen welcher Farbe Wichtel 2 sieht.

[Mathe Juergen]

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

Es ist doch völlig egal, ob der Elf 1 schon auf der Linie steht oder ob der Weihnachtsmann ihn erst dazu auffordert auf die Linie zu gehen. Elf 2 definiert die "Farbe" der beiden Halbgeraden und nicht Elf 1. 

Aber woher sollen die anderen Wichtel wissen, ob Wichtel 2 mit seiner Wahl den roten oder den blauen Strahl (oder die plus oder die minus Richtung oder wie auch immer du es nennen magst) definiert? Sie wissen ja nicht, wie viele Mützen welcher Farbe Wichtel 2 sieht.

Meine Lösung verwendet nicht das "gerade - ungerade" - Prinzip (siehe oben). Alle Elfen (außer dem Elf 1) sieht doch die Mützenfarbe von Elf 1 (die ja Elf 2 codiert), also wissen doch alle wo "rot" oder "blau" ist. Und Elf 1 weiß es nachdem sich Elf 3 positioniert hat (da Elf 1 ja die Mützenfarbe von Elf 2 sieht). 

[Feles]

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) .

Hast du das mal für n=3 durchgespielt? Und was ist direkt links und direkt rechts wenn oBdA immer zwischen 2 Wichteln noch ein dritter passen soll (bezüglich direkt) und was ist links/rechts auf der Linie, wenn da nur ein Wichtel steht und man die Linie von beiden Seiten betrachten kann?

[Mathe Juergen]

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) .

Hast du das mal für n=3 durchgespielt? Und was ist direkt links und direkt rechts wenn oBdA immer zwischen 2 Wichteln noch ein dritter passen soll (bezüglich direkt) und was ist links/rechts auf der Linie, wenn da nur ein Wichtel steht und man die Linie von beiden Seiten betrachten kann?

Klar für n = 3 funktionieren die Strategien nicht, um alle Elfen "durchzubekommen" (da schafft man nur 2, der dritte Elf stellt sich zwischen die beiden, falls sie die gleiche Mützenfarbe haben und nicht zwischen die beiden ersten, falls sie verschiedene Mützenfarben haben). Direkt ist ganz einfach für Elf 8: Elf 2 hat ja die Farbe des Strahls "definiert". Elf 8 stellt sich also so auf den richtigen (vorher verabredeten) Strahl, dass zwischen ihm und Elf 1 niemand anderes steht (das geht nach Aufgabentext immer).
By the way: Für n = 1 funktioniert keine Mützenaufgabe (außer einer mit Spiegel) 

[Feles]

Gut... Dann versteh ich nicht, warum wir hier diskutieren, wenn du zu demselben Schluss wie in meinen Beitrag 7 kommst xD

Ohne Zusatzannahmen geht es nicht für n <= 3
Mir Zusatzannahmen (dazu hatte ich Vorder-/Rückseite von Wichteln genommen oder man nimmt ein Links/Rechts der Linie) geht es auch für n = 3.

Da nehm ich lieber eine Variante ohne Zusatzannahme (etwa Beitrag 7) - mir ist nur nicht klar, was in deiner ersten Antwort "links" oder "rechts" von Wichtel 1 bedeutet. Aber gut... Er stellt sich auf eine Seite/Strahl (egal welche) und relativ zu Wichtel 1 ist dies dann jene Seite der Mützenfarbe von Wichtel 1. So stellen sich alle anderen relativ zu Wichtel 1 hin und der zuvorige Wichtel erfährt damit seine Farbe... Damit Wichtel 1 seine Farbe erfährt, muss es dann aber sogar mindestens 5 Wichtel nach deiner Strategie geben? 

Angenommen es gebe nur 4 Wichtel. Wichtel 1 stellt sich irgendwo hin, Wichtel 2 definiert den Strahl auf dem die Farbe von Wichtel 1 ist. Nun kennt noch keiner seine Farbe... Wichtel 3 muss sich jetzt so stellen, dass Wichtel 1, 2 und da er der vorletzte Wichtel ist auch Wichtel 4 seine Farbe erkennt... Er muss also bis zu 8 Informationen weitergeben (wenn du nicht über Paritäten gehst), hat aber nur 3 Positionen zur Verfügung? 

Wenn du magst, kannst du mir noch erklären, wie deine Lösung für n = 4 funktioniert ohne Zusatzannahmen.

[Mathe Juergen]

Gut... Dann versteh ich nicht, warum wir hier diskutieren, wenn du zu demselben Schluss wie in meinen Beitrag 7 kommst xD

Ohne Zusatzannahmen geht es nicht für n <= 3
Mir Zusatzannahmen (dazu hatte ich Vorder-/Rückseite von Wichteln genommen oder man nimmt ein Links/Rechts der Linie) geht es auch für n = 3.

Da nehm ich lieber eine Variante ohne Zusatzannahme (etwa Beitrag 7) - mir ist nur nicht klar, was in deiner ersten Antwort "links" oder "rechts" von Wichtel 1 bedeutet. Aber gut... Er stellt sich auf eine Seite/Strahl (egal welche) und relativ zu Wichtel 1 ist dies dann jene Seite der Mützenfarbe von Wichtel 1. So stellen sich alle anderen relativ zu Wichtel 1 hin und der zuvorige Wichtel erfährt damit seine Farbe... Damit Wichtel 1 seine Farbe erfährt, muss es dann aber sogar mindestens 5 Wichtel nach deiner Strategie geben? 

Angenommen es gebe nur 4 Wichtel. Wichtel 1 stellt sich irgendwo hin, Wichtel 2 definiert den Strahl auf dem die Farbe von Wichtel 1 ist. Nun kennt noch keiner seine Farbe... Wichtel 3 muss sich jetzt so stellen, dass Wichtel 1, 2 und da er der vorletzte Wichtel ist auch Wichtel 4 seine Farbe erkennt... Er muss also bis zu 8 Informationen weitergeben (wenn du nicht über Paritäten gehst), hat aber nur 3 Positionen zur Verfügung? 

Wenn du magst, kannst du mir noch erklären, wie deine Lösung für n = 4 funktioniert ohne Zusatzannahmen.

 Zunächst noch eine Vorbemerkung: Bei meiner Strategie ist es egal auf welchen Elf sich E8 bezieht beim Codieren von E7 und E9 (man muss es nur vorher festlegen), ich habe eben E1 gewählt.

So jetzt zu n=4: Also E1 stellt sich hin wo er will (auf der Linie) und definiert damit den Anfangspunkt der beiden "Farbstrahlen". E2 kennt die Farbe von E1 und stellt sich ebenfalls irgendwo auf die Linie (wo es ihm gerade gefällt), damit hat er für sich und E3 und E4 die "Farbrichtungen" festgelegt. Diese Farbrichtung gilt jetzt für alle weiteren Strahlen, deren Anfangspunkt durch weitere Elfen festgelegt wird. Jetzt vereinbaren die Elfen vorher, dass sich E3 auf E2 bezieht, wenn er die Mützenfarbe von E2 und E4 codiert und legen z.B. fest "gehe von E2 aus in die blaue Richtung und stelle dich dort hin, falls E2 und E4 die gleiche Mützenfarbe besitzen" ansonsten eben in die rote Richtung .
Da E1 ja auch sieht, ob E2 und E4 die gleiche oder eine verschiedene Mützenfarbe haben, weiß jetzt auch E1 wo die blaue Richtung ist und somit kennt er auch seine eigene Mützenfarbe (da er ja sieht, in welcher Farbrichtung von ihm aus betrachtet E2 steht). Somit wissen jetzt E1, E2 und E4 ihre Mützenfarbe. E4 codiert dann E3 indem er sich auf E3 bezieht und sich auf die blaue oder rote Seite (Richtung) von E3 aufstellt. 

[Feles]

Okay... Geht dann auch so, wobei man hier gleiche vs. verschiedene Farbe als vorletzter Wichtel codieren muss.
Die Lösung mit der Parität finde ich da etwas einfacher...