PUMaC 2021 · 团队赛 · 第 6 题

PUMaC 2021 — Team Round — Problem 6

Jack plays a game in which he first rolls a fair six-sided die and gets some number n ; then, he flips a coin until he flips n heads in a row and wins, or he flips n tails in a row in which case he rerolls the die and tries again. What is the expected number of times Jack must flip the coin before he wins the game? 8 7 5 4 3

解析

Jack plays a game in which he first rolls a fair six-sided die and gets some number n ; then, he flips a coin until he flips n heads in a row and wins, or he flips n tails in a row in which case he rerolls the die and tries again. What is the expected number of times Jack must flip the coin before he wins the game? Proposed by: Austen Mazenko Answer: 40 Let the expected number be E . After a given roll of the die, by symmetry the probability 1 that a win occurs compared to a reroll is . Now, given the roll was an i , consider the 2 expected number E ( i ) of coin flips before a run of i occurs given that you’ve already flipped 1 1 the coin once. Evidently, E (1) = 0. Then, E (2) = · 1 + · E (2) = ⇒ E (2) = 1. Next, 2 2 2 1 1 1 1 1 E (3) = · 2 + · (2 + E (3)) + · (1 + E (3)) = ⇒ E (3) = 6. We have E (4) = · 3 + · (3 + 4 4 2 8 8 1 1 E (4)) + · (2 + E (4)) + · (1 + E (4)) = ⇒ E (4) = 14. Similarly, E (5) = 30 and E (6) = 62. In 4 2 i general, the expected number of coin flips before a run of i appears is 2 − 1. Thus, considering the six possible starting cases, we have 6 X i 1 E E = · (2 − 1 + ) = ⇒ E = 40 . 6 2 i =1 8 7 5 4 3