Problem:
Adam is rolling a fair 10-sided die. He gets to roll repeatedly and may decide when to stop at any time.
If he obtains a value that is not 10 on each roll, he adds the upface to his total monetary sum.
If he rolls a 10, he loses all of his money.
If Adam plays optimally, he should stop once he has at least
$k$total.Find
$k$.
At any state Adam has two choices, he can either roll the die again or stop and collect his winnings. Only when he rolls a 10 does he lose all of his money.
The objective function for this problem is defined as follows:
$$\lambda(k) = \frac{1}{10}\sum_{i=1}^{9} (k+i) + \frac{1}{10}(0)$$
Where $k$ is the current state of the game and $k+i$ is the sum of the current state plus the value of the next roll.
We know the optimal stopping point belongs to the set of states where the objective function is greater than or equal to the current state such that:
$$S = \{k \in \mathbb{N} : \lambda(k) \geq k\}$$
The optimal stopping point is the largest value of $k$ in the set $S$.
In code we define this as follows:
def obj(k):
return 1/10 * sum(k + i for i in range(1, 10))
best = 0
for k in range(1000):
if obj(k) >= k:
if obj(k) > best:
best = obj(k)
Which gives us the optimal stopping point of $45$.