Maths Olympiad Prep

Library / /61 of 860

Combinatorics Difficulty 4.7 AIME Find the answer

How many functions f:{1,2,3,4,5}{1,2,3,4,5}f:\{1,2,3,4,5\} \rightarrow\{1,2,3,4,5\} satisfy f(f(x))=f(x)f(f(x))=f(x) for all x{1,2,3,4,5}x \in\{1,2,3,4,5\}?

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

Solution

A fixed point of a function ff is an element aa such that f(a)=af(a)=a. The condition is equivalent to the property that ff maps every number to a fixed point. Counting by the number of fixed points of ff, the total number of such functions is k=15(5k)k5k=1(50)+5(14+41)+10(23+32)=1+25+1017=196\begin{aligned} \sum_{k=1}^{5}\binom{5}{k} k^{5-k} & =1 \cdot\left(5^{0}\right)+5 \cdot\left(1^{4}+4^{1}\right)+10 \cdot\left(2^{3}+3^{2}\right) \\ & =1+25+10 \cdot 17 \\ & =196 \end{aligned}

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.