HMMT 二月 2021 · COMB 赛 · 第 10 题
HMMT February 2021 — COMB Round — Problem 10
题目详情
- Jude repeatedly flips a coin. If he has already flipped n heads, the coin lands heads with probability 1 n +1 and tails with probability . If Jude continues flipping forever, let p be the probability that he n +2 n +2 flips 3 heads in a row at some point. Compute b 180 p c .
解析
- Jude repeatedly flips a coin. If he has already flipped n heads, the coin lands heads with probability 1 n +1 and tails with probability . If Jude continues flipping forever, let p be the probability that he n +2 n +2 flips 3 heads in a row at some point. Compute b 180 p c . Proposed by: Anders Olsen Answer: 47 Solution: Let p be the probability that the n th head is flipped after a tail and Jude has yet to flip n 2 3 heads consecutively to this point. For example, p = , as it is impossible for 3 heads to be flipped 2 3 consecutively and the second head comes after a tail exactly when the first flip after the first head is a 1 See https://en.wikipedia.org/wiki/Catalan_number%23Second_proof for useful pictures 2 3 tail, which happens with probability . Similarly, p = . We now establish a recursion between values 3 3 4 of p : n n 1 p = p + p . n n − 1 n − 2 n + 1 n + 1 The first term comes from when the previous head had tails both before and after, and the second term comes from when the previous 2 heads were consecutive. Of course there cannot be other terms, as this would imply that 3 heads were flipped consecutively. This enables us to easily compute the 11 53 103 next few terms: , , , and so on. Notably, the differences between consecutive terms (starting 15 72 140 i ∑ n +1 ( − 1) 2 2 2 2 from p − p ) are , − , , − , and so on. This leads us to guess that p = 2 , which 3 2 n i =0 24 120 720 5040 i ! indeed satisfies the given recurrence relation. Then ∞ i ∑ ( − 1) 2 lim p = 2 = . n n →∞ i ! e i =0 But since the probability that the n th head comes after a tail approaches 1 as n increases, this limit is the same as the limit of the probability that the first n heads do not include 3 that came consecutively. Then this limit is just the probability that we never flip 3 consecutive heads. Then the desired 2 360 probability is just p = 1 − . We are asked to compute b 180 p c . This is the floor of 180 − . To e e compute 360 /e, note that we can just truncate the infinite sum ∞ n ∑ 360 360( − 1) = , e n ! n =0 1 as it converges rather quickly. The first several terms are 360 − 360 + 180 − 60 + 15 − 3 + , and the 2 rest are insignificant. This sums to about 132 . 5 , giving an answer of b 180 − 132 . 5 c = 47 .