HMMT 二月 2022 · COMB 赛 · 第 6 题
HMMT February 2022 — COMB Round — Problem 6
题目详情
- The numbers 1 , 2 , . . . , 10 are randomly arranged in a circle. Let p be the probability that for every ′ positive integer k < 10, there exists an integer k > k such that there is at most one number between k a ′ and k in the circle. If p can be expressed as for relatively prime positive integers a and b , compute b 100 a + b . 2
解析
- The numbers 1 , 2 , . . . , 10 are randomly arranged in a circle. Let p be the probability that for every ′ positive integer k < 10, there exists an integer k > k such that there is at most one number between k a ′ and k in the circle. If p can be expressed as for relatively prime positive integers a and b , compute b 100 a + b . Proposed by: Akash Das Answer: 1390 Solution: Let n = 10 and call two numbers close if there is at most one number between them and an circular permutation focused if only n is greater than all numbers close to it. Let A be the number n of focused circular permutations of { 1 , 2 , . . . , n } . If n ≥ 5, then there are 2 cases: n − 1 is either one or two positions from n . If n − 1 is one position from n , it is either on its left or right. In this case, one can check a permutation is focused if and only if removing n yields a focused permutation, so there are 2 A permutations in this case. If n − 1 is n − 1 two positions from n , there are n − 2 choices for k , the element that lies between n and n − 1. One can show that this permutation is focused if and only if removing both n and k and relabeling the numbers yields a focused permutation, so there are 2( n − 2) A permutations in this case. Thus, we n − 2 have A = 2 A + 2( n − 2) A . n n − 1 n − 2 If we let p = A / ( n − 1)! the probability that a random circular permutation is focused, then this n n becomes 2 p + 2 p n − 1 n − 2 p = . n n − 1 Since p = p = 1, we may now use this recursion to calculate 3 4 4 3 2 1 13 p = 1 , p = , p = , p = , p = , p = . 5 6 7 8 9 10 5 5 5 4 90 2