Würfelrätsel

09.09.2015, 13:20

kepfle

Würfelrätsel

Tach zusammen. Ich hab hier ein Problem, das zwar nicht von mir stammt (kommt von gutefrage.net) aber dessen Lösung mich doch auch interessieren würde, sofern das lösbar ist.

Man hat einen Würfel mit Primzahl Seiten (mindestens 7 Seiten).

Das Spiel wird abgebrochen wenn:

-23 mal keine Primzahl geworfen wurde

-Eine Primzahl gewürfelt wird welche kleiner ist als Würfelseite/2, und danach eine Primzahl welche größer ist als Würfelseite/2

-Eine Primzahl gewürfelt wird welche größer ist als Würfelseite/2, und danach eine Primzahl welche kleiner ist als Würfelseite/2

Ziel des Spiels ist es so häufig wie möglich zu Würfeln. Nun ist die Frage welcher Würfel der Beste ist.

Mein Ansatz dazu wäre gewesen, x/ln(x) als Anzahl der Primzahlen < x zu benutzen, und damit dann rumzuspielen. Aber das führt zu unberechenbarem Zeugs.

09.09.2015, 13:48

HAL 9000

Auf diesen Beitrag antworten »

Du kannst ja erstmal allgemein mit der Anzahl $\begin{align*} \pi(x) \end{align*}$ aller Primzahlen $\begin{align*} \leq x \end{align*}$ operieren, das $\begin{align*} \pi(x) \sim \frac{x}{\ln(x)} \end{align*}$ kann irgendwann später zum Zuge kommen.

Mein Frage wäre zunächst, das hier

Zitat:

Original von kepfle
Ziel des Spiels ist es so häufig wie möglich zu Würfeln.

zu präzisieren: Diese Wurfanzahl ist eine Zufallsgröße - soll deren Erwartungswert maximiert werden? Oder ein anderer Lageparameter? verwirrt

Dies muss zwar nicht, aber kann evtl. zu unterschiedlichen Lösungen führen - das muss die Untersuchung ergeben.

09.09.2015, 13:53

kepfle

Auf diesen Beitrag antworten »

Ok, dann setz ich mich da gleich mal ran und versuch das allgemeiner zu machen.

Ich hab die Frage so 1:1 kopiert. Ich nehm an, man soll die Würfelgröße (x) nehmen für die der Erwartungswert maximal wird.

09.09.2015, 14:03

HAL 9000

Auf diesen Beitrag antworten »

Sei $\begin{align*} n=2m+1 \end{align*}$ die Würfelseitenzahl. Grundsätzlich kann man das Spiel als Markovkette mit 26 Zuständen beschreiben:

$\begin{align*} A_0 \end{align*}$ ... Startzustand
$\begin{align*} A_k \end{align*}$ ... der letzte Primzahlwurf liegt $\begin{align*} k+1 \end{align*}$ Würfe zurück, d.h. die letzten $\begin{align*} k \end{align*}$ Würfe waren alles Nichtprimzahlen ( $\begin{align*} k=1\ldots 22 \end{align*}$ )
$\begin{align*} A_{23} \end{align*}$ ... Endzustand
$\begin{align*} A_{24} \end{align*}$ ... der letzte Wurf war eine Primzahl $\begin{align*} <\frac{n}{2} \end{align*}$
$\begin{align*} A_{25} \end{align*}$ ... der letzte Wurf war eine Primzahl $\begin{align*} >\frac{n}{2} \end{align*}$

$\begin{align*} A_0 \end{align*}$ ist der Startzustand, $\begin{align*} A_{23} \end{align*}$ der absorbierende Endzustand.

Dann kann man die Matrix der Übergangswahrscheinlichkeiten aufstellen, und den Erwartungswert des Erreichens von $\begin{align*} A_{23} \end{align*}$ berechnen oder zumindest erstmal für konkrete $\begin{align*} n \end{align*}$ simulieren.

Du solltest mal noch den genauen gutefrage.net-Link hier posten - damit wir überblicken, wie weit man dort gekommen ist.

09.09.2015, 14:23

kepfle

Auf diesen Beitrag antworten »

Kann ich gleich machen, aber gutefrage gibt mir grade Error 500. Allerdings ging da wirklich noch kaum was, ich war da der einzige der ernsthaft irgendwas versucht hat, nur halt ohne Markov-Ketten und damit effektiv substanzlos. Ich schau mir das heute Abend mal nochmal genauer an mit den Ketten und kann dann eher was dazu sagen.

09.09.2015, 14:53

kepfle

Auf diesen Beitrag antworten »

https://www.gutefrage.net/frage/wuerfels...nswer-176428070

Das ist alles was es dazu gibt. Die Frage wurde zwar nochmal eingestellt, aber da steht nur dass das ja schon jemand beantwortet hat.

09.09.2015, 14:53

HAL 9000

Auf diesen Beitrag antworten »

Die Übergangswahrscheinlichkeiten müssten so lauten:

$\begin{align*} p_{i,j} = \begin{cases} 1-\frac{\pi(n)}{n} & \;\mbox{für}\;i\leq 22,j=i+1\,\mbox{sowie}\;24\leq i\leq 25,j=1 \\ \frac{\pi(m)}{n} & \;\mbox{für}\;i\leq 22,j=24\,\mbox{sowie}\;i=24,j=24\,\mbox{und}\;i=25,j=23 \\ \frac{\pi(n)-\pi(m)}{n} & \;\mbox{für}\;i\leq 22,j=25\,\mbox{sowie}\;i=25,j=25\,\mbox{und}\;i=24,j=23 \\ 1 & \;\mbox{für}\,i=23,j=23 \\ 0 & \;\mbox{sonst} \end{cases} \end{align*}$

09.09.2015, 16:26

HAL 9000

Auf diesen Beitrag antworten »

In der gutefrage.net-Antwort

Zitat:

Original von kepfIe
P1: 23 mal keine Primzahl gewürfelt:

((Anzahl der Primzahlen)/(Würfelseiten))^23=((x/ln(x))/x)^23=(1/ln(x))^23

ist ein böser Fehler:

Die Rechnung ist für 23 Primzahlen hintereinander, es geht aber um 23 Nichtprimzahlen hintereinander!!!
Demzufolge lautet die Rechnung richtigerweise

$\begin{align*} P1 = \left(1-\frac{\pi(x)}{x}\right)^{23} \approx \left(1-\frac{1}{\ln(x)}\right)^{23} \to 1 \end{align*}$ für $\begin{align*} x\to\infty \end{align*}$

statt $\begin{align*} P1\to 0 \end{align*}$ , wie weiter unten falsch angemerkt.

Mit der Markovketten-Idee und ein wenig CAS-Rechnung scheint sich Seitenzahl $\begin{align*} n=7481 \end{align*}$ mit zugehöriger durchschnittlicher Spieldauer von 74.92 Würfen als Lösung herauszukristallisieren - ein ganz schön großer Würfel. Big Laugh

09.09.2015, 21:08

kepfle

Auf diesen Beitrag antworten »

Das hab ich weiter unten versucht zu verbessern, aber glaub ich auch falsch traurig

Wenns keine Umstände macht, kannst du mir das ganze Ding erklären? Ich wär jetzt theoretisch soweit die Übergangsmatrix zu haben, die schreib ich natürlich so nich ganz auf, aber von Markov-Ketten hab ich eh keine Ahnung. Kam in der Vorlesung zwar dran, aber in der Klausur dann nich mehr.

09.09.2015, 22:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von kepfle
aber von Markov-Ketten hab ich eh keine Ahnung. Kam in der Vorlesung zwar dran, aber in der Klausur dann nich mehr.

Dann musst du die Begriffe, die ich noch verwenden werde, nachschlagen - ist mir zuviel Aufwand, hier die Vorlesung zu rekapitulieren.

Ich würde die obige Idee noch etwas modifizieren:

Wir vereinigen Startzustand 0 mit 23 zu einem Zustand (und nennen ihn wieder 23), d.h. gedanklich wird mit dem Ende jedes Spiels sofort ein neues begonnen. Dann haben wir eine ergodische Markovkette, und die mittlere Spielzeit (in Würfen) entspricht dann dem Kehrwert der stationären Aufenthaltswahrscheinlichkeit in eben jenem Zustand 23.

Also: Markov-Übergangsmatrix $\begin{align*} P=(p_{i,j})_{i,j=1,\ldots,25} \end{align*}$ aufstellen mit

$\begin{align*} p_{i,j} = \begin{cases} 1-\frac{\pi(n)}{n} & \;\mbox{für}\;i\leq 22,j=i+1\,\mbox{sowie}\;23\leq i\leq 25,j=1 \\ \frac{\pi(m)}{n} & \;\mbox{für}\;i\leq 24,j=24\,\mbox{sowie}\;i=25,j=23 \\ \frac{\pi(n)-\pi(m)}{n} & \;\mbox{für}\;i\leq 23,j=25\,\mbox{sowie}\;i=25,j=25\,\mbox{und}\;i=24,j=23 \\ 0 & \;\mbox{sonst} \end{cases} \end{align*}$ .

Anschließend stationäre Verteilung $\begin{align*} s \end{align*}$ bestimmen, d.h. mit $\begin{align*} |s|=1 \end{align*}$ und $\begin{align*} P^T \cdot s = s \end{align*}$ . Der Wert $\begin{align*} \frac{1}{s_{23}} \end{align*}$ ist dann die erwähnte mittlere Wurfzahl - und die wollen wir bzgl. $\begin{align*} n \end{align*}$ maximieren! Eine Heidenarbeit, aber mit CAS ziemlich gut zu bewältigen. Augenzwinkern