HMMT 二月 2015 · COMB 赛 · 第 4 题
HMMT February 2015 — COMB Round — Problem 4
题目详情
- Alice Czarina is bored and is playing a game with a pile of rocks. The pile initially contains 2015 rocks. At each round, if the pile has N rocks, she removes k of them, where 1 ≤ k ≤ N , with each possible k having equal probability. Alice Czarina continues until there are no more rocks in the pile. Let p be the probability that the number of rocks left in the pile after each round is a multiple of 5. If p is of c a b the form 5 · 31 · , where a, b are integers and c, d are positive integers relatively prime to 5 · 31, find d a + b .
解析
- Alice Czarina is bored and is playing a game with a pile of rocks. The pile initially contains 2015 rocks. At each round, if the pile has N rocks, she removes k of them, where 1 ≤ k ≤ N , with each possible k having equal probability. Alice Czarina continues until there are no more rocks in the pile. Let p be the probability that the number of rocks left in the pile after each round is a multiple of 5. If p is of c a b the form 5 · 31 · , where a, b are integers and c, d are positive integers relatively prime to 5 · 31, find d a + b . 1 6 11 16 2006 2011 Answer: − 501 We claim that p = · · · . Let p be the probability that, starting n 5 10 15 20 2010 2015 with n rocks, the number of rocks left after each round is a multiple of 5. Indeed, using recursions we have p + p + · · · + p + p 5 k − 5 5 k − 10 5 0 p = 5 k 5 k for k ≥ 1. For k ≥ 2 we replace k with k − 1, giving us p + p + · · · + p + p 5 k − 10 5 k − 15 5 0 p = 5 k − 5 5 k − 5 = ⇒ (5 k − 5) p = p + p + · · · + p + p 5 k − 5 5 k − 10 5 k − 15 5 0 Substituting this back into the first equation, we have 5 kp = p + ( p + p + · · · + p + p ) = p + (5 k − 5) p , 5 k 5 k − 5 5 k − 10 5 k − 15 5 0 5 k − 5 5 k − 5 Combinatorics 5 k − 4 which gives p = p . Using this equation repeatedly along with the fact that p = 1 proves 5 k 5 k − 5 0 5 k the claim. Now, the power of 5 in the denominator is v (2015!) = 403 + 80 + 16 + 3 = 502, and 5 does not divide 5 2 any term in the numerator. Hence a = − 502. (The sum counts multiples of 5 plus multiples of 5 plus 3 n n +1 multiples of 5 and so on; a multiple of 5 but not 5 is counted exactly n times, as desired.) Noting that 2015 = 31 · 65, we found that the numbers divisible by 31 in the numerator are those of the 2 form 31 + 155 k where 0 ≤ k ≤ 12, including 31 = 961; in the denominator they are of the form 155 k 2 where 1 ≤ k ≤ 13. Hence b = (13 + 1) − 13 = 1 where the extra 1 comes from 31 in the numerator. Thus a + b = − 501.