PUMaC 2023 · 团队赛 · 第 1 题
PUMaC 2023 — Team Round — Problem 1
题目详情
- Given n ≥ 1, let A denote the set of the first n positive integers. We say that a bijection n f : A → A has a hump at m ∈ A \ { 1 , n } if f ( m ) > f ( m + 1) and f ( m ) > f ( m − 1). We say n n n that f has a hump at 1 if f (1) > f (2), and f has a hump at n if f ( n ) > f ( n − 1). Let P be n the probability that a bijection f : A → A , when selected uniformly at random, has exactly n n one hump. For how many positive integers n ≤ 2020 is P expressible as a unit fraction? n 1 1
解析
- Given n ≥ 1, let A denote the set of the first n positive integers. We say that a bijection n f : A → A has a hump at m ∈ A \ { 1 , n } if f ( m ) > f ( m + 1) and f ( m ) > f ( m − 1). We say n n n that f has a hump at 1 if f (1) > f (2), and f has a hump at n if f ( n ) > f ( n − 1). Let P be n the probability that a bijection f : A → A , when selected uniformly at random, has exactly n n one hump. For how many positive integers n ≤ 2020 is P expressible as a unit fraction? n Proposed by Oliver Thakar Answer: 11 Fix n. Let N ( n, k ) be the number of bijections f : A → A , that has one hump at k, and no n n n − 1 others. (Then, notice that f ( k ) = n. ) I claim that N ( n, k ) = . k − 1 0 I prove this claim by induction on n. For the base case, when n = 1 , we have N (1 , 1) = 1 = . 0 n − 2 Otherwise, assume that N ( n − 1 , k ) = for all k. Then, notice that a bjiection f : A → A n n k − 1 has one hump at k, and no others if and only if f : ( A ∼ { k } ) → A has one hump at n n − 1 either k − 1 or k + 1 . This means: n − 2 n − 2 n − 1 N ( n, k ) = N ( n − 1 , k − 1) + N ( n − 1 , k ) = + = , k − 2 k − 1 k − 1 by our induction hypothesis and a well-known property of binomial coefficients. P n Thus, the total number of bijections f : A → A with exactly one hump is N ( n, k ) = n n k =1 P n − 1 n n − 1 2 n − 1 = 2 . Since the total number of bijections f : A → A is n ! , then P = . n n n k =1 k − 1 n ! r r Letting r be the unique integer such that n = 2 + q where 0 ≤ q < 2 , then the exponent of 2 in n ! is equal to: ∞ r X X n n n ⌊ ⌋ ≤ = n − ≤ n − 1 , j j r 2 2 2 j =1 j =1 r with equality in both places if and only if n = 2 . Therefore, P is expressible as a unit n fraction if and only if n is a power of 2, so the n ≤ 2020 that satisfy this condition are precisely: 1 , 2 , 4 , 8 , 16 , 32 , 64 , 128 , 256 , 512 , 1024 , of which there are 11 . 1 1