mikrocontroller.net

Forum: Offtopic Mathe Spielereien²


Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Inspiriert von Beitrag "[Help] Mathematisches Problem" und 
meiner damaligen Theoretischen Informatik Vorlesung schmeiß ich doch mal 
folgendes kleines Spielchen in die Runde:

Du bist zusammen mit 2 Freunden zu einer Gameshow eingeladen. Die Regeln 
sind einfach: Ihr 3 bekommt jeweils per Zufall entweder einen schwarzen 
oder weißen Hut aufgesetzt (50:50). Ihr seht gegenseitig die beiden Hüte 
eurer Freunde aber nicht euren eigenen. Anschließend werdet ihr 
unabhängig voneinander gefragt welchen Hut ihr aufhattet. Ihr habt die 
Wahl ob ihr eine Antwort abgebt oder nicht. Wenn mindestens einer 
richtig und keiner falsch rät gewinnt ihr das Spiel. Eine nicht 
abgegebene Antwort zählt nicht als falsch, gibt jedoch keiner eine 
Antwort verliert ihr, da niemand eine richtige Antwort gegeben hat. Vor 
Beginn des Spiels dürft ihr eine Strategie besprechen.
Die Frage: Was für eine Strategie fahrt ihr um eure 
Gewinnwahrscheinlichkeit zu maximieren?

Für die Cracks unter euch: Das gleiche Spiel, dieselben Regeln nur mit 7 
Leuten

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:

> Die Frage: Was für eine Strategie fahrt ihr um eure
> Gewinnwahrscheinlichkeit zu maximieren?

Ist die Reihenfolge der Befragung vorher festgelegt und erfahren die 
anderen wenisgtens ob eine Antwort gegeben wurde

Ich weiß: 'unabhängige Befragung' schliesst letzteres eigentlich aus. 
Ich frag trotzdem.

Ist Zeichen geben erlaubt?  (das wär allerdings dann zu einfach)

Welche Form der Interaktion der Spieler ist erlaubt? Irgendetwas muss es 
ja geben, sonst wäre der Begriff "Strategie" nicht angebracht, weil es 
ja sonst keine Möglichkeit gibt eine bedingte Wahrscheinlichkeit zu 
konstruieren.

Oder liege ich völlig daneben?

: Wiederhergestellt durch Moderator
Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Nein, die einzige Information ist die Farbe der beiden Hüte eurer 
Mitstreiter. Keinerlei sonstige Information oder Interaktion. Ihr 
erfahrt nicht was die Mitstreiter geantwortet haben. Strategie bezieht 
sich darauf wer aufgrund seiner Beobachtung welche Antwort gibt bei der 
Befragung.

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Eine einfache Strategie:
  2 halten konsequent die Klappe und der 3te rät einfach.
  -> 50% Chance

Alles unter 50% ist daher schon mal aus dem Rennen

Autor: Stefanie B. (sbs)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Da die Wahrscheinlichkeit für meinen Hut von den anderen Hüten 
unabhängig ist, kann keiner aus den anderen Hüten erraten welchen Hut er 
auf hat.

Ergo 2 halten den Mund, einer rät.
Damit beträgt die Gesamtgewinnchance 50%.

Ok vll ein wenig anschaulicher mit einem anderen Beispiel:
Du wirfst Münzen. Es gibt Kopf und Zahl (=Hutfarbe).
Du kennst die Münzwürfe der Vergangenheit (=Hutfarbe deiner Freunde).
Was kommt beim nächsten Münzwurf (=Farbe deines Hutes) ?

Stefan

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:

> Strategie bezieht
> sich darauf wer aufgrund seiner Beobachtung welche Antwort gibt bei der
> Befragung.

Also zb sowas:
derjenige, welcher 2 Hüte in gleicher Farbe sieht, sagt die gegenteilige 
Farbe der Hüte.

Knifflig: Das Problem ist, dass die Antwort möglichst nicht falsch sein 
sollte. Im Zweifelsfall lieber keine Antwort als eine falsche.


Aber irgendwie fehlt mir da noch was.
Ob du mir die Augen verbindest oder ich die Hüte der anderen sehe, 
spielt doch keine Rolle, weil es keine Verbindung zu meinem Hut gibt.

Autor: Jeffrey Lebowski (the_dude)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
hmm, wäre nicht die Wahrscheinlichkeit dass jemand falsch antwortet, 
umso kleiner, desto weniger Personen antworten?
In diesem Fall denke ich dass die beste Canche dann besteht, wenn nur 
eine Person einen Tipp abgibt!?

Tipp von einer Person:  Canche 50:50
Tipp von zwei Personen: Canche 2x 50:50 => also 75:25 dass eine falsche 
Antwort dabei ist?
Weil: wenn die erste Person richtig liegt, gibt es immer noch 50% 
wahrscheinlichkeit dass eine (nämlich die zweite) falsche Antwort hinzu 
kommt.

Habe ich jetzt zu primitiv gedacht?

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl heinz Buchegger schrieb:
> D. I. schrieb:
>
>> Strategie bezieht
>> sich darauf wer aufgrund seiner Beobachtung welche Antwort gibt bei der
>> Befragung.
>
> Also zb sowas:
> derjenige, welcher 2 Hüte in gleicher Farbe sieht, sagt die gegenteilige
> Farbe der Hüte.

Zum Beispiel ja

Autor: Karl Heinz (kbuchegg) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
> Karl heinz Buchegger schrieb:
>> D. I. schrieb:
>>
>>> Strategie bezieht
>>> sich darauf wer aufgrund seiner Beobachtung welche Antwort gibt bei der
>>> Befragung.
>>
>> Also zb sowas:
>> derjenige, welcher 2 Hüte in gleicher Farbe sieht, sagt die gegenteilige
>> Farbe der Hüte.
>
> Zum Beispiel ja

mal sehen wohin uns das führt.
Welche Möglichkeiten gibt es

    1   2   3

    S   S   S        1, 2, 3 würden W sagen -> falsch
    S   S   W        3 würde W sagen -> richtig
    S   W   S        2 würde W sagen -> richtig
    S   W   W        1 würde S sagen -> richtig
    W   S   S        1 würde W sagen -> richtig
    W   S   W        2 würde S sagen -> richtig
    W   W   S        3 würde S sagen -> richtig
    W   W   W        alle 3 würden S sagen -> falsch


6 Richtige von 8 Möglichen.
Ich würde sagen: gar nicht so schlecht.
Gewinnwahrscheinlichkeit: 75%

gehts noch besser?   (Biiiiittteeee, wenigstens hier einen Tipp)

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Karl Heinz hats raus, so ist es, 75% besser gehts nicht.

So jetzt für die Profis das gleiche für 7 Personen auf gehts :)

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
D. I. schrieb:
>> Also zb sowas:
>> derjenige, welcher 2 Hüte in gleicher Farbe sieht, sagt die gegenteilige
>> Farbe der Hüte.
>
> Zum Beispiel ja

Zum Beispiel ...

Das impliziert ja, dass es noch weitere optimale Strategien gibt :)

Tatsächlich gibt es noch eine zweite, die ich mittels eines Brute-
Force-Algorithmus herausgefunden habe:

  Einer der drei Spieler — nennen wir ihn A — handelt folgendermaßen:
  Sieht er zwei gleichfarbige Hüte, gibt er als Antwort die Farbe dieser
  Hüte, andernfalls sagt er nichts.

  Die beiden anderen Spieler handeln so: Sehen sie zwei unterschiedliche
  Hüte, geben sie als Antwort die Farbe von A, anderenfalls schweigen
  sie.

Auch diese Strategie führt in 6 von 8 Fällen zum Gewinn. Weitere optima-
le Strategien gibt es nicht, sonst hätte sie das Programm ausgespuckt.

Leider ist der Algorithmus extrem ineffizient, so dass ich ihn schon für
4 Spieler nicht zu Ende laufen ließ, nicht auszudenken, wie lange man
für 7 Spieler warten müsste :-/

Eine primitive Strategie für n>3 Spieler wäre es, dass sich 3 ausgewähl-
te Spieler so vehalten, wie sie es auch im 3er-Spiel tun würden. Die
restlichen n-3 Spieler schweigen ganz einfach. Das ergibt ebenfalls eine
Gewinnquote von 75%. Ich bin aber fast überzeugt davon, dass es für 7
Spieler noch eine bessere Strategie gibt.

Vielleicht fällt mir über's Wochenende bei Sonne, Bier und Fußball ja
noch etwas ein :)

Autor: Vlad Tepesch (vlad_tepesch)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
wer spaß an sowas hat, der sollte sich mal project euler anschauen

http://projecteuler.net/

Yalu X. schrieb:
> Leider ist der Algorithmus extrem ineffizient, so dass ich ihn schon für
> 4 Spieler nicht zu Ende laufen ließ, nicht auszudenken, wie lange man
> für 7 Spieler warten müsste :-/

poste ihn doch mal, vielleicht kriegt man ihn schneller

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
für 7 Personen geht es tatsächlich besser als 75%, soviel sei schonmal 
verraten.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Vlad Tepesch schrieb:
> poste ihn doch mal, vielleicht kriegt man ihn schneller

Hmm, das Programm ist auf die Schnelle hingeklatscht, um hinterher
wieder gelöscht zu werden. Gelöscht habe ich es zwar noch nicht, aber
hingeklatscht sieht es immer noch aus, und ich habe gerade auch keine
Zeit, das großartig zu ändern ;-)

Aber egal, du hast darum gebeten, hier ist es:
#!/usr/bin/python3

from itertools import product
from pprint import pprint

nplayers = 3  # Anzahl der Spieler

answers = [0, 1, None]
player_strats = product(answers, repeat=2**(nplayers-1))
team_strats = product(player_strats, repeat=nplayers)
maxwins = 0
best_strats = []

for team_strat in team_strats:
  nwins = 0
  for hats in range(1 << nplayers):
    win = False
    for player, player_strat in zip(range(nplayers), team_strat):
      mask = (1 << player) - 1
      hats_seen = (hats >> 1) & ~mask | hats & mask
      answer = player_strat[hats_seen]
      if answer != None:
        if answer == (hats >> player) & 1:
          win = True
        else:
          win = False
          break
    if win:
      nwins += 1
  if nwins >= maxwins:
    if nwins > maxwins:
      best_strats = []
    maxwins = nwins
    best_strats.append(team_strat)
pprint(best_strats)
print('maxwins =', maxwins)

Es braucht für n=3 Spieler auf einem Dualcore-Laptop etwa 27s.

Hochgerechnet für n=4 beträgt die Laufzeit knapp 6000 Jahre.

Für n=7 sind es 1.45E+203 Jahre, wenn ich mich nicht verrechnet habe.
Da wird mir dann die Stromrechnung etwas zu teuer ;-)

Um die Rechenzeit auf unter 1 Tag zu reduzieren, müssten schon sehr
große Einschnitte in den Suchbaum gemacht werden. Genau genommen müsste
er fast komplett abgeholzt werden ;-)

Mit der Intelligenz, die zur Aufstellung der entsprechenden Abkürzungs-
regeln erforderlich ist, löst man die Aufgabe wahrscheinlich schneller
von Hand.

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich glaube, ich habe die Lösung(en) für 7 Personen und auch einen Weg
zur Ermittlung der Strategie für andere Personenzahlen gefunden. Leider
habe ich erst heute Abend Zeit, die Lösung zu formulieren. So viel
vorab: Die Strategie gewinnt in 87,5% aller Fälle.

@D. I.:

Bitte verrate die Lösung heute noch nicht :)

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Ich glaube, ich habe die Lösung(en) für 7 Personen und auch einen Weg
> zur Ermittlung der Strategie für andere Personenzahlen gefunden. Leider
> habe ich erst heute Abend Zeit, die Lösung zu formulieren. So viel
> vorab: Die Strategie gewinnt in 87,5% aller Fälle.
>
> @D. I.:
>
> Bitte verrate die Lösung heute noch nicht :)

Keine Sorge, aber 87,5% ist schonmal richtig

Autor: Yalu X. (yalu) (Moderator)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
So, jetzt ist es endlich so weit :)

D. I. schrieb:
> Inspiriert von Beitrag "[Help] Mathematisches Problem" und
> meiner damaligen Theoretischen Informatik Vorlesung schmeiß ich doch mal
> folgendes kleines Spielchen in die Runde:

Ich habe mich schon die ganze Zeit vergeblich gefragt, mit welchem
Teilgebiet der Informatik dieses Rätsel zu tun haben könnte, dass es
sogar in einer Vorlesung behandelt wird. Jetzt erst, nachdem ich die
Lösung über längere Um- und Irrwege gefunden habe, fällt es mir wie
Schuppen aus den Haaren¹:

Es geht um Kodierungstheorie, genauer gesagt um den Hamming-Code.


Herleitung der Lösung
=====================

Für diejenigen, die nicht wissen, was der Hamming-Code ist, weil sie
keine entsprechende Vorlesung besucht oder (wie ich) darin nicht auf-
gepasst haben, kommt hier die ausführliche Herleitung der Lösung, die
jeder auch ohne viel Informatikvorwissen nachvollziehen können sollte:

Bei sieben Spielern gibt es 2⁷=128 Variationen, deren Köpfe mit schwar-
zen und weißen Hüten zu bedecken. Nachdem sich die Spieler auf eine
Strategie geeinigt haben, gibt es zu jeder dieser Variationen einen
festgelegten Satz von Reaktionen der Spieler, der entweder zum Gewinn
oder zum Verlust des Spiels führt. Beispiel:
————————————————————————————————————————————————————
 Nr.  Hut von Spieler  Reaktion von Spieler   Gewinn
       6 5 4 3 2 1 0      6 5 4 3 2 1 0
————————————————————————————————————————————————————
  0    S S S S S S S      s - - - s w -        nein
  1    S S S S S S W      - - - - - - -        nein
  2    S S S S S W S      - s - s - w s         ja
  3    S S S S S W W      - - - - - - s        nein
             :                  :
             :                  :
127    W W W W W W W      - w - - w - -         ja
————————————————————————————————————————————————————

S: schwarzer Hut    s: Antwort "schwarz"
W: weißer Hut       w: Antwort "weiß"
                    -: keine Antwort

Ziel ist es, die Strategie so festzulegen, dass möglichst viele der 128
Variationen zum Gewinn führen.

Da ein Spieler seinen eigenen Hut nicht sehen kann, beruht seine Reak-
tion ausschließlich auf den Farben der sechs anderen Hüte. Deswegen
reagiert er auf jeweils zwei der 128 Variationen (die sich nur in seinem
eigenen Hut unterscheiden) gleich.

Im Beispiel reagiert Spieler 0 in den Variationen 0 und 1 gleich, weil
er in beiden Fällen sechs schwarze Hüte sieht, und verzichtet jeweils
auf eine Antwort. In den Variationen 2 und 3 sieht er jeweils fünf
schwarze Hüte und den weißen von Spieler 1. Seine Antwort ist in beiden
Fällen "schwarz", was einmal richtig und einmal falsch ist.

Da jede Antwort eines Spielers für eine der beiden zugehörigen Varia-
tionen richtig und für die andere falsch ist, ist von sämtlichen gemäß
seiner Strategie abgegebenen Antworten immer die Hälfte richtig und die
andere Hälfte falsch.

Das sieht auf den ersten Blick so aus, als sei die Gewinnchance unabhän-
gig von der Strategie immer 50%. Wie können die Spieler aber trotzdem
ihre Gewinnschancen erhöhen?

Das geschieht dadurch, dass die Antworten der einzelnen Spieler so fest-
gelegt werden, dass folgende Bedingungen erfüllt sind:

1. Um keine Chancen zu verschenken, gibt für jede Variation mindestens
   einer der Spieler eine Antwort. Damit gibt es keine Variation, die
   nur auf Grund mangelnder Redseligkeit der Spieler verloren geht (wie
   bspw. die Variation 1 in obiger Tabelle).

2. Die falschen Antworten aller Spieler konzentrieren sich auf möglichst
   wenige Variationen, fortan "Opfervariationen" genannt. Im Idealfall
   geht eine Variation nur dann verloren, wenn alle sieben Spieler ge-
   antwortet haben und alle sieben falsch liegen.

3. Die richtigen Antworten aller Spieler sind möglichst gut auf die ein-
   zelnen Variationen verteilt. Eine Variation, die von einem Spieler
   richtig beantwortet wird, wird idealerweise von den restlichen sechs
   Spielern nicht beantwortet.

Ist die Gesamtanzahl der durch die Strategie festgelegten Antworten
(also die Anzahl der 's' und 'w' in obiger Tabelle) gleich a, so sind
davon a/2 richtig und a/2 falsch. Nach Bedingung (2) sollten sich die
a/2 falschen Antworten auf (a/2)/7 = a/14 Opfervariationen konzentrie-
ren. Die a/2 richtigen Antworten hingegen sollten nach Bedingung (3)
jeweils eineindeutig einer Variation zugeordnet werden, die keine Opfer-
variation ist, so dass diese a/2 Variationen immer richtig beantwortet
werden. Nach Bedingung (1) dürfen keine unbeantworteten Variationen
übrig bleiben. Die Summe aller gewonnenen und verlorenen Variationen ist
128, also ist

     a/14 + a/2 = 128
  =>          a = 224

Auf jeden Spieler entfallen demnach 224/7 = 32 Antworten, davon sind 16
richtig und 16 falsch. Die insgesamt 2234/2 = 112 falschen Antworten
"füllen" 112/7 = 16 Opfervariationen, die gemäß Bedingung (2) von allen
sieben Spielern falsch beantwortet werden. Die 112 richtigen Antworten
führen jeweils einer, insgesamt also bei 112 Variationen zum Erfolg. Die
Verteilung der Antworten geht also ohne Divisionsreste auf, was übrigens
genau dann der Fall ist, wenn die Anzahl der Spieler die Form 2ⁿ-1 hat
(also 1, 3, 7, 15, ... ist).

Wenn es tatsächlich gelingt, eine Stragegie zu finden, die die genannte
Antwortenverteilung hat, wird das Spiel in 112 von 128 Fällen gewonnen
und in nur 16 Fällen verloren.

Um zu dieser Strategie zu gelangen, muss erst einmal entschieden werden,
welche 16 der 128 Variationen die 112 falschen Antworten aufnehmen sol-
len. Für diese Opfervariationen muss folgende Bedingung erfüllt sein:

4. Jeweils zwei Opfervariationen müssen sich mindestens in drei Hüten
   unterscheiden.

Begründung: Würden sie sich nur in dem Hut eines einzigen Spielers un-
terscheiden, dann wäre eine falsche Antwort dieses Spielers in der einen
Variation automatisch eine richtige Antwort in der anderen Variation.
Damit wird letztere aber nicht von allen Spielern falsch beantwortet,
so dass bedingung (2) nicht erfüllt ist.

Würden sie sich hingegen nur in den Hüten von zwei Spielern unterschei-
den, so ließen es zwei weitere Variationen finden, die sich jeweils um
einen Hut von den beiden Opfervariationen unterscheiden. Beide dieser
Variationen würden von den beiden Spielern richtig beantwortet werden,
was aber gegen Bedingung (3) verstößt.

Es ist etwas mühselig, von Hand 16 Variationen zu finden, die Bedingung
(4) erfüllen, zumal ich nicht nur eine lösung, sondern möglichst alle
finden wollte. Deswegen habe ich ein kleines Python-Programm geschrie-
ben, das mir diese Arbeit abnimmt. Es liefert folgende 12 Ergebnisse:
  6543210   6543210   6543210   6543210   6543210   6543210

  SSSSSSS   SSSSSSW   SSSSSWS   SSSSSWW   SSSSWSS   SSSSWSW
  SSSSWWW   SSSSWWS   SSSSWSW   SSSSWSS   SSSWSSW   SSSWSSS
  SSWWSSW   SSWWSSS   SSWWSSS   SSWWSSS   SSWSSWS   SSWSSWS
  SSWWWWS   SSWWWWW   SSWWWWW   SSWWWWW   SSWWWWW   SSWWWWW
  SWSWSWS   SWSWSWS   SWSWSSW   SWSWSSW   SWSSSWW   SWSSSWW
  SWSWWSW   SWSWWSW   SWSWWWS   SWSWWWS   SWSWWWS   SWSWWWS
  SWWSSWW   SWWSSWW   SWWSSWW   SWWSSWS   SWWSWSW   SWWSWSS
  SWWSWSS   SWWSWSS   SWWSWSS   SWWSWSW   SWWWSSS   SWWWSSW
  WSSWSWW   WSSWSWW   WSSWSWW   WSSWSWS   WSSSWWW   WSSSWWS
  WSSWWSS   WSSWWSS   WSSWWSS   WSSWWSW   WSSWSWS   WSSWSWW
  WSWSSWS   WSWSSWS   WSWSSSW   WSWSSSW   WSWSSSW   WSWSSSW
  WSWSWSW   WSWSWSW   WSWSWWS   WSWSWWS   WSWWWSS   WSWWWSS
  WWSSSSW   WWSSSSS   WWSSSSS   WWSSSSS   WWSSSSS   WWSSSSS
  WWSSWWS   WWSSWWW   WWSSWWW   WWSSWWW   WWSWWSW   WWSWWSW
  WWWWSSS   WWWWSSW   WWWWSWS   WWWWSWW   WWWSWWS   WWWSWWW
  WWWWWWW   WWWWWWS   WWWWWSW   WWWWWSS   WWWWSWW   WWWWSWS


  6543210   6543210   6543210   6543210   6543210   6543210

  SSSSWWS   SSSSWWW   SSSWSSS   SSWSSWS   SSSWSWS   SSSWSWW
  SSSWSSS   SSSWSSS   SSSWWWS   SSWWWSW   SSSWWSW   SSSWWSS
  SSWSSSW   SSWSSSW   SSWSSSS   SWSSSSW   SSWSSSS   SSWSSSS
  SSWWWWW   SSWWWWS   SSWSWWS   SWSWWWS   SSWSWWW   SSWSWWW
  SWSSSWW   SWSSSWS   SWSSSWS   WSSSWSS   SWSSSSW   SWSSSSW
  SWSWWSW   SWSWWSW   SWSSWSS   WSSWSWW   SWSSWWS   SWSSWWS
  SWWSWSS   SWWSWSS   SWWWSWS   WWWSWWW   SWWWSWW   SWWWSWS
  SWWWSWS   SWWWSWW   SWWWWSS   WWWWSSS   SWWWWSS   SWWWWSW
  WSSSWSW   WSSSWSS   WSSSSWW   SSSSWWW   WSSSSWW   WSSSSWS
  WSSWSWW   WSSWSWW   WSSSWSW   SSSWSSS   WSSSWSS   WSSSWSW
  WSWSSWS   WSWSSWS   WSWWSWW   SWWSWSS   WSWWSSW   WSWWSSW
  WSWWWSS   WSWWWSW   WSWWWSW   SWWWSWW   WSWWWWS   WSWWWWS
  WWSSSSS   WWSSSSW   WWSWSSW   WSWSSSW   WWSWSSS   WWSWSSS
  WWSWWWS   WWSWWWS   WWSWWWW   WSWWWWS   WWSWWWW   WWSWWWW
  WWWSWWW   WWWSWWW   WWWSSSW   WWSSSWS   WWWSSWS   WWWSSWW
  WWWWSSW   WWWWSSS   WWWSWWW   WWSWWSW   WWWSWSW   WWWSWSS

Die Ziffern über den Blöcken sind dabei die Spielernummern.

Die Spielstrategie lautet nun folgendermaßen:

Man wähle einer der obigen 12 Opfervariationssätze aus, z.B. den ersten.
Jeder Spieler prüft, ob die sechs für ihn sichbaren Hüte mit einer der
16 Opfervariationen zusammenpassen. Wenn nein, antwortet er nicht. Wenn
ja, gibt er als Antwort die gegenteilige Farbe des Huts in dieser Opfer-
variation an seiner eigenen Position.

Beispiel 1:

Die Hüte der sieben Spieler entsprechen einer der 112 Variationen, die
nicht Opfervariation sind:

  6543210
  WWWSSWS

Spieler 2 sieht die Hüte WWWSxWS (x ist dabei sein eigener, unbekannter
Hut). Keiner der 16 Opfervariationen entspricht diesem Muster, also gibt
er keine Antwort. Den Spielern 0, 1, 3, 4 und 6 geht es ähnlich, auch
sie antworten nicht.

Spieler 5 hingegen sieht die Hüte WxWSSWS. Dieses Muster passt zur 11.
Opfervariation (WSWSSWS) von oben. Darin steht anstelle des 'x' ein 'S'.
Spieler 5 antwortet mit dem Gegenteil, also mit 'W', was richtig ist.

Ein Spieler hat richtig geraten, die anderen haben nicht geantwortet,
also ist das Spiel gewonnen.


Beispiel 2:

Die Hüte der sieben Spieler entsprechen einer der 16 Opfervariationen:

  6543210
  SSWWWWS

Spieler 0 sieht die Hüte SSWWWWx. Das passt zur 4. Opfervariation
(SSWWWWS) Darin steht anstelle des 'x' ein 'S'. Spieler 0 antwortet
gemeäß seiner Strategie mit dem Gegenteil, also mit 'W', was falsch ist.
Die Spieler 1 bis 6 antworten ebenfalls alle falsch.

Da keiner der Spieler richtig geantwortet hat, geht das Spiel verloren.

Da dieser zweite Fall aber nur bei 16 der 128 Variationen eintritt,
werden ingesamt 112 von 128 Spielen gewonnen, das sind immerhin 87,5%.
Mit keiner anderen Strategie kann ein höherer Gewinnanteil erreicht
werden, weil nach obiger Überlegung die Anzahl der Opfervariationen
nicht weiter reduziert werden kann.


Bezug zur Kodierungstheorie
===========================

Ich schrieb anfangs etwas vom Hamming-Code.

  http://de.wikipedia.org/wiki/Hamming-Code

Beim ersten der obigen 12 Opfervariationssätze handelt es sich genau um
einen solchen, wenn man die 'S' jeweils durch eine 0 und die 'W' durch
eine 1 ersetzt:

  0000000     0
  0000111     1
  0011001     2
  0011110     3
  0101010     4
  0101101     5
  0110011     6
  0110100     7
  1001011     8
  1001100     9
  1010010    10
  1010101    11
  1100001    12
  1100110    13
  1111000    14
  1111111    15

  DDDPDPP


Der Hamming-Code ist ein selbstkorrigierender Code, bei dem u.a. ein
einzelnes umgekipptes Bit erkannt und rekonstruiert werden kann. In
vorliegenden Fall handelt es sich um einen (7,4)-Hamming-Code, bei dem
in einem 7 Bit langen Codeword 4 Nutzdatenbits (D) kodiert sind. Die
restlichen 3 Bits sind Paritätsbits (P). Es gibt also 2⁴ = 16 verschie-
dene Codeworte, was gerade der Anzahl der Opfervariationen entspricht.
Die Paritätsbits sind die Hüte der Spieler 0, 1 und 3. Streicht man
diese aus der Liste heraus bleiben die binärkodierten Zahlen von 0
(0000) bis 15 (1111) stehen.

Man kann also die Strategie der Spieler folgendermaßen umformulieren:

Von einem 7 Bit (Hüte) langen Codewort ist ein Bit (der eigene Hut)
verdeckt. Der Spieler versucht nun, dieses eine Bit zu rekonstruieren.
Ist dies möglich, gibt er als Antwort das invertierte Bit (die gegen-
teilige Hutfarbe) als Antwort. Gelingt die Rekonstruktion nicht, weil
sich das Wort um mehr als 1 Bit von einem gültigen Hamming-Codewort
unterscheidet, antwortet der Spieler nicht.


Verallgemeinerung
=================

Das beschriebene Verfahren kann für alle Spielerzahlen der Form 2ⁿ-1
verallgemeinert werden. Bei 2ⁿ-1 Spielern kommt der (2ⁿ-1,2ⁿ-n-1)-
Hamming-Code zum Einsatz. Der Anteil der gewonnenen Spiele ist
(2ⁿ-1)/2ⁿ. Dieser Anteil bleibt der gleiche, wenn man die Spielerzahl
"krumm" ist, also zwischen 2ⁿ-1 und 2ⁿ⁺¹-1 liegt. Bei 6 Spielern ist er
also der gleiche wie bei 3 Spielern (n=2), nämlich 3/4 oder 75%.


Und ein Dankeschön
==================

Zum Schluss noch meinen Dank an D. I. für das Posten dieses reizvollen
Rätsels, das wirklich zur edlen Kategorie gehört.


——————————————
¹) Den Spruch habe ich von Karl Heinz Buchegger übernommen ;-)

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Yalu X. schrieb:
> Zum Schluss noch meinen Dank an D. I. für das Posten dieses reizvollen
> Rätsels, das wirklich zur edlen Kategorie gehört.

Und von mir ein Dank über diese durchaus umfangreiche aber doch 
verständliche Lösung. Das hast du richtig erkannt, es ging um 
Kodierungstheorie und in dem Fall um Hamming-Codes. Mein Prof. konnte 
das damals vor 2,5 Jahren nicht so anschaulich erklären.

Ich denke die Lösung muss man erstmal sacken lassen :)

Evtl. finde ich noch meinen Ordner mit weiteren "appetizern" (so nannte 
unser Prof. die Probleme die er uns zu Beginn gegeben hat um Lust auf 
die Vorlesung zu wecken). Man kann sich die allgemeine Reaktion der 3. 
Semester darauf vorstellen :D

Autor: D. I. (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Ich habe tatsächlich noch eins, aber das werde ich nicht vor morgen oder 
übermorgen posten :)

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.