HMMT 二月 2011 · 冲刺赛 · 第 11 题
HMMT February 2011 — Guts Round — Problem 11
题目详情
- [ 8 ] Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let a = 4, 1 a = 3, and a = a + a for all n ≥ 3. On the n th flip, if the coin is heads, Rosencrantz pays 2 n n − 1 n − 2 Guildenstern a dollars, and, if the coin is tails, Guildenstern pays Rosencrantz a dollars. If play n n continues for 2010 turns, what is the probability that Rosencrantz ends up with more money than he started with?
解析
- [ 8 ] Rosencrantz and Guildenstern play a game in which they repeatedly flip a fair coin. Let a = 4, 1 a = 3, and a = a + a for all n ≥ 3. On the n th flip, if the coin is heads, Rosencrantz pays 2 n n − 1 n − 2 Guildenstern a dollars, and, if the coin is tails, Guildenstern pays Rosencrantz a dollars. If play n n continues for 2010 turns, what is the probability that Rosencrantz ends up with more money than he started with? 1 1 Answer: − 1341 2 2 Since Rosencrantz and Guildenstern have an equal chance of winning each toss, both have the same probability of ending up with a positive amount of money. Let x denote the probability that they both 1 − x end up with zero dollars. We wish to find . 2 We have x is equal to the probability that s := i a + i a + · · · i a = 0 , 2010 1 1 2 2 2010 2010 where i has an equal probability of being either 1 or − 1. n We claim that s = 0 if and only if i = − i = − i for all n ≤ 670. We start with the 2010 3 n 3 n − 1 3 n − 2 following lemma. n − 3 ∑ Lemma. We have a > a for all n ≥ 4. n k k =1 Proof: For the case n = 4, a = a + a = 2 a + a > a . In case n > 4, we have 4 3 2 2 1 1 n − 4 n − 3 n − 3 ∑ ∑ ∑ a = a + a > a + a = a + a > a . n n − 2 n − 1 n − 2 k n − 4 k k k =1 k =1 k =1 It suffices to show that s = 0 only if i = − i = − i for all k ≤ n . The triangle inequality 3 n 3 k 3 k − 1 3 k − 2 implies the following: ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ 0 ≤ i a + s − i a + i a ≤ | s | = 0 ∣ ∣ 3 n − 2 3 n − 2 3 n − 3 3 n − 1 3 n − 1 3 n 3 n 3 n ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ 0 ≤ i a + s − i a + i a ≤ | s | = 0 ∣ ∣ 3 n − 1 3 n − 1 3 n − 3 3 n − 2 3 n − 2 3 n 3 n 3 n Guts Round By the lemma, we have 3 n − 3 ∑ a + a < a + a < a + a 3 n − 2 k 3 n − 2 3 n 3 n − 1 3 n k =1 3 n − 3 ∑ a + a < a + a + a + a = a + a 3 n − 1 k 3 n − 1 3 n − 3 3 n − 4 3 n − 2 3 n − 2 3 n k =1 ∣ ∣ ∣ 3 n − 3 ∑ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ ∣ i = i implies a + a < i a + i a and i = i implies a + 3 n 3 n − 1 3 n − 2 k 3 n − 1 3 n − 1 3 n 3 n 3 n 3 n − 2 3 n − 1 ∣ ∣ ∣ k =1 ∣ 3 n − 3 ∑ ∣ ∣ ∣ ∣ ∣ ∣ a < i a + i a , which are both contradictions; therefore, we must have i = − i k 3 n − 2 3 n − 2 3 n 3 n 3 n 3 n − 1 ∣ k =1 and i = − i . 3 n 3 n − 2 ( ) 670 1 1 1 1 − x 1 1 The probability that i = − i = − i is , so x = = , and = − . 3 n 3 n − 1 3 n − 2 1340 1341 4 4 2 2 2 2