Cash King

Solution

A natural class of strategies is: reroll until we see a number at least as large as some threshold \(t\), and then stop rerolling and cash out that face value for all remaining moves. This is a very clean way to attack the game. If we choose a threshold \(t\), then two quantities matter: - how long it takes on average to see a value at least \(t\), - what that accepted value is worth on average. If the die is \(20\)-sided, then the values we accept are \[ t,t+1,\dots,20. \] There are \[ 21-t \] such values, so the probability that a given roll is acceptable is \[ p = \frac{21-t}{20}. \] The expected number of rolls needed to hit one of those values is therefore \[ E[R] = \frac{1}{p} = \frac{20}{21-t}. \] Once we do hit an acceptable value, that value is equally likely to be any of \[ t,t+1,\dots,20, \] so its average is \[ E[V] = \frac{t+20}{2}. \] If it takes about \[ \frac{20}{21-t} \] moves to find the value, then we have about \[ 100 - \frac{20}{21-t} \] moves left to cash it out. So the expected payout for threshold \(t\) is approximately \[ E[X_t] = \left(100 - \frac{20}{21-t}\right)\left(\frac{t+20}{2}\right). \] Now we just compare a few thresholds. If we wait for a \(20\) only, then the expected wait is \[ \frac{20}{1} = 20 \] moves, and the value we cash out is \[ 20. \] So the expected payout is \[ (100-20)\cdot 20 = 80\cdot 20 = 1600. \] If we accept \(19\) or \(20\), then the expected wait is \[ \frac{20}{2} = 10, \] and the accepted value averages \[ \frac{19+20}{2} = 19.5. \] So the expected payout is \[ (100-10)\cdot 19.5 = 90\cdot 19.5 = 1755. \] If we accept \(18,19,20\), then the expected wait is \[ \frac{20}{3}, \] and the accepted value averages \[ \frac{18+20}{2} = 19. \] So the expected payout is \[ \left(100-\frac{20}{3}\right)\cdot 19 = \frac{280}{3}\cdot 19 = \frac{5320}{3} \approx 1773.33. \] If we accept \(17,18,19,20\), then the expected wait is \[ \frac{20}{4} = 5, \] and the accepted value averages \[ \frac{17+20}{2} = 18.5. \] So the expected payout is \[ (100-5)\cdot 18.5 = 95\cdot 18.5 = 1757.5. \] If we accept \(16\) or better, then the expected wait is \[ \frac{20}{5} = 4, \] and the accepted value averages \[ \frac{16+20}{2} = 18. \] So the expected payout is \[ (100-4)\cdot 18 = 96\cdot 18 = 1728. \] Now a pattern has appeared: \[ 1600,\quad 1755,\quad 1773.33,\quad 1757.5,\quad 1728,\dots \] The expected value increases as we relax the threshold from \(20\) down to \(18\), but then starts falling once we go below \(18\). So the best threshold is \[ t=18. \] A full dynamic programming solution can refine this slightly near the very end of the game, but this threshold argument is the cleanest way to derive the main strategy and gets essentially the optimal play.