spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Letztens hat ein Prof. von uns dieses durchaus interessante Rätsel gestellt. Ich bin nicht drauf gekommen (hab aber die Lösung erfahren), aber evtl. jemand von euch.

Unendlich viele Weihnachtsmänner treffen sich, nachdem sie sich über eine Strategie beraten haben stellen sie sich in eine Reihe auf, sodass jeder Weihnachtsmann alle Weihnachtsmänner vor ihm sehen kann, aber die hinter ihm nicht (jeder Weihnachtsmann sieht also unendlich viele andere Weihnachtsmänner). Nun nehmen alle Weihnachtsmänner gleichzeitige eine Müze aus ihrer Tasche die entweder rot oder blau sein kann und setzen sie auf (ohne hin zu schauen). Nun müssen alle Weihnachtsmänner gleichzeitig einen Tip über ihre Hutfarbe abgeben.
Die Frage ist: Gibt es eine Strategie, sodass nur endlich viele Weihnachtsmänner falsch liegen und wieso (gibt es sie oder eben nicht)?

Oder Mathematischer ausgedrückt: Sei §A=\left\{(a_i)_{i\in\mathbb{N}}:a\in\{rot, blau\}\right\}§ und §W:=(w_i)_{i\in\mathbb{N}}\in{}A§ die Folge der Hüte ist. Die Frage ist dann: Gibt es ein §f:A\to\{rot,blau\}§, sodass §\left|\{i: f((a)_{>{}i})\ne{}w_i, a\in{}A, i\in\mathbb{N}\}\right|<\infty§?

EDIT: natürlich muss es §f((a)_{>i})§ und nicht §f((a)_{\ge{}i})§ heißen.
EDIT2: meine "mathematische" Beschreibung war ziemlicher Müll/ungenau, weiter unten wurde das eh disktutiert

Zitat von »dot«

Abzählbar oder überabzählbar unendlich viele?

Abzählbar, steht ja in der mathematischen Beschreibung des Problems

Zitat von »Jonathan_Klein«

Hm, die Strategie ist, jeder sagt welche Mütze sein Vordermann hat, und der Vordermann merkt sich das dann und sagt es als Tip.
Wenn sie nicht sprechen dürfen ist die Antwort halt: 42!

Sie müssen ihre Antwort gleichzeitig abgeben
und 42 ist die Antwort auf die Frage nach dem Universum, dem Leben und den ganzen Rest, nicht aber auf meine Frage.

Hinweis: es reicht zu Zeigen das es eine solche Strategie gibt, nicht wie sie aussieht.

Zitat

Zur Klarstellung:

W ist außerhalb der Einflussmöglichkeiten?

Es muss also ein f gefunden werden dass für jedes W funktioniert?!

Das folgt alles aus dem Text. W ist beliebig und es muss ein f für alle W geben.

Zitat

Sollte es nicht

§f((w_i)_{i>k})\neq w_k§

heißen?

Ja sollte es, sry.

Zitat von »hanse«

Hinweis: es reicht zu Zeigen, dass es eine solche Strategie gibt, nicht wie sie aussieht.

Es reicht zu zeigen dass oder ob es eine Strategie gibt?

Da du ja damit mehr oder weniger schon angedeutet hast, dass die "richtige" Antwort ja sein soll,

Ups, da hab ich schon was verraten. Ja es gibt eine, das wieso fehlt natürlich noch.

Zitat

nehme ich an dass in der Beschreibung noch eine Sonderregel fehlt, es z.B. eine "beherrschbare" Folge mit Bildungsvorschrift und nicht eine zufällige sein soll. Die "korrekte" Heuristik wäre hier natürlich aus (w_i)_{i>k} die Bildungsvorschrift zu erraten und diese dann anzuwenden. Die Frage ist, geht das immer?

Nein, es fehlt keine Bedingung, die Folge ist beliebig, es muss für alle funktionieren.

Also mit den neuen Informationen ist die Aufgabe (§A§ wie oben):
z.Z. §\exists f:A\to\{rot,blau\},\forall (w_n)\in{}A \Rightarrow \left|\{i: f((w_n)_{n>i})\ne{}w_i, i\in\mathbb{N}\}\right|<\infty§

EDIT: das kleine a war natürlich nirgends definiert und sollte auch ein w sein. (Garnicht so einfach Latex Code zu schreiben -.-)

Zitat von »Mastermind«

Dann Entkräfte doch bitte das Argument mit der Bernoulli-Kette.

Kann ich nicht, ohne dir die Lösung zu sagen, da ich keine Ahnung von Statistik habe.

Zitat

Wenn das was du da vorschlägst ginge könnte man damit One-Time-Pad knacken. (Präziser: Es gäbe eine Dekodierungsfunktion, die auf einer unendlichen Nachricht die mit OTP verschlüsselt ist beweisbar nur endlich viele Bitfehler macht)

Das ist aber ganz was anderes!