返回题库

HMMT 十一月 2017 · 冲刺赛 · 第 28 题

HMMT November 2017 — Guts Round — Problem 28

专题
Contest Math / 竞赛数学
难度
L3
来源
HMMT

题目详情

英文原题

  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 } .
    x x 2
    n − 22
    n − 1
解析

英文解析

  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