Two players simultaneously each pick an integer from 1 to 100 (inclusive). The winner is decided as follows: take the **larger** of the two picks, subtract 10 from it, and compare the result with the smaller pick — whichever of these two values is larger wins the game. Devise the best strategy for playing this game, and be prepared to defend every step of your reasoning: the interviewer will keep pushing on *why* your strategy is right. ### Constraints & Assumptions - Picks are integers in $\{1, 2, \dots, 100\}$, chosen simultaneously in a single round (no repetition, no communication). - If both players pick the same number, the game is a draw. - If the larger pick minus 10 exactly equals the smaller pick, the game is a draw. - Score the game as zero-sum: $+1$ for a win, $-1$ for a loss, $0$ for a draw. Both players are rational and know the rules. ### Clarifying Questions to Ask - What happens on ties — both when the two picks are equal, and when the larger pick minus 10 exactly equals the smaller pick? - Is this a one-shot simultaneous game, or repeated play where I can learn my opponent's tendencies? - Am I maximizing the probability of winning, or a win/loss/draw payoff? (With the symmetric zero-sum scoring above, these lead to the same analysis.) - Should I assume the opponent is fully rational and adversarial, or is the opponent's strategy known/fixed? ### Part 1 First, nail down the mechanics. If the two picks are $x$ and $y$ with $x > y$, exactly when does the player who chose the larger number $x$ win, lose, or draw? State the outcome as a function of the gap $g = x - y$. ```hint Case on the gap The comparison is $(x - 10)$ versus $y$, which is the same as comparing the gap $g = x - y$ with 10. Work out all three cases — and notice the counterintuitive middle zone where picking *smaller* is better. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 2 Now argue about strategy. First show that no deterministic (pure) strategy can ever be optimal. Then argue rigorously — not just from intuition — that there is some threshold $T$ such that a rational player should never play a number below $T$. The interviewer will keep pressing: *"Why does the cutoff sit exactly where it does, and not somewhere else?"* Derive $T$ from the structure of the game and prove it, don't just assert it. ```hint Exploit any known pick Using the Part 1 win condition, list everything that beats a fixed known pick $x$. If your opponent knows your number in advance, can you ever be safe? ``` ```hint Compare a low pick to one shifted up by the penalty Take any pick $a$ and compare it directly to $a + 10$ or $a + 20$ (whichever stays $\le 100$): using only the Part 1 case rule, is the shifted pick ever strictly worse against *any* fixed opponent pick $b$? Check a few values of $b$ by hand before generalizing — this is a dominance argument, and it doesn't require any equilibrium computation yet. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### Part 3 Focus on the range of numbers that survive the elimination from Part 2 — the ones a rational player would never rule out. Is there a number in that range that is better than all the others in it? Describe the structure of the win/loss relation restricted to that range, and use it to state — and verify — the optimal way to randomize over it. ```hint Tournament structure Restrict the "beats" relation from Part 1 to just the surviving range: for each number in it, count how many of the other numbers in the range it beats, how many it loses to, and how many it ties. The pattern you find should remind you of a classic game. ``` ```hint Indifference check A mixed strategy is a symmetric equilibrium if every number in its support earns the same expected payoff against it, and every number outside the support earns strictly less. Verify both conditions for your proposed mix. ``` #### What This Part Should Cover ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### Follow-up Questions - If the penalty subtracted from the larger pick is $k$ instead of 10, what does the optimal strategy become? What is the pattern? - If the picks range over 1 to $N$ for large $N$ instead of 1 to 100, does the answer change? - Suppose you knew your opponent picks uniformly at random over all of 1–100. What is your best response, and what is your expected payoff? - How does the analysis change if a draw (larger pick minus 10 equals the smaller pick) is instead ruled a win for the smaller pick?