Raadsel: dobbelsteen spel

Moderator: Rhiannon

Reageer
Gebruikersavatar
Berichten: 2.598

Raadsel: dobbelsteen spel

Een spel wordt gespeeld met een dobbelsteen met N zijden. Er zijn 2 spelers. De eerste speler die bij de volgende worp niet hoger gooit dan het aantal ogen van zijn vorige worp verliest. Wat is de kans dat de eerste speler wint?

Berichten: 652

Re: Raadsel: dobbelsteen spel

Vrijwel 50% om te winnen.
Evenveel % om te verliezen.
Zeer kleine kans op gelijk aantal ogen.
Ik ben er niet zeker van.

Gebruikersavatar
Berichten: 2.598

Re: Raadsel: dobbelsteen spel

Ik snap de uitleg niet goed. Hier een scenario.

Stel het gaat om een 8-zijdige dobbelsteen.

Speler 1 gooit 3
Speler 2 gooit 5
Speler 1 gooit 6 (5 is groter dan 3, dus ok)
Speler 2 gooit 7 (7 is groter dan 5, dus ok)
Speler 1 gooit 2 (2 is niet groter dan 6, dus speler 1 verliest)


Bedoeling is een formule te vinden voor de kans dat speler 1 wint als de dobbelsteen N zijden telt.

Berichten: 474

Re: Raadsel: dobbelsteen spel

Via een erg lange route kom ik uit op

\(\small \displaystyle \text{winst}_1(N) = \sum_{k=2}^N \frac{k-1}{N^{2k}}\binom{N}{k}\binom{N+1}{k}\)

Een aantal voorbeelden ter controle:
\(\small \displaystyle \text{winst}_1(2) = 0.1875\)
\(\small \displaystyle \text{winst}_1(6) = 0.27400847991813178697\)
\(\small \displaystyle \text{winst}_1(10) = 0.28922605708120190099\)
\(\small \displaystyle \text{winst}_1(100) = 0.30891888901075824219\)
\(\small \displaystyle \text{winst}_1(1000) = 0.31083875994882911191\)

Klopt dit, en zo ja, is er een snelle manier om tot dit antwoord te komen?

Gebruikersavatar
Moderator
Berichten: 10.209

Re: Raadsel: dobbelsteen spel

Met een Monte-Carlomethode kom ik op
2 0,187739
3 0,233072
4 0,254066
5 0,265616
6 0,273657
7 0,279805
8 0,283235
9 0,287291
10 0,289194
100 0,308427
1000 0,310983
Dat komt goed overeen met wat RedCat vindt.

Voor n=6 zijn dit de (exact berekende) kansen dat een enkele speler zijn vorige worp niet overtreft:
0
0,583333
0,324074
0,081019
0,010802
0,000750
0,000021

Verder ben ik niet gekomen.

Gebruikersavatar
Berichten: 2.598

Re: Raadsel: dobbelsteen spel

God, ik heb een verkeerde interpretatie gegeven aan de vraag. Het was lang geleden dat ik ze zelf had opgelost, maar het originele raadsel is er een waarbij ze hoger moeten gooien dan de laatste worp van de andere speler.

Scenario is dus:

Speler 1 gooit 3
Speler 2 gooit 5 (5 is groter dan 3, dus ok)
Speler 1 gooit 6 (6 is groter dan 5, dus ok)
Speler 2 gooit 7 (7 is groter dan 6, dus ok)
Speler 1 gooit 2 (2 is niet groter dan 7, dus speler 1 verliest)

Excuses.

Ik ga proberen om de oplossing van Redcat na te rekenen. Vermoedelijk zal die wel juist zijn.

Gebruikersavatar
Berichten: 2.598

Re: Raadsel: dobbelsteen spel

Stel \(p_k\) de kans dat de speler die aan de beurt is wint, gesteld dat de hoogste worp tot nu toe gelijk is aan \(k\). Je kan dan de volgende recurrentie opstellen

$$p_k=\sum_{i=k+1}^{n}\frac{1}{n}(1-p_i)$$

Je kan dit uitdrukken in functie van \(p_{k+1}\).

$$p_k=p_{k+1}+\frac{1}{n}\left(1-p_{k+1}\right)=\frac{1}{n} + \left(1-\frac{1}{n}\right)p_{k+1} $$

Er geldt dat

$$p_n=0$$

Je rekent dan terug naar \( p_0\) en komt uit op

$$p_0=\sum_{k=0}^{n-1}\frac{1}{n}\left(1-\frac{1}{n}\right)^k=1-\left(1-\frac{1}{n}\right)^n$$

Maar dat was dus niet de vraag die ik origineel stelde, ik kijk verder om de originele vraag te beantwoorden.

Gebruikersavatar
Berichten: 2.598

Re: Raadsel: dobbelsteen spel

Elke mogelijke reeks van n strikt stijgende dobbelsteenworpen kan worden verkregen door n verschillende waarden te selecteren, zonder vervanging, uit de verzameling van de N waarden van de dobbelsteen en ze vervolgens te sorteren in een strikt toenemende volgorde. Dit kan op \(N \choose n\) manieren.

Op basis hiervan geldt dat de kans \(p_n\) dat n worpen strikt stijgend zijn, gelijk is aan

$$p_n = \frac{1}{N^n} { N \choose n}.$$

Ik definieer \(q_n\) als de kans dat n-1 worpen strikt stijgend zijn en de n de worp niet stijgt. Om \(q_n\) te berekenen maak ik een opsplitising tussen de gevallen waarbij n verschillende waarden geworpen worden en de gevallen waarbij bij de laatste worp een waarde herhaald wordt.

$$q_{1,n} = \frac{1}{N^n} { N \choose n} (n-1),$$

en het geval waarbij de laatste waarde een herhaling is van een eerdere waarde

$$q_{2,n} = \frac{1}{N^n} { N \choose n-1} (n-1),$$

Ik tel beide kansen op en kom tot

$$q_n = \frac{1}{N^n} { N \choose n} (n-1) + \frac{1}{N^n} { N \choose n-1} (n-1).$$

De kans dat de eerste speler wint is


$$\sum_{k=2}^{N} p_k q_k= \sum_{k=2}^{N}\frac{1}{N^k} { N \choose k} \left( \frac{1}{N^k} { N \choose k} (k-1) + \frac{1}{N^k} { N \choose k-1} (k-1) \right)$$

$$= \sum_{k=2}^{N}\frac{(k-1)}{N^{2k}} { N \choose k} \left( { N \choose k} + { N \choose k-1} \right)$$

$$= \sum_{k=2}^{N}\frac{(k-1)}{N^{2k}} { N \choose k} { N+1 \choose k} $$

En kijk dat is de oplossing van RedCat. Mooi gedaan!

Beetje anders dan ik in gedachte had, maar mooi oplosbaar.

Berichten: 474

Re: Raadsel: dobbelsteen spel

wnvl1 schreef: za 29 jun 2024, 16:51 ... Beetje anders dan ik in gedachte had, ...
Jouw variant is een erg goede upgrade van het origineel.

Reageer