HMMT 二月 2012 · 冲刺赛 · 第 30 题
HMMT February 2012 — Guts Round — Problem 30
题目详情
- [ 19 ] You have a twig of length 1. You repeatedly do the following: select two points on the twig independently and uniformly at random, make cuts on these two points, and keep only the largest piece. After 2012 repetitions, what is the expected length of the remaining piece?
解析
- [ 19 ] You have a twig of length 1. You repeatedly do the following: select two points on the twig independently and uniformly at random, make cuts on these two points, and keep only the largest piece. After 2012 repetitions, what is the expected length of the remaining piece? 2012 Answer: (11 / 18) First let p ( x ) be the probability density of x being the longest length. ∫ ∫ 1 1 Let a be the expected length after n cuts. a = p ( x ) · ( xa ) dx = a xp ( x ) dx = a a . n n n − 1 n − 1 1 n − 1 0 0 n 2012 It follows that a = a , so our answer is ( a ) . We now calculate a . n 1 1 1 1 Let P ( z ) be the probability that the longest section is ≤ z . Clearly P ( z ) = 0 for z ≤ . 3 To simulate making two cuts we pick two random numbers x, y from [0 , 1], and assume without loss of generality that x ≤ y . Then picking two such points is equivalent to picking a point in the top 1 left triangle half of the unit square. This figure has area so our P ( z ) will be double the area where 2 1 1 x ≤ z , y ≥ 1 − z and y − x ≤ z . For ≤ z ≤ the probability is double the area bounded by 3 2 1 2 2 x = z, 1 − z = y, y − x = z . This is 2( (3 z − 1) ) = (3 z − 1) . 2 Guts 1 For ≤ z ≤ 1 this value is double the hexagon bounded by x = 0, y = 1 − z , y = x , x = z , y = 1, 2 2 (1 − z ) 2 y = x + z . The complement of this set, however, is three triangles of area , so P ( z ) = 1 − 3(1 − z ) 2 1 for ≤ z ≤ 1. 2 ∫ ∫ 1 1 ′ ′ Now note that P ( z ) = p ( z ). Therefore by integration by parts a = zp ( z ) dz = zP ( z ) dz = 1 0 0 ∫ 1 1 [ zP ( z ) − P ( z ) dz . This equals 0 0 ∫ 1 ∫ 1 2 2 2 1 − (3 z − 1) dz − 1 − 3(1 − z ) dz 1 1 3 2 3 1 (3 z − 1) 1 1 3 2 = 1 − [ − + [ ( z − 1) 1 1 2 3 9 2 . 1 1 1 1 1 = 1 − − + = + 72 2 8 2 9 11 = 18 11 2012 So the answer is ( ) . 18