HMMT 二月 2003 · COMB 赛 · 第 10 题
HMMT February 2003 — COMB Round — Problem 10
题目详情
- A calculator has a display, which shows a nonnegative integer N , and a button, which replaces N by a random integer chosen uniformly from the set { 0 , 1 , . . . , N − 1 } , pro- vided that N > 0. Initially, the display holds the number N = 2003. If the button is pressed repeatedly until N = 0, what is the probability that the numbers 1 , 10 , 100, and 1000 will each show up on the display at some point? 2
解析
- A calculator has a display, which shows a nonnegative integer N , and a button, which replaces N by a random integer chosen uniformly from the set { 0 , 1 , . . . , N − 1 } , pro- vided that N > 0. Initially, the display holds the number N = 2003. If the button is pressed repeatedly until N = 0, what is the probability that the numbers 1 , 10 , 100, and 1000 will each show up on the display at some point? Solution: 1 / 2224222 First, we claim that if the display starts at some N , the probability that any given number M < N will appear at some point is 1 / ( M +1). We can show this by induction on N . If N = M + 1 (the base case), M can only be reached if it appears after the first step, and this occurs with probability 1 /N = 1 / ( M + 1). If N > M + 1 and the claim holds for N − 1, then there are two possibilities starting from N . If the first step leads to N − 1 (this occurs with probability 1 /N ), the probability of seeing M subsequently is 1 / ( M + 1) by the induction hypothesis. If the first step leads to something less than N − 1 (probability ( N − 1) /N ), then it leads to any of the integers { 0 , 1 , . . . , N − 2 } with equal probability. But this is exactly what the first step would have been if we had started from N − 1; hence, the probability of seeing M is again 1 / ( M +1) by induction. 1 1 N − 1 1 Thus, the overall probability of seeing M is · + · = 1 / ( M + 1), proving N M +1 N M +1 the induction step and the claim. Now let P ( N, M ) ( M < N ) be the probability of eventually seeing the number M if we start at N ; note that this is the same as the conditional probability of seeing M given that we see N . Hence, the desired probability is 1 1 1 1 1 P (2003 , 1000) · P (1000 , 100) · P (100 , 10) · P (10 , 1) = · · · = . 1001 101 11 2 2224222 4