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 } . 2 x x 2 n − 2 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, ( ) 9 or there exists exactly one permutation cycle of length 5. In the latter case, there are ways to choose 5 ( ) 9 which numbers are in the cycle and 4! ways to create the cycle. The answer is thus 1 + · 4! = 3025 . 5 2 x x n − 2 n − 1 2