HMMT 二月 2003 · COMB 赛 · 第 10 题

英文解析

10. A calculator has a display, which shows a nonnegative integer N , and a button, whichreplaces 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 ispressed 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 givennumber M < N will appear at some point is 1 / ( M +1). We can show this by inductionon N . If N = M + 1 (the base case), M can only be reached if it appears after the firststep, and this occurs with probability 1 /N = 1 / ( M + 1). If N > M + 1 and the claimholds for N − 1, then there are two possibilities starting from N . If the first step leadsto N − 1 (this occurs with probability 1 /N ), the probability of seeing M subsequentlyis 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 } withequal probability. But this is exactly what the first step would have been if we hadstarted 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 ifwe start at N ; note that this is the same as the conditional probability of seeing Mgiven 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