Brainteaser sympa (from J.S. )
On possède devant nous un dé à 20 faces, les rolistes comprendront. Il est équilibré. On joue à un jeu avec les règles suivantes :
- on peut jouer $n = 100$ fois, on dit qu’on a $n$ essais
- à chaque essaie on peu ou bien récupérer le numéro du dé en cash, ou bien relancer le dé (si on relance, on ne récupère rien)
- le dé commence sur la face $1$
- on peut jouer $n = 100$ fois, on dit qu’on a $n$ essais
- à chaque essaie on peu ou bien récupérer le numéro du dé en cash, ou bien relancer le dé (si on relance, on ne récupère rien)
- le dé commence sur la face $1$
Stratégie optimale ? Combien coûte ce jeu ?
Ma proposition.
Je note $X$ la variable aléatoire qui correspond à un lancer de dé à 20 faces. Je pose $a = \mathbf{E}[X] = 10.5$.
On note $V[j, n]$ l’espérance du jeu quand le dé commence sur la face $j$ et qu’on a $n$ essais. Il est clair que $V[j, 1] = j$. Que vaut $V[j, 2] $ ? On a le choix entre cash out $j$ deux fois ou bien relancer une fois le dé et espérer un plus grand résultat que $2j$. En note $a$ l’espérance du dé à 20 faces, je peux en conclure que $V[j, 2] = \max ( 2j, a )$. En continuant sur cette lancée, je peux poser $V[j, n] = \max ( n \cdot j, \mathbf{E}[ V(X, n-1) ] ) $. On peut donc implémenter en $O(n^2)$ ce petit programme (en supposant $j \leq n$ ).
Je note $X$ la variable aléatoire qui correspond à un lancer de dé à 20 faces. Je pose $a = \mathbf{E}[X] = 10.5$.
On note $V[j, n]$ l’espérance du jeu quand le dé commence sur la face $j$ et qu’on a $n$ essais. Il est clair que $V[j, 1] = j$. Que vaut $V[j, 2] $ ? On a le choix entre cash out $j$ deux fois ou bien relancer une fois le dé et espérer un plus grand résultat que $2j$. En note $a$ l’espérance du dé à 20 faces, je peux en conclure que $V[j, 2] = \max ( 2j, a )$. En continuant sur cette lancée, je peux poser $V[j, n] = \max ( n \cdot j, \mathbf{E}[ V(X, n-1) ] ) $. On peut donc implémenter en $O(n^2)$ ce petit programme (en supposant $j \leq n$ ).
La stratégie se lit sur le gain : je vais note $a_1 = n \cdot j, a_2 = \mathbf{E}[ V(X, n-1) ]$. Je lance le dé tant que $a_1 \leq a_2$ et j’arrête lorsque $a_1 >a_2$, à partir de là je ne fais qu’empocher mon argent.
Je trouve $1773$ et des poussières pour la valeur du jeu, très proche de la stratégie naïve qui consiste à lancer le dé jusqu’à obtenir $18, 19$ ou $20$ et cash out ensuite.
---> ~ Heartbeat Heartbeat ~ www.youtube.com/watch?v=yogaAzfzpkk <---
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses