HMMT 二月 2015 · COMB 赛 · 第 4 题

英文解析

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 possiblek having equal probability. Alice Czarina continues until there are no more rocks in the pile. Let p bethe probability that the number of rocks left in the pile after each round is a multiple of 5. If p is ofca bthe form 5 · 31 · , where a, b are integers and c, d are positive integers relatively prime to 5 · 31, finda + b .d
   1 6 11 16 2006 2011
   Answer: − 501 We claim that p = · · · . Let p be the probability that, startingn
   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 wehavep + p + · · · + p + p
   5 k − 5 5 k − 10 5 0
   p =
   5 k
   5 kfor k ≥ 1. For k ≥ 2 we replace k with k − 1, giving usp + 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 kthe claim.
   Now, the power of 5 in the denominator is v (2015!) = 403 + 80 + 16 + 3 = 502, and 5 does not divideany term in the numerator. Hence a = − 502. (The sum counts multiples of 5 plus multiples of 5 plus 25
   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 theform 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.2
   Thus a + b = − 501.