# Optimal Stopping with Square-Number Ruin You repeatedly roll a fair six-sided die and add each roll to a running total. Before each roll, you may stop and receive the current total. If a roll makes the total a positive perfect square, the game ends immediately and you receive zero. Determine an optimal stopping rule and explain how to compute the value of the game. ### Constraints & Assumptions - The running total starts at zero, and stopping at zero is allowed. - Perfect squares are 1, 4, 9, 16, and so on. - A roll that lands on a square causes ruin before another stop decision. - The answer may present a dynamic-programming computation and a threshold or state-dependent policy rather than one closed-form number. ### Clarifying Questions to Ask - Is there a maximum number of rolls or a maximum total? - Does landing above a square have any effect, or only landing exactly on one? - Must a practical solution provide a numerical truncation error bound? ```hint Test square boundaries Compare decisions at totals immediately before and immediately after a perfect square, and distinguish landing on a square from jumping past it. ``` ```hint Check decision timing Stopping at zero is permitted, while a ruin roll ends the game before another decision can be made. ``` ### What a Strong Answer Covers - A Bellman equation that compares stopping now with the expected value of rolling. - Correct zero value for transitions landing on perfect squares. - A finite computation or convergence argument for the unbounded state space. - A policy described by the states in which stopping dominates rolling. ### Follow-up Questions - How would the policy change for a die with a different set of face values? - Can you bound the error introduced by solving only up to a large terminal total?