PUMaC 2009 · 组合（B 组） · 第 8 题

PUMaC 2009 — Combinatorics (Division B) — Problem 8

We randomly choose 5 distinct positive integers less than or equal to 90. What is the floor of 10 times the expected value of the fourth largest number? 1

解析

We randomly choose 5 distinct positive integers less than or equal to 90. What is the floor of 10 times the expected value of the fourth largest number? ( ) k − 1 Solution. 606. The expected value is 182/3. For any 3 < k < 90, there are (90 − k ) 3 ways in which the fourth largest number is exactly k (3 numbers must be less than k , they can be put on k − 1 positions, one number must be larger than k , it can be put on 90 − k positions). Hence the expected value is ( ) 89 ∑ 1 k − 1 ( ) k (90 − k ) 90 3 5 k =1 2 ( ) ( ) k − 1 k We can simplify the sum as follows. First note that k = 4 so the sum equals 3 4 ( ) ∑ 89 k 4 (90 − k ) . This can be broken up into two parts k =1 4 ( ) ( ) ( ) 89 89 89 ∑ ∑ ∑ k k k 4 (91 − ( k + 1)) = 4 × 91 − 4 ( k + 1) 4 4 4 k =1 k =1 k =1 ( ) ( ) k k +1 As above, we have ( k + 1) = 5 so this equals 4 5 ( ) ( ) 89 89 ∑ ∑ k k + 1 4 × 91 − 4 × 5 4 5 k =1 k =1 Using the known identity ( ) ( ) ( ) ( ) a a + 1 b b + 1

- . . . + = a a a a + 1 the last expression simplifies to ( ) ( ) ( ) 90 91 182 90 4 × 91 − 4 × 5 = 5 6 3 5 To get the expected value, we must divide this by the total number of possibilities, which is ( ) 90 just , and this finishes the solution. 5 Alternative Solution: Consider a regular 91-gon. Choose 6 vertices at random. Then choose one vertex out of the 6, label it with 0, and starting from that vertex label the remaining ones in clockwise direction with 1,2,...,90. Then our problem asks for the expected arclength between the vertex 0 and the 4th chosen vertex. By symmetry, the expected distance between any two consecutive chosen vertices is 91/6, hence our answer is 4 times that: 4 × 91 / 6 = 182 / 3. 3