HMMT 二月 2022 · 冲刺赛 · 第 35 题
HMMT February 2022 — Guts Round — Problem 35
题目详情
- [20] A random permutation of { 1 , 2 , . . . , 100 } is given. It is then sorted to obtain the sequence (1 , 2 , . . . , 100) as follows: at each step, two of the numbers which are not in their correct positions are selected at random, and the two numbers are swapped. If s is the expected number of steps (i.e. swaps) required to obtain the sequence (1 , 2 , · · · , 100), then estimate A = ⌊ s ⌋ . An estimate of E earns 1 max(0 , ⌊ 20 − | A − E |⌋ ) points. 2
解析
- [20] A random permutation of { 1 , 2 , . . . , 100 } is given. It is then sorted to obtain the sequence (1 , 2 , . . . , 100) as follows: at each step, two of the numbers which are not in their correct positions are selected at random, and the two numbers are swapped. If s is the expected number of steps (i.e. swaps) required to obtain the sequence (1 , 2 , · · · , 100), then estimate A = ⌊ s ⌋ . An estimate of E earns 1 max(0 , ⌊ 20 − | A − E |⌋ ) points. 2 Proposed by: Sheldon Kieren Tan Answer: 2427 Solution: Let f ( n ) be the expected number of steps if there are n elements out of order. Let’s consider one of these permutations and suppose that a and b are random elements that are out of order. The 1 probability that swapping a and b sends a to the proper place is , and the probability that it sends n − 1 1 b to the proper place is . Thus we can approximate n − 1 2 n − 3 f ( n ) ≈ 1 + f ( n − 1) + f ( n ) . n − 1 n − 1 (The chance that both get sent to the right place decreases the overall probability that the number of fixed points increases, but also decreases the expected number of moves after the swap. These effects largely cancel out.) As a result, we conclude that n − 1 f ( n ) ≈ f ( n − 1) + , 2 n ( n − 1) and since f (0) = 0 we have f ( n ) ≈ . At the beginning, the expected number of elements that 4 99 · 98 are in the right place is 1, so the answer is approximately f (99) ≈ ≈ 2425. This is good enough 4 for 19 points.