返回题库

HMMT 二月 2021 · COMB 赛 · 第 7 题

HMMT February 2021 — COMB Round — Problem 7

专题
Discrete Math / 离散数学
难度
L3
来源
HMMT

题目详情

  1. Let S = { 1 , 2 , . . . , 2021 } , and let F denote the set of functions f : S → S . For a function f ∈ F , let { } 2021 T = f ( s ) : s ∈ S , f 2021 where f ( s ) denotes f ( f ( · · · ( f ( s )) · · · )) with 2021 copies of f . Compute the remainder when ∑ | T | f f ∈F is divided by the prime 2017, where the sum is over all functions f in F .
解析
  1. Let S = { 1 , 2 , . . . , 2021 } , and let F denote the set of functions f : S → S . For a function f ∈ F , let { } 2021 T = f ( s ) : s ∈ S , f 2021 where f ( s ) denotes f ( f ( · · · ( f ( s )) · · · )) with 2021 copies of f . Compute the remainder when ∑ | T | f f ∈F is divided by the prime 2017, where the sum is over all functions f in F . Proposed by: Milan Haiman Answer: 255 k Solution: The key idea is that t ∈ T if and only if f ( t ) = t for some k > 0. To see this, let s ∈ S f and consider 2021 s, f ( s ) , f ( f ( s )) , . . . , f ( s ) . m n This sequence has 2022 terms that are all in S , so we must have a repeat. Suppose f ( s ) = f ( s ) with 2021 2021+ m − n 2021 k 0 ≤ n < m ≤ 2021. Then f ( s ) = f ( s ). In particular, for t = f ( s ), we have f ( t ) = t k 2021 k − 2021 2021 with k = m − n . On the other hand, if f ( t ) = t , then letting s = f ( t ) gives f ( s ) = t . k We will compute the number of f for which f (1) = 1 for some k , and then multiply by 2021. We do this by casework on the minimum possible value of k . 1 2 k − 1 Given k , we just need to choose distinct values in { 2 , . . . , 2021 } for each of f (1) , f (1) , . . . , f (1). 2020! We have ways to do this. For each of the 2021 − k other values with f not yet determined, (2021 − k )! 2021 − k we can do anything we want, giving 2021 choices. So, 2021 ∑ ∑ 2020! 2021 − k | T | = 2021 · 2021 . f (2021 − k )! f ∈F k =1 2021 − k 5 − k Taking this mod 2017, all terms with k > 4 reduce to 0, and 2021 reduces to 4 for k ≤ 4. We are thus left with ∑ [ ] 4 3 2 1 | T | ≡ 4 4 + 3 · 4 + 3 · 2 · 4 + 3 · 2 · 1 · 4 ≡ 255 (mod 2017) . f f ∈F