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 ```premium-lock What This Part Should Cover ``` ### 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 ```premium-lock What This Part Should Cover ``` ### 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 ```premium-lock What This Part Should Cover ``` ### What a Strong Answer Covers ```premium-lock What a Strong Answer Covers ``` ### 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?