Maths Olympiad Prep

Library / /304 of 740

Algebra Difficulty 4.9 AIME Prove it United States

Problem:

Compute the number of functions f:{1,2,,9}{1,2,,9}f:\{1,2, \ldots, 9\} \rightarrow \{1,2, \ldots, 9\} which satisfy f(f(f(f(f(x)))))=xf(f(f(f(f(x))))) = x for each x{1,2,,9}x \in \{1,2, \ldots, 9\}.

Solution

Solution:

All cycle lengths in the permutation must divide 55, which is a prime number. Either f(x)=xf(x) = x for all xx, or there exists exactly one permutation cycle of length 55. In the latter case, there are (95)\binom{9}{5} ways to choose which numbers are in the cycle and 4!4! ways to create the cycle. The answer is thus 1+(95)4!=30251 + \binom{9}{5} \cdot 4! = 3025.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.