HMMT 二月 2018 · ALGNT 赛 · 第 7 题
HMMT February 2018 — ALGNT Round — Problem 7
题目详情
- Rachel has the number 1000 in her hands. When she puts the number x in her left pocket, the number − 1 changes to x + 1. When she puts the number x in her right pocket, the number changes to x . Each minute, she flips a fair coin. If it lands heads, she puts the number into her left pocket, and if it lands tails, she puts it into her right pocket. She then takes the new number out of her pocket. If the E expected value of the number in Rachel’s hands after eight minutes is E , then compute b c . 10
解析
- Rachel has the number 1000 in her hands. When she puts the number x in her left pocket, the number − 1 changes to x + 1. When she puts the number x in her right pocket, the number changes to x . Each minute, she flips a fair coin. If it lands heads, she puts the number into her left pocket, and if it lands tails, she puts it into her right pocket. She then takes the new number out of her pocket. If the E expected value of the number in Rachel’s hands after eight minutes is E , then compute b c . 10 Proposed by: Kevin Sun Answer: 13 1 Call a real number very large if x ∈ [1000 , 1008], very small if x ∈ [0 , ], and medium-sized if 1000 1 x ∈ [ , 8]. Every number Rachel is ever holding after at most 8 steps will fall under one of these 8 categories. Therefore the main contribution to E will come from the probability that Rachel is holding a number at least 1000 at the end. Note that if her number ever becomes medium-sized, it will never become very large or very small again. Therefore the only way her number ends up above 1000 is if the sequence of moves consists of − 1 x → x + 1 moves and consecutive pairs of x → x moves. Out of the 256 possible move sequences, the number of ways for the number to stay above 1000 is the number of ways of partitioning 8 into an ordered sum of 1 and 2, or the ninth Fibonacci number F = 34. 9 Therefore 34 34 · 1000 ≤ E ≤ · 1000 + 8 , 256 256 34 where · 1000 ≈ 132 . 8. Furthermore, the extra contribution will certainly not exceed 7, so we get 256 E that b c = 13. 10 (The actual value of E is 1538545594943410132524842390483285519695831541468827074238984121209064525621 , 11415831910281261197289931074429782903650103348754306523894286954489856000 which is approximately equal to 134 . 77297. We can see that the extra contribution is about 2 and is very insignificant.)