HMMT 二月 2022 · 冲刺赛 · 第 20 题
HMMT February 2022 — Guts Round — Problem 20
题目详情
- [11] Let π be a uniformly random permutation of the set { 1 , 2 , . . . , 100 } . The probability that π (20) = 20 a 21 and π (21) = 21 can be expressed as , where a and b are relatively prime positive integers. Compute b k 100 a + b . (Here, π means π iterated k times.) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . HMMT February 2022, February 19, 2022 — GUTS ROUND Organization Team Team ID#
解析
- [11] Let π be a uniformly random permutation of the set { 1 , 2 , . . . , 100 } . The probability that π (20) = a 21 20 and π (21) = 21 can be expressed as , where a and b are relatively prime positive integers. b k Compute 100 a + b . (Here, π means π iterated k times.) Proposed by: Sean Li Answer: 1025 m Solution: We look at the cycles formed by π . Let ord ( n ) denote the smallest m such that π ( n ) = n . π In particular, the condition implies that ord (20) | 20 and ord (21) | 21 . π π Claim 1. 20 and 21 cannot be in the same cycle. Proof. If 20 and 21 were in the same cycle, then x = ord (20) = ord (21) for some x . Then x > 1 π π since the cycle contains both 20 and 21, but x | 20 , x | 21 implies x = 1, a contradiction. Claim 2. The probability that a = ord (20) , b = ord (21) for some fixed a, b such that a + b ≤ 100 is π π 1 . 99 · 100 Proof. We can just count these permutations. We first choose a − 1 elements of [100] \ { 20 , 21 } to be in the cycle of 20, then we similarly choose b − 1 to be in the cycle of 21. We then have ( a − 1)! ways to reorder within the cycle of 20, ( b − 1)! ways to reorder within the cycle of 21, and (100 − a − b )! ways to permute the remaining elements. The total number of ways is just 98! · ( a − 1)!( b − 1)!(100 − a − b )! = 98! , ( a − 1)!( b − 1)!(100 − a − b )! 98! 1 so the probability this happens is just = . 100! 9900 Now, since ord (20) | 20 and ord (21) | 21, we have 6 possible values for ord (20) and 4 for ord (21), π π π π 6 · 4 2 so in total we have a = probability that the condition is satisfied. 9900 825