You play the following game: four fair coins are tossed at the same time. For every coin that lands heads, you are paid \$1. The interviewer walks you through the game in three stages, adding a "magic wand" that lets you modify the coins after you see the initial toss. ### Constraints & Assumptions - All four coins are fair and independent: each lands heads with probability $1/2$. - The payoff is exactly \$1 per head showing at the end; there are no other costs or payoffs. - In Parts 2 and 3 the wand is used **after** you observe the initial toss, you may use it an unlimited number of times, and each use is free. - "A pair" means any two distinct coins of your choice, and you may choose a different pair on every use (fully adaptive play). - You are risk-neutral, so the fair price of a wand is the increase in your expected payoff from owning it. ### Clarifying Questions to Ask - Are the coins fair, and are the four tosses independent? - Do I see the coins before deciding how to use the wand, and can I choose each pair adaptively based on the current state? - For the "turn over" wand, do both chosen coins deterministically flip to their opposite faces (heads becomes tails and vice versa)? - Is every use of the wand free, with no limit on the number of uses, and do I decide when to stop and collect the payoff? - Should I price the wand for a risk-neutral player, i.e., fair price equals the gain in expected payoff? ### Part 1 What is your expected payoff from the game (no wand)? ```hint One line, no enumeration Use linearity of expectation: the expected payoff is the sum of each coin's expected contribution. You never need to list all $2^4$ outcomes. ``` #### What This Part Should Cover - Applying linearity of expectation across the four coins instead of enumerating outcomes. - Stating the per-coin expected contribution and combining it into a clean numeric answer. ### Part 2 You are offered a magic wand. After seeing the toss, the wand lets you **turn over any pair of coins** (both chosen coins flip to their opposite faces). You may use it as many times as you like. What is a fair price for this wand? ```hint Look for an invariant Turning over two coins changes the number of heads by $-2$, $0$, or $+2$, depending on what the two coins were showing. What property of the head count can no sequence of pair-flips ever change? ``` ```hint Best reachable payoff Split the $16$ equally likely initial outcomes into classes the wand cannot move between. For each class, find the largest head count you can reach, and weight by the probability of the class. ``` #### What This Part Should Cover - Identifying what a pair-flip can and cannot change about the configuration of heads. - Determining the best reachable payoff from each class of starting outcomes, with a constructive argument that it is reachable and an argument that nothing better is. - Computing the expected payoff with the wand and pricing it as the difference versus Part 1. ### Part 3 The wand's power changes: now each use lets you **pick any pair of coins and re-toss both of them**. Again you may use it an unlimited number of times, free of charge, and you decide when to stop. What is a fair price for this wand? ```hint What changed versus Part 2 Re-tossing is random, so the constraint you found in Part 2 no longer binds. Notice that re-tossing two coins that both show tails can never make you worse off. Which pair should you re-toss whenever at least two tails are showing? ``` ```hint The only risky decision The interesting state is exactly three heads: any re-toss must now include a head, so you can lose ground. Either set up the optimal-stopping value equations for the states "two heads" and "three heads," or look for a strategy that only ever stops in one particular state. ``` #### What This Part Should Cover - Recognizing that re-tossing removes the structural restriction from Part 2 and injects fresh randomness with free retries. - A correct treatment of the stop-or-continue decision at three heads (value equations or a dominance/absorption argument). - Arguing termination: the proposed strategy reaches its target state with probability 1, so the claimed expected payoff is actually achieved. - Pricing the wand as the gain in expected payoff, and comparing it with the Part 2 wand. ### What a Strong Answer Covers Across all three parts, the interviewer is checking that the candidate: - Prices every option the same way: value of the tool = expected payoff with it minus expected payoff without it, under risk neutrality. - Reasons structurally about the allowed operation (invariants for the deterministic wand, monotone never-lose moves for the random one) instead of brute-forcing cases. - Is careful about what "unlimited free uses" buys, including why the two wands are not worth the same amount. - Communicates a clean final number for each part and sanity-checks it against simple bounds (the payoff can never exceed \$4). ### Follow-up Questions - Generalize Part 2 and Part 3 to $n$ fair coins. How do the two wand prices behave as $n$ grows? - Suppose each use of the Part 3 wand costs a fee $c > 0$. How does your strategy change, and for what values of $c$ is the wand worth buying at all? - What if the wand in Part 3 could only be used at most $k$ times? Set up (don't fully solve) the dynamic program for its value. - Redo Part 1 and Part 2 with biased coins that land heads with probability $p$. Which parts of your argument survive unchanged?