El único momento en el que podríamos considerar parar es cuando $k$ es casi un cuadrado perfecto. Supongamos que $k \approx n^2$ (más específicamente, tomar $n^2-6\leq k<n^2$ ).
Si nos detenemos, nuestra puntuación es siempre al menos $n^2-6$ . Si intentamos continuar más allá $n^2$ y luego se detiene cuando casi llegamos a $(n+1)^2$ la probabilidad de que realmente pasemos $n^2$ es como máximo $\frac{5}{6}$ por lo que la puntuación esperada es, en el mejor de los casos $\frac{5}{6}\left((n+1)^2 - 1\right)=\frac{5}{6}\left(n^2+2n\right)$ . Así que parar ahora es mejor que pasar $(n+1)^2$ siempre que $n^2-6>\frac{5}{6}(n^2+2n)$ y posiblemente antes. Esta desigualdad se cumple siempre que $n \geq 13$ .
Por lo tanto, si $n$ es al menos $13$ Si no se supera el número de rondas, detenerse es mejor que hacer una ronda más, y hacer varias rondas extra no va a ayudar nunca (ya que la desigualdad nunca deja de ser cierta, por lo que hacer una ronda extra es mejor que hacer dos, que es mejor que hacer tres, y así sucesivamente). Eso significa que siempre es mejor parar antes de intentar superar $13^2=169$ es decir, cuando $k$ es al menos $163$ .
Dado que es finito (¡y no demasiado grande!) debería ser sencillo, aunque tedioso, averiguar la estrategia óptima y el valor esperado para todos los $k<163$ .
A continuación se presenta un sencillo código Sage (para la aritmética racional exacta) para encontrar la estrategia óptima:
#!/usr/bin/env sage -python
from sage.all import *
evs_dict = dict([(n, QQ(n)) for n in range(163, 169)])
for n in range(162, -1, -1):
if sqrt(n) in ZZ and n != 0:
evs_dict[n] = 0
else:
evs_dict[n] = max(QQ('1/6') * sum(evs_dict[n+k] for k in range(1, 7)), n)
for n in range(0, 169):
ev = evs_dict[n]
print n, ev if ev in ZZ else ev.n()
Parece que lo óptimo es parar cuando $k \geq 75$ y cerca de un cuadrado perfecto, o cuando $k \in \{30, 31, 43, 44, 45, 58, 59, 60, 61, 62 \}$ . También, $f(0) \approx 7.17549931276711$ .
La versión "cubo perfecto" de este problema debería funcionar de forma similar.
La versión en la que se pierde si se alcanza una potencia de $2$ es más interesante. Se puede comprobar que incluso en el peor de los casos - cuando se aterriza en $2^n-6$ - la posibilidad de superar con éxito $2^n$ es mayor que $\frac{1}{2}$ y subiendo a $2^{n+1}$ duplicará aproximadamente su puntuación si tiene éxito. Así que el valor esperado de continuar una ronda más supera el valor esperado de parar, y sin embargo, el valor esperado de continuar para siempre es claramente cero. Es decir, hay no estrategia óptima, sino una sucesión de estrategias cada vez mejores.
Los juegos infinitos son raros a veces...
