Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Dienstag, 5. Januar 2016

UNO, Mathe und HTML


Deutsch

Wenn sich mir ein rech­ne­ri­sches Pro­blem einmal in den Kopf gesetzt hat, dann bleibt es meis­tens dort, bis ich es gelöst habe. Beim Kar­ten­spie­len war es dann wieder soweit. In diesem Bei­trag verwen­de ich zum ers­ten Mal MathML zum Einbin­den der ma­the­mati­schen Formeln.

Die Fra­ge­stellung zum Spiel UNO lau­tet: Wie hoch ist die Wahr­scheinlichkeit, dass man beim Zie­henmüs­sen von n Kar­ten ei­nen +2er oder +4er nach­zieht?

UNO ent­hält 112 Spielkar­ten. Davon sind acht +2er und vier +4er. Insge­s­amt also 12 Zieh- und 100 an­de­re Kar­ten. Die herkömmli­che Be­rech­nung für die Wahr­scheinlichkeit, dass man min­des­tens ei­nen +2er oder +4er aus dem vol­len Zugstapel nach­zieht, ist:

O ( n ) = 1 - 100 ! ( 100 - n ) ! · ( 112 - n ) ! 112 !

Allerdings fehlt hier die Einbeziehung der +2er und +4er, die be­reits auf dem Ab­la­ge­stapel liegen müs­sen, um überhaupt ein Zie­henmüs­sen von n Kar­ten zu bewirken. Bei n=2 liegt be­reits ein +2er auf dem Ab­la­ge­stapel, bei n=4 zwei +2er oder ein +4er, bei n=6 drei +2er oder ein +4er und ein +2er usw. Die­se feh­len dann natürlich im Zugstapel und können nicht nach­gezogen wer­den. Außerdem gibt es ver­schiede­ne Kombi­nationen der +2er und +4er, um überhaupt auf n nach­zuzie­hen­de Kar­ten zu kommen. Das Bei­spiel für n=8 soll das ver­deutli­chen:

Aus diesem Baum kann man schon ei­ne Menge Dinge ab­le­sen, die für die weite­re Be­rech­nung wichtig sind: Es gibt ei­ne von n abhängige Anzahl an Pfaden und jeder Pfad hat ei­ne ei­gene Auf­trittswahr­scheinlichkeit. Zudem befindet sich am En­de jeden Pfads ei­ne un­ter­schiedli­che Anzahl von +2ern und +4ern auf dem Ab­la­ge­stapel. Die ge­fragte Wahr­scheinlichkeit setzt sich dann wie folgt zu­sammen:

Q ( n ) = 1 - i = 1 F ( n 2 + 1 ) 100 ! ( 100 - n ) ! · ( 112 - t ( n , i ) - f ( n , i ) - n ) ! ( 112 - t ( n , i ) - f ( n , i ) ) ! · p ( n , i )

Das ist eins minus die Summe der Wahr­scheinlichkei­ten von jedem Pfad, dass man nicht ei­nen +2er oder +4er nach­zieht. Dabei liefert f(n,i) die Anzahl der verwende­ten +4er und t(n,i) die Anzahl der verwende­ten +2er auf dem i-ten Pfad sowie p(n,i) die Auf­trittswahr­scheinlichkeit für den i-ten Pfad.

Insge­s­amt gibt es bei n nach­zuzie­hen­den Kar­ten F(n2+1) Pfade, wobei F(n) die n-te Fibonacci-Zahl liefert:

F ( n ) = { n n 1 F ( n - 2 ) + F ( n - 1 ) n

Die Formel Q(n) gilt nur für 2n16, da ab n>16 min­des­tens ein, und für größe­re Zah­len noch mehr, +4er ein­gesetzt wer­den müs­sen. Zu f(n,i):

f ( n , i ) = { 0 i 1 1 i n 2 2 i n 2 + ( n 2 - 3 ) · ( n 2 - 2 ) 2 3 i 33 4 i

Die­se Fallun­ter­scheidung beruht auf Beobach­tun­gen (insbesonde­re die magi­sche Zahl 33), ist aber für n16 korrekt. t(n,i) kann leicht aus f(n,i) be­rech­net wer­den:

t ( n , i ) = n - 4 · f ( n , i ) 2

Etwas komplexer ist die Formel für die Auf­trittswahr­scheinlichkeit des i-ten Pfads:

p ( n , i ) = ( 12 - t ( n , i ) + r ( i ) - f ( n , i ) ) ! 12 ! · 8 ! ( 8 - t ( n , i ) + r ( i ) ) ! · 4 ! ( 4 - f ( n , i ) ) !

Wie im obigen Baum zu erkennen ist, be­rech­net sich die Wahr­scheinlichkeit als ein Bruch, in de­s­sen Zäh­ler und Nenner ein Pro­dukt steht. Im Nenner stehen die Anzahl der verwende­ten +2er und +4er viele Fak­to­ren; und zwar von 12 abwärts. Im Zäh­ler tau­chen für jeden verwende­ten +2er ei­ne Zahl von 8 abwärts und für jeden verwende­ten +4er ei­ne Zahl von 4 abwärts auf. Ist allerdings die letzte Kar­te des Pfads ein +2er, so ist de­s­sen Wahr­scheinlichkeit 1. In diesem Falle muss die Wahr­scheinlichkeit des Pfads nur bis zur vorletz­ten Kar­te be­rech­net wer­den und ge­nau dafür sorgt die Funkti­on r(i), wel­che im­mer 0 oder 1 zurückgibt. Es handelt sich bei ihr um die i-te Stel­le des unendli­chen Fibonacci-Worts:

r ( i ) = ( i + 1 ) · - 1 + 5 2 - i · - 1 + 5 2

Für die gesuch­te Wahr­scheinlichkeit ergibt sich also:

P ( n ) = { 0 n = 0 12 112 n = 1 Q ( n ) n 16 R ( n ) n 32

Der Fall n=1 be­rech­net die Wahr­scheinlichkeit für das Zie­hen ei­nes +2ers oder +4ers, wenn man einfach ei­ne Kar­te nach­zieht. Bis auf den Fall n=1 muss n ge­rade sein. Die Funkti­on Q(n) wurde be­reits hergeleitet; es fehlt noch R(n).

Man kommt schnell dar­auf, dass R(32)=0 und R(32)=1-100!(100-30)!·(101-30)!101!, da bei n=32 nicht ein +2er oder +4er bzw. bei n=30 nur noch ein +2er im Zugstapel ist. Allgemein ergibt sich für R(n):

R ( n ) = 1 - i = 8 - n 4 16 - n 2 100 ! ( 100 - n ) ! · ( 100 + i - n ) ! ( 100 + i ) ! · q ( n , i )

q(n,i) gibt die Wahr­scheinlichkeit für das Ver­blei­ben von i Ziehkar­ten im Zugstapel an:

q ( n , i ) = j = 1 t ( 32 - n , j ) + f ( 32 - n , j ) = i F ( 32 - n 2 + 1 ) 1 F ( 32 - n 2 + 1 ) ( 1 1 + ( 16 - n 2 ) - ( 8 - n 4 ) )

Hierbei wer­den die Pfade mit i Kar­ten gezählt und durch die Pfadgesamtzahl ge­teilt.

Nun kann man die Wer­te der ver­einfach­ten Formel O(n) und die Wer­te von P(n) ta­bel­larisch gegenüber­stel­len:

nO(n)P(n)Δ
00,000,000,00
10,110,110,00
20,200,190,01
40,370,330,04
60,500,430,07
80,610,500,11
100,690,570,12
120,760,600,16
140,820,630,19
160,860,640,22
180,890,630,26
200,920,610,31
220,940,590,35
240,950,550,40
260,970,490,48
280,970,380,59
300,980,300,68
320,990,000,99

Die Be­rech­nun­gen gehen davon aus, dass sich alle 100 an­de­ren Kar­ten noch im Zugstapel befin­den. Mit jeder die­ser Kar­ten, die auf den Ab­la­ge­stapel gelegt wird, steigt die Wahr­scheinlichkeit P(n); allerdings sinkt sie auch mit jedem +2er und +4er, der auf den Ab­la­ge­stapel gelegt wird.

Das Ganze habe ich auch als PDF-Da­tei hoch­gela­den:
PDF-Da­tei
Das Herun­terla­den sowie Weiterverwen­den des Dokuments und/oder de­s­sen Inhalt ist hiermit ge­stattet.


Keine Kommentare:

Kommentar veröffentlichen