HMMT 二月 2013 · 冲刺赛 · 第 32 题
HMMT February 2013 — Guts Round — Problem 32
题目详情
- [ 20 ] For an even 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 , and places 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 shifts the unstuck stones in the following manner: • He picks an unstuck stone uniformly at random and then flips a fair coin. • If the coin came up heads, he then moves that stone and every stone in the largest contiguous set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one 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. k Evaluate p − p + p − . . . + p − p + p n − 1 n − 2 n − 3 3 2 1 p + p + p + . . . + p + p + p n − 1 n − 2 n − 3 3 2 1 in terms of n . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT 2013, 16 FEBRUARY 2013 — GUTS ROUND Organization Team Team ID# 25 24 23 2 1
解析
- [ 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 , and places 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 shifts the 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 set containing that stone one point to the left. If the coin came up tails, he moves every stone in that set one 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. k Evaluate p − p + p − . . . + p − p + p n − 1 n − 2 n − 3 3 2 1 p + p + p + . . . + p + p + p n − 1 n − 2 n − 3 3 2 1 in terms of n . 1 Answer: After we have selected the positions of the initial n stones, we number their n − 1 positions: a < a < . . . < a . The conditions on how we move the stones imply that the expected 1 2 n value of ( a − a ) after t minutes is still equal to a − a . In addition, if b is the final position of the i j i j i i 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 , the i +1 i +1 i ( )( ) j 2 n − j − g number of spaces before a of g · , so we get i i − 1 n − i +1 ( )( ) ∑ ∑ 1 j 2 n − j − g ( ) g · 2 n +1 i − 1 n − i − 1 n g j ( )( ) ( ) ∑ 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 i j i − 1 n − i − 1 n − 1 1 so p is constant for all i 6 = 0 , n . It follows that the answer is . i n − 1 25 24 23 2 1