DENK m a l
+ + + 2001: des Rätsels Lösung + + +
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Lösung der 4. Aufgabe   vom 26.2.2001

Vorbemerkung:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Eine Münze wird geworfen.und es wird keine Anzahl von Würfen vorgegeben

Es wird nicht mehr geworfen wenn eine der beiden folgenden Situationen eintritt:
KOPF - KOPF - KOPF  oder   ZAHL - KOPF - ZAHL  fällt nacheinander 

 

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

um sich das Problem zu verdeutlichen kann man mit einen Ereignisbaum beginnen:

K : KOPF geworfen   Z : ZAHL geworfen
K : Ende der    K - K - K  -   Kette ==> Adan gewinnt (es wird nicht weitergewürfelt)
Z : Ende der    Z - K - Z    -   Kette  ==> Eva gewinnt (es wird nicht weitergewürfelt)
1.
Wurf		 2.
Wurf		 3.
Wurf		 4.
Wurf		 5.
Wurf		 6.
Wurf		 . . .
  
K K K
Z K K K
Z . . .
Z
Z K K . . .
Z
Z K . . .
Z . . .
Z K K K
Z K . . .
Z . . .
Z
Z K K K
Z . . .
Z
Z K K . . .
Z
Z K . . .
Z . . .
Z K K K
Z K K . . .
Z
Z K . . .
Z . . .
Z
Z K K K
Z K . . .
Z . . .
Z
Z K K K
Z . . .
Z
Z K K . . .
Z
Z K . . .
Z . . .

Lex Bedijs  baut seine Lösung auf so einen Ereignisbaum auf:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Nach dem 3. Wurf kann erstmalig geprüft werden, ob Adam oder Eva gewonnen haben. 
Es gibt 8 verschiedene Möglichkeiten, von denen je eine für Adam bzw. Eva günstig sind. 
Nach dem 3. Wurf besteht für beide also Wahrscheinlichkeit von 1/8. Die anderen 6 Würfe 
sind für beide nicht günstig. Streicht man nun den ersten Wurf und ersetzt ihn durch 
einen vierten, sieht das Bild etwas anders aus. Es gibt 12 Möglichkeiten, von den einer 
für Adam günstig ist, aber zwei für Eva. Adam erhöht seine Gesamtwahrscheinlichkeit also 
um 1/16 auf 3/16, Eva um 2/16 auf 4/16. 
Dieses Verfahren kann man nun Wurf für Wurf durchführen. Ohne Computer ist dies ein lästiges 
und fehlerträchtiges Verfahren. Deshalb habe ich also den Rechenknecht eingesetzt. Es ist 
eine deutliche Konvergenz zu erkennen, die gegen 5/12 (Adam) und 7/12 zu laufen scheint. 

Hier eine Tabelle für die Anzahl der günstigen Würfe 

Wurf   Adam    Eva 
  3      1      1 
  4      1      2 
  5      2      3 
  6      3      4 
  7      4      6 
  8      6      9 
  9      9     13 
 10     13     19 
 11     19     28 
 12     28     41 
 13     41     60 
 14     60     88 
 15     88    129 
 16    129    189 
 17    189    277 
 18    277    406 
 19    406    595 
 20    595    872 
 21    872   1278 
 22   1278   1873 
 23   1873   2745 
 24   2745   4023 
 25   4023   5896 
 26   5896   8641 
 27   8641  12664 
 28  12664  18560 
 29  18560  27201 
 30  27201  39865 
.... 
Nach jedem Wurf wird die Wertigkeit für die neuen günstigen Fälle halbiert. 
Für Adam und Eva ergeben sich ihre Gewinnwahrscheinlichkeit also zu 
W_eva = 1/8 + 2/16 + 3/32 + 4/64 + 6/128 + 9/256 ... 
W_adam = 1/8 + 1/16 + 2/32 + 3/64 + 4/128 + 6/256 ... 
Aus der obigen Liste sieht man sofort, dass ab dem 4. Wurf die Anzahl der neuen günstigen Fälle Adams immer denjenigen Evas aus dem vorigen Wurf entsprechen. 
Daraus kann man die Gewinnwahrscheinlichkeiten bestimmen. 

Es gilt dann nämlich 

W_adam = 1/8 + W_eva/2 
W_adam + W_eva = 1 

Daraus folgt direkt 

W_adam = 5/12 
W_eva = 7/12 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Als Zusatzaufgabe habe ich (Lex Bedijs) mich gefragt, wie hoch die jeweiligen Gewinnwahrscheinlichkeiten sind, wenn Adam und Eva andere Kopf/Zahl-Kombinationen als jeweils günstigen Fall haben. 


  Adam:Eva | Eva                                    | 

           | KKK  KKZ  KZK  KZZ  ZKK  ZKZ  ZZK  ZZZ | 

  ---------+----------------------------------------+ 

  Adam KKK | ---  1:1  2:3  2:3  1:7  5:7  3:7  1:1 | 

       KKZ | 1:1  ---  2:1  2:1  1:3  5:3  1:1  7:3 | 

       KZK | 3:2  1:2  ---  1:1  1:1  1:1  3:5  7:5 | 

       KZZ | 3:2  1:2  1:1  ---  1:1  1:1  3:1  7:1 | 

       ZKK | 7:1  3:1  1:1  1:1  ---  1:1  1:2  3:2 | 

       ZKZ | 7:5  3:5  1:1  1:1  1:1  ---  1:2  3:2 | 

       ZZK | 7:3  1:1  5:3  1:3  2:1  2:1  ---  1:1 | 

       ZZZ | 1:1  3:7  5:7  1:7  2:3  2:3  1:1  --- | 
Für Eva wäre es deutlich günstiger gewesen, nicht die Folge Zahl, Kopf, Zahl sondern Zahl, 
Kopf, Kopf zu haben. Ihre Gewinnchance wäre dann 5x höher. 



~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Christopher Bluethgen analysiert alle möglichen Verbindungen zwischen den Ereignissen
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

Es gibt für die ersten 3 Würfe insgesamt 8 mögliche (gleich wahrscheinliche) Ergebnisse:

A: KKK
B: KKZ
C: KZK
D: KZZ
E: ZKK
F: ZKZ
G: ZZK
H: ZZZ

Sei P die Wahrscheinlichkeit, dass Adam gewinnt. Dann gilt

P(A) = 1
P(B) = ½P(C) + ½P(D)
P(C) = ½P(E) + ½P(F)
P(D) = ½P(G) + ½P(H)
P(E) = ½P(A) + ½P(B)
P(F) = 0
P(G) = ½P(E) + ½P(F)
P(H) = ½P(G) + ½P(H) <-> P(H) = P(G)

und 

P = [P(A) + P(B) + P(C) + P(D) + P(E) + P(F) + P(G) + P(H)] /8

Aus den obigen Gleichungen ergibt sich folgende Matrix:

    1    0    0    0    0    0    0    0    1
  0    1  -1/2 -1/2   0    0    0    0    0
  0    0    1    0  -1/2 -1/2   0    0    0
  0    0    0    1    0    0  -1/2 -1/2   0
-1/2 -1/2   0    0    1    0    0    0    0
  0    0    0    0    0    1    0    0    0
  0    0    0    0  -1/2 -1/2   1    0    0
  0    0    0    0    0    0   -1    1    0

Diese bringen wir mit Gauß-Alg. auf "Obere Dreiecksform".

1    0    0    0    0    0    0    0    1 
0    1  -1/2 -1/2   0    0    0    0    0 
0    0    1    0  -1/2 -1/2   0    0    0 
0    0    0    1    0    0 -1/2 -1/2    0 
0    0    0    0    1  -1/7 -1/7 -1/7  4/7 
0    0    0    0    0    1    0    0    0 
0    0    0    0    0    0    1  -1/13 4/13 
0    0    0    0    0    0    0    1   1/3 

 Es ergibt sich sukzessive:

P(H) = 1/3
P(G) = 1/3
P(F) = 0
P(E) = 2/3
P(D) = 1/3
P(C) = 1/3
P(B) = 1/3
P(A) = 1

P = 5/12

Adam gewinnt mit der Wahrscheinlichkeit von 5/12.

Eva gewinnt folglich mit der Wahrscheinlichkeit von 7/12.
(Lässt sich überprüfen, indem man P(A) = 0 und P(F) = 1 setzt und die neue Matrix auflöst) 

Die Gewinnchancen liegen also 7 zu 5 pro Eva.

 


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

Roland Koppenberger gab eine sehr anschauliche Methode diese Aufgabe zu lösen vor:
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 
Die Frage nach dem Sieg von Adam ist äquivalent mit der Frage nach der Wahrscheinlichkeit, dass ein Teilchen, das (in der Graphik) bei "Adam" startet, am Platz "1" landet, wobei der Platz "0" für ein Loch steht, wo es nicht mehr raus kann und die Wege bei Wegkreuzungen mit Wahrscheinlichkeiten gewichtet sind.

Die Berechnung erfolgt einfach über ein umfangreiches Gleichungssystem etwa folgender Gestalt, wobei p(X) für die Wahrscheinlichkeit steht, vom Ort "X" zum Ort "1" zu gelangen.
Grafik

p(Adam) = ½ p(K) + ½ p(Z)

p(K) = ½ p(Z) + ½ p(KK)

p(Z) = ½ p(Z) + ½ p(ZK)

p(KK) = ½ p(Z) + ½ p(KKK)

p(ZK) = ½ p(KK) + ½ p(ZKZ)

p(KKK) = 1

p(ZKZ) = 0

 

Als Lösung ergibt sich für p(Adam) = 5/12 
(und für p(Eva) = 7/12.)

Also gewinnt Adam in 5 und Eva in 7 von 12 Spielen.

 

 


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Anmerkung 1

Der Brite und Algorithmen-Meister John Horton Conway (Universität Cambridge) hat ein effizientes Verfahren entwickelt, wie sich derartige Gewinnchancen recht einfach berechnen lassen. Der Schlüssel dazu liegt in der Berechnung jener vier Dualzahlen, die Conway als "leading numbers" getauft hat.
Es sei A = KKK und E = ZKZ (wie oben). Wir wollen die Wahrscheinlichkeiten berechnen, dass A das Tupel E schlägt. Dazu bildet man vier Blöcke, indem man A über A, E über E, A über E und schließlich E über A schreibt (siehe Abbildung). Oberhalb des ersten Tupels jedes Blocks wird nun eine Dualzahl konstruiert.
Betrachten wir bspw. den Block EE. Nun sieht man sich den ersten Buchstaben des oberen Tupels an und fragt sich, ob die insgesamt drei Buchstaben - beginnend mit dem ersten - exakt den drei Buchstaben des unteren Tupels in eben dieser Reihenfolge entsprechen oder nicht. Offensichtlich ist das der Fall. Deshalb schreiben wir eine 1 über den ersten Buchstaben. Dann nehmen wir den zweiten Buchstaben des oberen Tupels und fragen uns, ob die zwei Buchstaben (beginnend mit dem zweiten) des oberen Tupels mit den ersten zwei Buchstaben am Anfang des zweiten Tupels übereinstimmen. Das ist offensichtlich nicht der Fall, also schreiben wir eine 0 über den zweiten Buchstaben. Stimmt der letzte Buchstabe des oberen mit dem ersten Buchstaben des unteren Tupels überein? Ja, also eine 1 anschreiben.

111 = 7 000 = 0 101 = 5 000 = 0
A = KKK A = KKK E = ZKZ E = ZKZ
A = KKK E = ZKZ E = ZKZ A = KKK

Nun werden die vier Dualzahlen ins Dezimalsystem übersetzt und folgende Berechnung angestellt:

p(E) : p(A) = (AA - AE) : (EE - EA) = (7 - 0) : (5 - 0) = 7 : 5

also p(E) = 7/12 und p(A) = 5/12

Dabei ist es unerheblich, ob die beiden Tupel dieselbe Länge besitzen.



Anmerkung 2

Der spannende Hintergrund dazu bieten nichttransitive Relationen. Wenn bei dem Spiel Adam eine beliebige Kombination aus drei möglichen Zuständen beim Münzwurf (etwa "KKZ") wählt, so gelingt es Eva anschließend immer, eine gewinnträchtigere Variante zu wählen.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~


Auswertung:

eingegangene Lösungen richtige Lösungen falsche Lösungen
46 31 15
BemerkungenDie Wahrscheinlichkeitsrechnung hat viele Irrwege und manchmal begann das Problem beim Interpretieren des Textes.

 

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 [ aktuelle Aufgabe ]  [ zur 4. zurück ]  [ zur Hall of FAME ]   

 

?     ?    ???    ?    ?

 

 

_>^..^<____________________________________________________________
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Das ist der ganze Jammer:
die Dummen sind so sicher und die Gescheiten so im Zweifel.
      Helmut Schmidt 
  
<^>
~~~~~~~~~~~~~~
 "blättern"
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

© Karin S., Jan.2000