HMMT 十一月 2017 · 冲刺赛 · 第 28 题
HMMT November 2017 — Guts Round — Problem 28
题目详情
英文原题
- [ 19 ] Compute the number of functions f : { 1 , 2 , . . . , 9 } → { 1 , 2 , . . . , 9 } which satisfy f ( f ( f ( f ( f ( x ))))) =
x for each x ∈ { 1 , 2 , . . . , 9 } .
x x 2
n − 22
n − 1
解析
英文解析
- [ 19 ] Compute the number of functions f : { 1 , 2 , . . . , 9 } → { 1 , 2 , . . . , 9 } which satisfy f ( f ( f ( f ( f ( x ))))) =
x for each x ∈ { 1 , 2 , . . . , 9 } .
Proposed by: Evan Chen
Answer: 3025
All cycles lengths in the permutation must divide 5, which is a prime number. Either f ( x ) = x for all x,
( )
or there exists exactly one permutation cycle of length 5. In the latter case, there are ways to choose 9
( )5
which numbers are in the cycle and 4! ways to create the cycle. The answer is thus 1 + · 4! = 3025 .9
x x 25
n − 2
n − 1 2