HMMT 二月 2022 · COMB 赛 · 第 9 题
HMMT February 2022 — COMB Round — Problem 9
题目详情
- Consider permutations ( a , a , . . . , a ) of (0 , 1 , . . . , 2022) such that 0 1 2022 • a = 625, 2022 625 i • for each 0 ≤ i ≤ 2022, a ≥ , i 2022 • for each 0 ≤ i ≤ 2022, { a , . . . , a } is a set of consecutive integers (in some order). i 2022 a ! The number of such permutations can be written as for positive integers a, b, c , where b > c and a b ! c ! is minimal. Compute 100 a + 10 b + c .
解析
- Consider permutations ( a , a , . . . , a ) of (0 , 1 , . . . , 2022) such that 0 1 2022 • a = 625, 2022 625 i • for each 0 ≤ i ≤ 2022, a ≥ , i 2022 • for each 0 ≤ i ≤ 2022, { a , . . . , a } is a set of consecutive integers (in some order). i 2022 a ! The number of such permutations can be written as for positive integers a, b, c , where b > c and a b ! c ! is minimal. Compute 100 a + 10 b + c . Proposed by: Milan Haiman Answer: 216695 Solution: Ignore the second condition for now. The permutations we seek are in bijection with the 2022 ways to choose 625 indices i ≤ 2021 so that a < 625. These are in bijection with up-right lattice i 625 paths from (0 , 0) to (625 , 1397) in the following way: a step ( i, j ) → ( i + 1 , j ) indicates that a = i , i + j while a step ( i, j ) → ( i, j + 1) indicates that a = 2022 − j . i + j Under this bijection, the second condition now becomes: for every right step ( i, j ) → ( i + 1 , j ), we have 625 1397 i ≥ ( i + j ), which is equivalent to j ≤ i . In other words, we want to count the number of paths 2022 625 1397 from (0 , 0) to (625 , 1397) that stay under the line y = x . 625 This can be counted via a standard shifting argument. Given a path from (0 , 0) to (625 , 1397), one can shift it by moving the first step to the end. We claim that exactly one of these cyclic shifts has the 1397 2021! property of lying under the lines y = x . If we can show this, it follows that the answer is , 625 1397!625! since, as gcd(2022 , 625) = 1, all the cyclic shifts are distinct. (It is true that the 2021 is minimal and that, given the numerator, the form of the denominator is unique. However, proving this is a bit annoying so we omit it here.) To see that exactly one cyclic shift lies under the line, imagine extending a path infinitely in both directions in a periodic manner. A cyclic shift corresponds to taking a subset of this path between two points P and Q at distance 2022 along the path. Note that the condition of the path lying below the line corresponds to the infinite path lying below line P Q , so the unique P, Q that satisfy this condition 1397 are those that lie on the highest line of slope that touches the path. Since gcd(2022 , 625) = 1, 625 these points are unique.