Maths Olympiad Prep

Library / /435 of 860

Combinatorics Difficulty 5.2 AIME, harder Find the answer

Let S={1,2,,9}S=\{1,2, \ldots, 9\}. Compute the number of functions f:SSf: S \rightarrow S such that, for all sS,f(f(f(s)))=ss \in S, f(f(f(s)))=s and f(s)sf(s)-s is not divisible by 3.

A number or a short expression. Spacing and $ signs are ignored.

Solution

Since f(f(f(s)))=sf(f(f(s)))=s for all sSs \in S, each cycle in the cycle decomposition of ff must have length 1 or 3. Also, since f(s)≢smod3f(s) \not \equiv s \bmod 3 for all sSs \in S, each cycle cannot contain two elements a,ba, b such that a=bmod3a=b \bmod 3. Hence each cycle has exactly three elements, one from each of residue classes mod 3. In particular, 1,4,71,4,7 belong to distinct cycles. There are 636 \cdot 3 ways to choose two other numbers in the cycle containing 1. Then, there are 424 \cdot 2 ways to choose two other numbers in the cycle containing 4. Finally, there are 212 \cdot 1 ways to choose two other numbers in the cycle containing 7. Hence the desired number of functions ff is 634221=2886 \cdot 3 \cdot 4 \cdot 2 \cdot 2 \cdot 1=288.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.