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
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 User
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.
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
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
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.
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?
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
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)
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 :)
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 :)
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
für 7 Personen geht es tatsächlich besser als 75%, soviel sei schonmal verraten.
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:
1 | #!/usr/bin/python3
|
2 | |
3 | from itertools import product |
4 | from pprint import pprint |
5 | |
6 | nplayers = 3 # Anzahl der Spieler |
7 | |
8 | answers = [0, 1, None] |
9 | player_strats = product(answers, repeat=2**(nplayers-1)) |
10 | team_strats = product(player_strats, repeat=nplayers) |
11 | maxwins = 0 |
12 | best_strats = [] |
13 | |
14 | for team_strat in team_strats: |
15 | nwins = 0 |
16 | for hats in range(1 << nplayers): |
17 | win = False |
18 | for player, player_strat in zip(range(nplayers), team_strat): |
19 | mask = (1 << player) - 1 |
20 | hats_seen = (hats >> 1) & ~mask | hats & mask |
21 | answer = player_strat[hats_seen] |
22 | if answer != None: |
23 | if answer == (hats >> player) & 1: |
24 | win = True |
25 | else: |
26 | win = False |
27 | break
|
28 | if win: |
29 | nwins += 1 |
30 | if nwins >= maxwins: |
31 | if nwins > maxwins: |
32 | best_strats = [] |
33 | maxwins = nwins |
34 | best_strats.append(team_strat) |
35 | pprint(best_strats) |
36 | 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.
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 :)
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
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:
1 | ———————————————————————————————————————————————————— |
2 | Nr. Hut von Spieler Reaktion von Spieler Gewinn |
3 | 6 5 4 3 2 1 0 6 5 4 3 2 1 0 |
4 | ———————————————————————————————————————————————————— |
5 | 0 S S S S S S S s - - - s w - nein |
6 | 1 S S S S S S W - - - - - - - nein |
7 | 2 S S S S S W S - s - s - w s ja |
8 | 3 S S S S S W W - - - - - - s nein |
9 | : : |
10 | : : |
11 | 127 W W W W W W W - w - - w - - ja |
12 | ———————————————————————————————————————————————————— |
13 | |
14 | S: schwarzer Hut s: Antwort "schwarz" |
15 | W: weißer Hut w: Antwort "weiß" |
16 | -: 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:
1 | 6543210 6543210 6543210 6543210 6543210 6543210 |
2 | |
3 | SSSSSSS SSSSSSW SSSSSWS SSSSSWW SSSSWSS SSSSWSW |
4 | SSSSWWW SSSSWWS SSSSWSW SSSSWSS SSSWSSW SSSWSSS |
5 | SSWWSSW SSWWSSS SSWWSSS SSWWSSS SSWSSWS SSWSSWS |
6 | SSWWWWS SSWWWWW SSWWWWW SSWWWWW SSWWWWW SSWWWWW |
7 | SWSWSWS SWSWSWS SWSWSSW SWSWSSW SWSSSWW SWSSSWW |
8 | SWSWWSW SWSWWSW SWSWWWS SWSWWWS SWSWWWS SWSWWWS |
9 | SWWSSWW SWWSSWW SWWSSWW SWWSSWS SWWSWSW SWWSWSS |
10 | SWWSWSS SWWSWSS SWWSWSS SWWSWSW SWWWSSS SWWWSSW |
11 | WSSWSWW WSSWSWW WSSWSWW WSSWSWS WSSSWWW WSSSWWS |
12 | WSSWWSS WSSWWSS WSSWWSS WSSWWSW WSSWSWS WSSWSWW |
13 | WSWSSWS WSWSSWS WSWSSSW WSWSSSW WSWSSSW WSWSSSW |
14 | WSWSWSW WSWSWSW WSWSWWS WSWSWWS WSWWWSS WSWWWSS |
15 | WWSSSSW WWSSSSS WWSSSSS WWSSSSS WWSSSSS WWSSSSS |
16 | WWSSWWS WWSSWWW WWSSWWW WWSSWWW WWSWWSW WWSWWSW |
17 | WWWWSSS WWWWSSW WWWWSWS WWWWSWW WWWSWWS WWWSWWW |
18 | WWWWWWW WWWWWWS WWWWWSW WWWWWSS WWWWSWW WWWWSWS |
19 | |
20 | |
21 | 6543210 6543210 6543210 6543210 6543210 6543210 |
22 | |
23 | SSSSWWS SSSSWWW SSSWSSS SSWSSWS SSSWSWS SSSWSWW |
24 | SSSWSSS SSSWSSS SSSWWWS SSWWWSW SSSWWSW SSSWWSS |
25 | SSWSSSW SSWSSSW SSWSSSS SWSSSSW SSWSSSS SSWSSSS |
26 | SSWWWWW SSWWWWS SSWSWWS SWSWWWS SSWSWWW SSWSWWW |
27 | SWSSSWW SWSSSWS SWSSSWS WSSSWSS SWSSSSW SWSSSSW |
28 | SWSWWSW SWSWWSW SWSSWSS WSSWSWW SWSSWWS SWSSWWS |
29 | SWWSWSS SWWSWSS SWWWSWS WWWSWWW SWWWSWW SWWWSWS |
30 | SWWWSWS SWWWSWW SWWWWSS WWWWSSS SWWWWSS SWWWWSW |
31 | WSSSWSW WSSSWSS WSSSSWW SSSSWWW WSSSSWW WSSSSWS |
32 | WSSWSWW WSSWSWW WSSSWSW SSSWSSS WSSSWSS WSSSWSW |
33 | WSWSSWS WSWSSWS WSWWSWW SWWSWSS WSWWSSW WSWWSSW |
34 | WSWWWSS WSWWWSW WSWWWSW SWWWSWW WSWWWWS WSWWWWS |
35 | WWSSSSS WWSSSSW WWSWSSW WSWSSSW WWSWSSS WWSWSSS |
36 | WWSWWWS WWSWWWS WWSWWWW WSWWWWS WWSWWWW WWSWWWW |
37 | WWWSWWW WWWSWWW WWWSSSW WWSSSWS WWWSSWS WWWSSWW |
38 | 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:
1 | 0000000 0 |
2 | 0000111 1 |
3 | 0011001 2 |
4 | 0011110 3 |
5 | 0101010 4 |
6 | 0101101 5 |
7 | 0110011 6 |
8 | 0110100 7 |
9 | 1001011 8 |
10 | 1001100 9 |
11 | 1010010 10 |
12 | 1010101 11 |
13 | 1100001 12 |
14 | 1100110 13 |
15 | 1111000 14 |
16 | 1111111 15 |
17 | |
18 | 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 ;-)
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
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? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.