Alice and Bob play a dice game. Alice has a fair 30-sided die (faces $1$ through $30$) and Bob has a fair 20-sided die (faces $1$ through $20$). Each player wants their final number to be as high as possible: whoever shows the higher number wins, and **ties are awarded to Bob**. They roll simultaneously. Bob, however, gets one extra option: if he is unhappy with his first roll, he may reroll his die **once**. He makes this decision without seeing Alice's number, and if he rerolls he must keep the second result. Alice has no reroll. Assuming Bob plays optimally, what is the probability that Alice wins? ```hint Simplify Bob's objective Alice's roll is uniform on $\{1, \ldots, 30\}$ and Bob's number can never exceed $20$. So the probability Bob wins given his final number is $b$ is a simple **linear** function of $b$. What single quantity should Bob therefore maximize? ``` ```hint Threshold strategy Bob's optimal rule is a cutoff: keep the first roll when it beats what a fresh roll is worth in expectation, reroll otherwise. Compare keeping a value $b$ against the expected value of one new throw of a d20. ``` ### Constraints & Assumptions - Both dice are fair: Alice's roll is uniform on $\{1, \ldots, 30\}$, Bob's rolls are uniform on $\{1, \ldots, 20\}$, and all rolls are independent. - Bob's reroll decision may depend only on his own first roll — he never observes Alice's number before deciding. - Bob has at most one reroll, and a rerolled result is final (he cannot revert to his first roll). - Ties count as a win for Bob, so Alice wins exactly when her number is strictly greater than Bob's final number. - "Optimal" means Bob maximizes his own probability of winning. ### Clarifying Questions to Ask - Does Bob see Alice's roll before deciding whether to reroll? (No — the decision is blind.) - If Bob rerolls, can he keep the better of his two rolls, or is the second roll binding? (The second roll is binding.) - How exactly are ties resolved? (A tie is a win for Bob.) - Are the dice fair and are all rolls independent? (Yes.) - Is Bob restricted to deterministic strategies, or could randomized strategies matter here? ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - How does the answer change if ties are awarded to Alice instead of Bob? - Suppose Bob observes Alice's roll *before* deciding whether to reroll. What is his optimal rule then, and what is Alice's winning probability? - If Bob had two rerolls instead of one (each subsequent roll binding until the last), how would you set the two thresholds, and would they be equal? - The reduction you used relies on a particular relationship between the two dice. If Bob rolled a 40-sided die against Alice's 30-sided die, why does "maximize the expected final roll" stop being the right objective, and how would you solve it instead?