HMMT 二月 2021 · COMB 赛 · 第 4 题

HMMT February 2021 — COMB Round — Problem 4

Let S = { 1 , 2 , . . . , 9 } . Compute the number of functions f : S → S such that, for all s ∈ S , f ( f ( f ( s ))) = s and f ( s ) − s is not divisible by 3.

解析

Let S = { 1 , 2 , . . . , 9 } . Compute the number of functions f : S → S such that, for all s ∈ S , f ( f ( f ( s ))) = s and f ( s ) − s is not divisible by 3. Proposed by: James Lin Answer: 288 Solution: Since f ( f ( f ( s ))) = s for all s ∈ S, each cycle in the cycle decomposition of f must have length 1 or 3 . Also, since f ( s ) 6 ≡ s mod 3 for all s ∈ S , each cycle cannot contain two elements a, b such that a = b mod 3 . Hence each cycle has exactly three elements, one from each of residue classes mod 3. In particular, 1 , 4 , 7 belong to distinct cycles. There are 6 · 3 ways to choose two other numbers in the cycle containing 1 . Then, there are 4 · 2 ways to choose two other numbers in the cycle containing 4 . Finally, there are 2 · 1 ways to choose two other numbers in the cycle containing 7. Hence the desired number of functions f is 6 · 3 · 4 · 2 · 2 · 1 = 288 .