HMMT 二月 2015 · COMB 赛 · 第 10 题

英文解析

10. A group of friends, numbered 1 , 2 , 3 , . . . , 16, take turns picking random numbers. Person 1 picks anumber uniformly (at random) in [0 , 1], then person 2 picks a number uniformly (at random) in [0 , 2],
    and so on, with person k picking a number uniformly (at random) in [0 , k ]. What is the probabilitythat the 16 numbers picked are strictly increasing?
    1715
    Answer: Solution 1 (intuitive sketch). If person i picks a , this is basically a continuous
    2 i
    16!
    version of Catalan paths (always y ≤ x ) from (0 , 0) to (17 , 17), with “up-right corners” at the ( i, a ).
    1 i
    A cyclic shifts argument shows that “ ” of the increasing sequences ( x , . . . , x ) in [0 , 17] work 16
    1 16
    1617
    1 1 17
    (i.e. have x ∈ [0 , i ] for all i ), so contribute volume . Explicitly, the cyclic shift we’re using isi
    17 16!
    T : ( x , . . . , x ) 7 → ( x − x , . . . , x − x , C − x )
    C 1 16 2 1 16 1 1
    for C = 17 (though it’s the same for any C > 0), which sends increasing sequences in [0 , C ] to 16
    increasing sequences in [0 , C ] . The “ ” essentially follows from the fact that T has period 17, and 161
    2 317
    almost every T -orbit (of 17 (increasing) sequences) contains exactly 1 working sequence .
    But to be more rigorous, we still need some more justification.4
    The volume contribution of permitted sequences (i.e. a ∈ [0 , i ] for all i ; those under consideration inithe first place) ( a , . . . , a ) ∈ [0 , 17] is 16!, so based on the previous paragraph, our final probability 16
    1 16
    1715
    is .
    16!2
    Solution 2. Here we present a discrete version of the previous solution.
    To do this, we consider several related events.
    Let X be a 16-tuple chosen uniformly and randomly from [0 , 17] (used to define events A, B, C ). Let 16
    Z be a 16-tuple chosen uniformly and randomly from { 1 , 2 , . . . , 17 } (used to define event D ).16
    • A is the event that X ’s coordinates are ordered ascending;
    • B is the event that X lies in the “box” [0 , 1] × · · · × [0 , 16];
    • C is the event that when X ’s coordinates are sorted ascending to form Y (e.g. if X = (1 , 3 . 2 , 3 , 2 , 5 , 6 , . . . , 16)
    then Y = (1 , 2 , 3 , 3 . 2 , 5 , 6 , . . . , 16)), Y lies in the box;
    • D is the event that when Z ’s coordinates are sorted ascending to form W , W lies in the aforementioned box. When Z satisfies this condition, Z is known as a parking function .
    If we wanted to be completely rigorous, we’d want to also show that the set of such sequences is measurable . However, our 1
    sets here are simple enough that this is not a major concern.
    i.e. “outside a set of measure 0”2
    Try to visualize this yourself! Compare the “exactly 1 of 17” with the discrete solutions below.3
    1716
    We’re using a symmetry/“bijection-of-integrals” argument here (to equate 17 integrals with sum ), so we need to be a 4
    16!
    little careful with the bijections. In particular, we must make sure the cyclic shift
    T : ( x , . . . , x ) 7 → ( x − x , . . . , x − x , 17 − x )
    1 16 2 1 16 1 1
    16 2
    is “measure-preserving” on R . (An example of a non-measure-preserving bijection is t 7 → t on [0 , 1].) The standard wayto check this is by taking a Jacobian (determinant); more conceptually, since T = Id, and T is affine (so the Jacobian is 17
    constant), we should be able to avoid direct computation by using the chain rule. Alternatively, more “combinatorially”, itshould also be possible to do so by properly discretizing our space.
    Combinatorics
    We want to find P ( A | B ) because given that X is in B , X has a uniform distribution in the box, justas in the problem. Now note
    P ( A ∩ B ) P ( A ∩ B ) P ( A ) P ( A )
    P ( A | B ) = = = P ( B | A ) .
    P ( B ) P ( A ) P ( B ) P ( B )
    P ( A ∩ C ) P ( A ∩ B )
    1 1
    C is invariant with respect to permutations, so = P ( A | C ) = = . Since P ( A ) = ,
    16! P ( C ) P ( C ) 16!
    P ( A ∩ B )
    we have P ( B | A ) = = P ( C ).
    P ( A )
    Furthermore, P ( C ) = P ( D ) because C only depends on the ceilings of the coordinates. So P ( A | B ) =
    P ( A ) P ( A )
    P ( C ) = P ( D ) . ()
    P ( B ) P ( B )
    Given a 16-tuple Z from { 1 , 2 , . . . , 17 } , let Z + n (for integers n ) be the 16-tuple formed by adding 16
    n to each coordinate and then reducing modulo 17 so that each coordinate lies in [1 , 17].
    Key claim (discrete analog of cyclic shifts argument). Exactly one of Z, Z + 1 , . . . , Z + 16 is aparking function.
    1 1 16!
    First, assuming this claim, it easily follows that P ( D ) = . Substituting P ( A ) = , P ( B ) =
    17 16! 1716
    1715
    into () gives P ( A | B ) = . It now remains to prove the claim.
    16!2
    Proof. Consider the following process.
    Begin with 17 parking spots around a circle, labelled 1 to 17 clockwise and all unoccupied. There are
    16 cars, 1 to 16, and they park one at a time, from 1 to 16. The i th car tries to park in the spot givenby the i th coordinate of Z . If this spot is occupied, that car parks in the closest unoccupied spot inthe clockwise direction. Because there are only 16 cars, each car will be able to park, and exactly onespot will be left.
    Suppose that number 17 is left. For any integer n (1 ≤ n ≤ 16), the n cars that ended up parking inspots 1 through n must have corresponded to coordinates at most n . (If not, then the closest spot inthe clockwise direction would have to be before spot 17 and greater than n , a contradiction.) It followsthat the n th lowest coordinate is at most n and that when Z is sorted, it lies in the box.
    Suppose now that D is true. For any integer n (1 ≤ n ≤ 16), the n th lowest coordinate is at most n ,
    so there are (at least) n cars whose corresponding coordinates are at most n . At least one of these carsdoes not park in spots 1 through n − 1. Consider the first car to do so. It either parked in spot n , orskipped over it because spot n was occupied. Therefore spot n is occupied at the end. This is true forall n not equal to 17, so spot 17 is left.
    It follows that Z is a parking function if and only if spot 17 is left. The same is true for Z +1 (assumingthat the process uses Z + 1 instead of Z ), etc.
    Observe that the process for Z + 1 is exactly that of Z , rotated by 1 spot clockwise. In particular, itsempty spot is one more than that of Z , (where 1 is one more than 17.) It follows that exactly one of
    Z, Z + 1 , . . . , Z + 16 leaves the spot 17, and that exactly one of these is a parking function.
    Solution 3. Suppose that person i picks a number in the interval [ b − 1 , b ] where b ≤ i . Then wei i ihave the condition: b ≤ b ≤ · · · ≤ b . Let c be the number of b ’s such that b = i . Then, for each
    1 2 16 i j jadmissible sequence b , b , . . . , b , there is the probability that the problem condition holds,1
    1 2 16
    c ! c ! ··· c !
    1 2 16
    since if c numbers are picked uniformly and randomly in the interval [ i − 1 , i ], then there is chance 1
    c !iiof them being in an increasing order. Thus the answer we are looking for is
    ( )
    ∑ ∑
    1 1 1 c + · · · + c
    1 16 = .
    16! c ! c ! · · · c ! 16! c , c , . . . , c 2
    1 2 16 1 2 16
    b ≤ i b ≤ ii ib ≤···≤ b b ≤···≤ b
    1 16 1 16
    Thus it suffices to prove that
    ( )
    ∑
    c + · · · + c
    1 16 = 17 .15
    c , c , . . . , c
    1 2 16
    b ≤ iib ≤···≤ b
    1 16
    Combinatorics
    The left hand side counts the number of 16-tuple such that the n th smallest entry is less than or equalto n . In other words, this counts the number of parking functions of length 16. Since the number 5
    n n − 11
    of parking functions of length n is · ( n + 1) = ( n + 1) (as proven for n = 16 in the previousn +1
    solution), we obtain the desired result.
    See http://www-math.mit.edu/~rstan/transparencies/parking.pdf .5
    Combinatorics