HMMT 二月 2012 · 冲刺赛 · 第 30 题

英文解析

30. [ 19 ] You have a twig of length 1. You repeatedly do the following: select two points on the twigindependently and uniformly at random, make cuts on these two points, and keep only the largestpiece. 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
    Let P ( z ) be the probability that the longest section is ≤ z . Clearly P ( z ) = 0 for z ≤ .11
    To simulate making two cuts we pick two random numbers x, y from [0 , 1], and assume without loss 3
    of generality that x ≤ y . Then picking two such points is equivalent to picking a point in the topleft triangle half of the unit square. This figure has area so our P ( z ) will be double the area where 1
    1 12
    x ≤ z , y ≥ 1 − z and y − x ≤ z . For ≤ z ≤ the probability is double the area bounded by
    3 2
    2 21
    x = z, 1 − z = y, y − x = z . This is 2( (3 z − 1) ) = (3 z − 1) .
    Guts 2
    For ≤ z ≤ 1 this value is double the hexagon bounded by x = 0, y = 1 − z , y = x , x = z , y = 1,1
    (1 − z )22
    y = x + z . The complement of this set, however, is three triangles of area , so P ( z ) = 1 − 3(1 − z )2
    for ≤ z ≤ 1.12
    ∫ ∫2
    1 1
    ′ ′
    Now note that P ( z ) = p ( z ). Therefore by integration by parts a = zp ( z ) dz = z p ( z ) dz =
    0 01
    ∫
    [ z p ( z ) − P ( z ) dz . This equals 11
    ∫ 1 ∫00
    2 221
    1 − (3 z − 1) dz − 1 − 3(1 − z ) dz
    1 1
    3 2
    (3 z − 1) 113
    1 3 = 1 − [ − + [ ( z − 1)2
    3211
    9 2
    .
    1 1 1 1 1 = 1 − − + = +
    72 2 8 2 9 =11
    11 201218
    So the answer is ( ) .
    18