HMMT 二月 2014 · 冲刺赛 · 第 29 题

英文解析

29. [ 20 ] Natalie has a copy of the unit interval [0 , 1] that is colored white. She also has a black marker,
    and she colors the interval in the following manner: at each step, she selects a value x ∈ [0 , 1] uniformlyat random, and
    1 1
    (a) If x ≤ she colors the interval [ x, x + ] with her marker.
    2 2
    1 1
    (b) If x > she colors the intervals [ x, 1] and [0 , x − ] with her marker.
    2 2
    What is the expected value of the number of steps Natalie will need to color the entire interval black?
    Answer: 5 The first choice always wipes out half the interval. So we calculate the expected valueof the amount of time needed to wipe out the other half.
    Solution 1 (non-calculus):
    We assume the interval has 2 n points and we start with the last n colored black. We let f ( k ) be theexpected value of the number of turns we need if there are k white points left. So we must calculatef ( n ).
    We observe that
    ∑
    k − 1
    ( n − k + 1) · 0 + ( n − k + 1) · f ( k ) + 2 f ( i )
    i =1
    f ( k ) = 1 +
    2 n
    ∑
    k − 1
    n + k − 1 f ( i )
    i =1
    f ( k ) = 1 +
    2 n n
    ∑
    n + k f ( i )ki =1
    f ( k + 1) = 1 +
    2 n nn + k + 1
    f ( k + 1) = f ( k )
    n + kn + kf ( k ) = f (1)
    n + 1
    4 n
    And note that f (1) = 2 so f ( n ) = and lim f ( n ) = 4.
    n →∞
    n +1
    Therefore adding the first turn, the expected value is 5.
    Solution 2 (calculus):
    We let f ( x ) be the expected value with length x uncolored. Like above, lim f ( x ) = 2.
    x → 0
    Similarly we have the recursion
    ∫
    1 xf ( x ) = 1 + ( − x ) f ( x ) + 2 f ( y ) dy
    ′ ′ ′102
    f ( x ) = 0 + f ( x ) − f ( x ) − xf ( x ) + 2 f ( x )
    ′2
    f ( x ) 1
    1=
    f ( x )
    x +
    1 12
    And solving yields f ( x ) = c ( + x ) and since lim f ( x ) = 2, c = 4. So f ( x ) = 2 + 4 x and f ( ) = 4.
    x → 0
    2 2
    Therefore adding the first turn, our expected value is 5.
    °