HMMT 二月 2014 · 冲刺赛 · 第 29 题
HMMT February 2014 — Guts Round — Problem 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 2 [0 , 1] uniformly at 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?
解析
- [ 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] uniformly at 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 value of 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 the expected value of the number of turns we need if there are k white points left. So we must calculate f ( 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 ∑ k n + k f ( i ) i =1 f ( k + 1) = 1 + 2 n n n + k + 1 f ( k + 1) = f ( k ) n + k n + k f ( 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 ∫ x 1 f ( x ) = 1 + ( − x ) f ( x ) + 2 f ( y ) dy 2 0 1 ′ ′ ′ f ( x ) = 0 + f ( x ) − f ( x ) − xf ( x ) + 2 f ( x ) 2 ′ f ( x ) 1 = 1 f ( x ) x + 2 1 1 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. ◦