Brainteaser sympa (from J.S. )

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$ ).

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.