HMMT 二月 2013 · 冲刺赛 · 第 32 题

英文解析

32. [ 20 ] For an even integer positive integer n Kevin has a tape of length 4 n with marks at − 2 n, − 2 n +
    1 , . . . , 2 n − 1 , 2 n . He then randomly picks n points in the set − n, − n + 1 , − n + 2 , . . . , n − 1 , n , andplaces a stone on each of these points. We call a stone ‘stuck’ if it is on 2 n or − 2 n , or either all the points to the right, or all the points to the left, all contain stones. Then, every minute, Kevin shiftsthe unstuck stones in the following manner:
    • He picks an unstuck stone uniformly at random and then flips a fair coin.
    Guts Round
    • If the coin came up heads, he then moves that stone and every stone in the largest contiguous setcontaining that stone one point to the left. If the coin came up tails, he moves every stone in that setone point right instead.
    • He repeats until all the stones are stuck.
    Let p be the probability that at the end of the process there are exactly k stones in the right half.
    Evaluatekp − p + p − . . . + p − p + pn − 1 n − 2 n − 3 3 2 1
    p + p + p + . . . + p + p + pn − 1 n − 2 n − 3 3 2 1
    in terms of n .
    Answer: After we have selected the positions of the initial n stones, we number their 1
    n − 1
    positions: a < a < . . . < a . The conditions on how we move the stones imply that the expected
    1 2 nvalue of ( a − a ) after t minutes is still equal to a − a . In addition, if b is the final position of thei j i j ii th stone, E ( b − b ) = E ( a − a ). But this quantity is also equal to (3 n + 2) · p + 1 · (1 − p ).
    i +1 i i +1 i i i
    Now, let’s calculate the expected value of a − ai . This is the sum over g = a − a , and j , thei +1 i +1 i
    ( )( )
    j 2 n − j − gnumber of spaces before a of g · , so we geti − 1 n − i +1 i
    ( )( )
    ∑ ∑
    1 j 2 n − j − g
    ( ) g ·
    2 n +1
    i − 1 n − i − 1
    n gj
    ( )( ) ( )
    ∑
    j 2 n − j − g 2 n − g +1
    But is just . Therefore the expected value of a − a is independent of i ,
    i +1 iji − 1 n − i − 1 n − 1
    so p is constant for all i 6 = 0 , n . It follows that the answer is .1
    n − 1 i
    25 24 23 2 1