Two players play a coin-flipping game with a single fair coin. The coin is flipped once per round. Every heads counts for Player 1, and every tails counts for Player 2. Player 1 wins the moment the coin has landed heads 4 times in total; Player 2 wins the moment it has landed tails 4 times in total. The game stops immediately when either player wins. ### Constraints & Assumptions - The coin is fair: each flip is heads or tails with probability $1/2$, and flips are independent. - One shared coin is flipped once per round (the players do not flip separate coins). - The counts are cumulative totals over the whole game, not consecutive runs. - The game ends immediately at the flip on which one player's count reaches 4. ### Clarifying Questions to Ask - Is the coin fair, and are the flips independent? - Is there one shared flip per round (heads credits Player 1, tails credits Player 2), or does each player flip their own coin? - Do the four heads/tails need to be consecutive, or are they cumulative totals? - Does the game stop the instant one player reaches 4, or do we always flip a fixed number of rounds? ### Part 1 What is the maximum possible number of rounds the game can last? In other words, after how many rounds is a winner guaranteed? ```hint Pigeonhole After $n$ flips, the head count and the tail count sum to exactly $n$. How large does $n$ have to be before $\max(\text{heads}, \text{tails}) \ge 4$ is forced? Also check that the bound is achievable — exhibit a sequence that lasts that long. ``` #### What This Part Should Cover - A clean counting (pigeonhole) argument for the upper bound, not just a guessed number. - Verifying achievability: showing a concrete flip sequence in which the game actually lasts the maximum number of rounds, so the bound is tight. ### Part 2 What is the probability that the game lasts the full 7 rounds — that is, a 7th flip is actually needed to decide the winner? ```hint Translate to the first six flips The game reaches round 7 exactly when neither player has won during rounds 1–6. Express that as a condition on the number of heads among the first 6 flips, then count sequences with a binomial coefficient. ``` #### What This Part Should Cover - Correctly translating "the game reaches round 7" into an event about the first six flips, and explaining why the early-stopping rule does not complicate this event. - A clean binomial computation with the final probability stated as an exact fraction. - Awareness that with exactly 3 heads and 3 tails after six flips, neither player can have already won. ### Part 3 Now suppose you are told two facts: the game lasted the full 7 rounds, and among the first three rounds there were exactly two heads and one tail. Given this information, what is the probability that Player 1 won the game? ```hint Which flip decides the winner If the game reached round 7, what must the score have been after round 6? Then who wins is determined entirely by a single flip. ``` ```hint Red-herring check Given that the game lasted 7 rounds, does the extra detail about the first three rounds tell you anything about the deciding flip? Remember the flips are independent — you should not need a long Bayes computation. ``` #### What This Part Should Cover - Conditioning correctly: deducing what the first six flips must look like in aggregate given that the game reached round 7. - Using independence of the 7th flip to answer immediately, rather than grinding through an unnecessary Bayes'-rule calculation. - Recognizing (and being able to justify) that part of the given information is redundant — and verifying the shortcut with a quick enumeration if challenged. ### What a Strong Answer Covers Across all parts, the interviewer is checking that you can: - Translate game rules and stopping conditions into precise events about an i.i.d. flip sequence. - Execute small combinatorial computations quickly and state exact answers as fractions. - Spot when conditioning information is irrelevant instead of mechanically applying Bayes' rule, and defend the shortcut rigorously when probed. - Communicate the reasoning crisply, stating assumptions (fair coin, independence, immediate stopping) up front. ### Follow-up Questions - Generalize: if Player 1 needs $n$ heads and Player 2 needs $n$ tails, what is the maximum game length, and what is the probability the game lasts the full $2n-1$ rounds? - Suppose the coin is biased with $P(\text{heads}) = p$. Given that the game lasted 7 rounds, what is the probability Player 1 won? Does the first-three-rounds information matter now? - What is the expected number of rounds the game lasts with a fair coin? - This game is equivalent to a best-of-7 playoff series between evenly matched teams. What is the probability such a series goes to a game 7, and why does it match your Part 2 answer?