HMMT 二月 2015 · COMB 赛 · 第 10 题
HMMT February 2015 — COMB Round — Problem 10
题目详情
- A group of friends, numbered 1 , 2 , 3 , . . . , 16, take turns picking random numbers. Person 1 picks a number 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 probability that the 16 numbers picked are strictly increasing?
解析
- A group of friends, numbered 1 , 2 , 3 , . . . , 16, take turns picking random numbers. Person 1 picks a number 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 probability that the 16 numbers picked are strictly increasing? 15 17 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 ). i 1 16 A cyclic shifts argument shows that “ ” of the increasing sequences ( x , . . . , x ) in [0 , 17] work 1 16 17 16 1 1 17 (i.e. have x ∈ [0 , i ] for all i ), so contribute volume . Explicitly, the cyclic shift we’re using is i 17 16! T : ( x , . . . , x ) 7 → ( x − x , . . . , x − x , C − x ) C 1 16 2 1 16 1 1 16 for C = 17 (though it’s the same for any C > 0), which sends increasing sequences in [0 , C ] to 1 16 increasing sequences in [0 , C ] . The “ ” essentially follows from the fact that T has period 17, and 17 2 3 almost every T -orbit (of 17 (increasing) sequences) contains exactly 1 working sequence . 4 But to be more rigorous, we still need some more justification. The volume contribution of permitted sequences (i.e. a ∈ [0 , i ] for all i ; those under consideration in i 16 the first place) ( a , . . . , a ) ∈ [0 , 17] is 16!, so based on the previous paragraph, our final probability 1 16 15 17 is . 2 16! Solution 2. Here we present a discrete version of the previous solution. To do this, we consider several related events. 16 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 ). • 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 afore- mentioned box. When Z satisfies this condition, Z is known as a parking function . 1 If we wanted to be completely rigorous, we’d want to also show that the set of such sequences is measurable . However, our sets here are simple enough that this is not a major concern. 2 i.e. “outside a set of measure 0” 3 Try to visualize this yourself! Compare the “exactly 1 of 17” with the discrete solutions below. 16 17 4 We’re using a symmetry/“bijection-of-integrals” argument here (to equate 17 integrals with sum ), so we need to be a 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 way 17 to check this is by taking a Jacobian (determinant); more conceptually, since T = Id, and T is affine (so the Jacobian is constant), we should be able to avoid direct computation by using the chain rule. Alternatively, more “combinatorially”, it should 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, just as 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 ) 16 Given a 16-tuple Z from { 1 , 2 , . . . , 17 } , let Z + n (for integers n ) be the 16-tuple formed by adding 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 a parking function. 1 1 16! First, assuming this claim, it easily follows that P ( D ) = . Substituting P ( A ) = , P ( B ) = 16 17 16! 17 15 17 into () gives P ( A | B ) = . It now remains to prove the claim. 2 16! 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 given by the i th coordinate of Z . If this spot is occupied, that car parks in the closest unoccupied spot in the clockwise direction. Because there are only 16 cars, each car will be able to park, and exactly one spot will be left. Suppose that number 17 is left. For any integer n (1 ≤ n ≤ 16), the n cars that ended up parking in spots 1 through n must have corresponded to coordinates at most n . (If not, then the closest spot in the clockwise direction would have to be before spot 17 and greater than n , a contradiction.) It follows that 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 cars does not park in spots 1 through n − 1. Consider the first car to do so. It either parked in spot n , or skipped over it because spot n was occupied. Therefore spot n is occupied at the end. This is true for all 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 (assuming that 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, its empty 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 we i i i have 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 j 1 admissible sequence b , b , . . . , b , there is the probability that the problem condition holds, 1 2 16 c ! c ! ··· c ! 1 2 16 1 since if c numbers are picked uniformly and randomly in the interval [ i − 1 , i ], then there is chance i c ! i of them being in an increasing order. Thus the answer we are looking for is ( ) ∑ ∑ 1 1 1 c + · · · + c 1 16 = . 2 16! c ! c ! · · · c ! 16! c , c , . . . , c 1 2 16 1 2 16 b ≤ i b ≤ i i i b ≤···≤ b b ≤···≤ b 1 16 1 16 Thus it suffices to prove that ( ) ∑ c + · · · + c 1 16 15 = 17 . c , c , . . . , c 1 2 16 b ≤ i i b ≤···≤ 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 equal 5 to n . In other words, this counts the number of parking functions of length 16. Since the number 1 n n − 1 of parking functions of length n is · ( n + 1) = ( n + 1) (as proven for n = 16 in the previous n +1 solution), we obtain the desired result. 5 See http://www-math.mit.edu/~rstan/transparencies/parking.pdf . Combinatorics