Lösung zu noch einem Marterpfahl-Rätsel

Die Lösung zum zweiten Marterpfahl-Rätsel steht ja noch aus… Also, wie können möglichst viele die Cowboys ihre Haut retten? Überraschenderweise gibt es eine Möglichkeit, so dass jeder Cowboy außer einer mit Sicherheit überlebt, also die Farbe seiner Feder erraten kann. Und zwar völlig egal, wie viele Cowboys es sind. Dazu müssen sich die Cowboys nachts in ihrem Gefängnis-Tipi auf folgendes Vorgehen einigen:

Der hinterste Cowboy – also der, der alle anderen Federn sehen kann – zählt die schwarzen Federn vor sich. Kommt er auf eine gerade Zahl, so sagt er weiß, kommt er auf eine ungerade Zahl, so sagt er schwarz. Seine eigene Feder spielt bei seinen Überlegungen also keine Rolle – wie könnte sie auch, schließlich kennt er sie nicht. Somit bleibt sein Überleben eine Frage des Glücks…

Nun ist der zweit hinterste Cowboy an der Reihe. Auch er zählt die schwarzen Federn vor sich und kommt auf eine gerade oder auf eine ungerade Zahl. Nun kennt er die Aussage des Cowboys hinter sich und kann daraus auf seine eigene Feder schließen.

Es ist Zeit für ein Beispiel, glaube ich: Nehmen wir fünf Cowboys, mit Federfarben „schwarz“, „schwarz“, „weiß“, „schwarz“, „weiß“, von vorne nach hinten. Der hinterste Cowboy sieht drei schwarze Federn vor sich – also eine ungerade Zahl – und sagt somit schwarz. Ups, er geht jetzt drauf, sorry… Nun ist der zweit hinterste Cowboy dran, er zählt und findet zwei schwarze Federn – also eine gerade Anzahl – vor sich. Da der Cowboy hinter ihm eine ungerade Anzahl an schwarzen Federn gesehen hat (er hat ja „schwarz“ gesagt), und er selber eine gerade Anzahl an schwarzen Federn vor sich sieht, muss seine eigene Feder eine Schwarze sein. Folglich sagt er schwarz und weiß, dass er richtig liegt.

Und jetzt ist der drittletzte Cowboy dran: Er zählt, findet zwei schwarze Federn – also eine gerade Anzahl – vor sich. Nun: der letzte Cowboy sah eine ungerade Anzahl (weil er „schwarz“ sagte), der vorletzte hatte eine schwarze Feder (weil er „schwarz“ sagte), folglich muss seine eigene Feder weiß sein. Genauso können der zweite und zum Schluss der erste Cowboy nacheinander ihre Farben bestimmen.

So, das war viel viel Gelabber – jetzt verknappen wir das mal auf Mathematisch! Könnt ihr in Restklassen rechnen? Das geht so: Wir benutzen nur die zwei Zahlen 0 und 1. Erst kommt die 0, dann die 1, und nach der 1 kommt wieder die 0, also 0, 1, 0, 1, 0, … D.h., alle geraden Zahlen sind „0“, alle ungeraden Zahlen sind „1“ (das ist jeweils gerade der Rest, wenn man die Zahl durch 2 teilt, deswegen die Bezeichnung „Restklasse“). Dann gilt z.B. 1 + 1 = 0, denn statt „2“ sagen wir ja „0“. Wir interessieren uns also nur dafür, ob eine Zahl gerade oder ungerade ist. Das ganze nennt sich der Restklassenring ℤ2, aber das ist nicht so wichtig.

Jetzt passiert folgendes: wir sagen „schwarz“ = 1, „weiß“ = 0 und rechnen wie oben in der Restklasse. Der hinterste Cowboy addiert die Federn vor sich:

F1 + F2 + F3 + F4 = „schwarz“ + „schwarz“ + „weiß“ + „schwarz“ = 1 + 1 + 0 + 1 = 1,

er sagt also „schwarz“ ( = 1). Der zwei hinterste Cowboy addiert die Federn vor sich:

F1 + F2 + F3 = „schwarz“ + „schwarz“ + „weiß“ = 1 + 1 + 0 = 0.

Dann rechnet sich seine eigene Feder als Differenz der Federn, die der Cowboy hinter sich sieht und den Federn, die er selber vor sich sieht, also:

F4 = (F1 + F2 + F3 + F4) – (F1 + F2 + F3) = 1 – 0 = 1. Er hat also 1 = „schwarz“.

Der mittlere Cowboy sieht dann zwei Federn vor sich: F1 + F2 = 1 + 1 = 0. Für seine Feder gilt:

F3 = (F1 + F2 + F3 + F4) – F4 – (F1 + F2) = 1 – 1 – 0 = 0 = „weiß“.

Und der zweite Cowboy sieht F1 = 1 und weiß somit

F2 = (F1 + F2 + F3 + F4) – F4 – F3 – F1 = 1 – 1 – 0 – 1 = 1 = „schwarz“,

womit auch der vorderste Cowboy seine eigene Farbe kennt:

F1 = (F1 + F2 + F3 + F4) – F4 – F3 – F2 = 1 – 1 – 0 – 1 = 1 = „schwarz“.

Und das tolle daran ist, dass das auch mit mehreren Farben genauso funktioniert. Gibt es z.B. vier verschiedene Feder-Farben, so ordnet man jeder der Farben eine Zahl von 0 bis 3 zu und rechnet dann genau wie oben, nur im Restklassenring ℤ4, also mit 0, 1, 2, 3, 0, 1, 2, 3, …

weitere Pfeffernüsse