2018 AIME II Problems/Problem 10

Problem

Find the number of functions $f(x)$ from $\{1, 2, 3, 4, 5\}$ to $\{1, 2, 3, 4, 5\}$ that satisfy $f(f(x)) = f(f(f(x)))$ for all $x$ in $\{1, 2, 3, 4, 5\}$ .

Solution

We do casework on the number of fixed points of $f$ , that is, the number of $x\in\{1,2,3,4,5\}$ such that $f(x)=x$ . We know that at least one such $x$ exists, namely $x=f(f(1))$ .

$\textbf{Case 1: one fixed point.}$
There are five ways to choose the fixed point. WLOG let the fixed point be $1$ . Then at least one of $2,3,4,5$ must map onto $1$ , the only fixed point.
Suppose exactly one of these values maps to $1$ ; there are four ways to choose such a value. WLOG let it be $2$ . Then all of $3,4,5$ must map to $2$ in order to be mapped to $1$ in the next iteration. There are $4$ solutions in this case.
Suppose exactly two of these values map to $1$ ; there are $\binom 4 2=6$ ways to choose such values. WLOG let them be $2$ and $3$ . Then $4$ and $5$ must map to one of $2$ and $3$ , where there are $2^2=4$ ways to do so. Therefore there are $6\cdot 4=24$ solutions in this case.
Suppose exactly three of these values map to $1$ ; there are $\binom 4 3=4$ ways to choose such values. WLOG let them be $2$ , $3$ , and $4$ . Then $5$ must map to one of $2$ , $3$ , and $4$ , where there are $3$ solutions. Therefore there are $4\cdot 3=12$ solutions in this case.
Suppose exactly four of these values map to $1$ . Then everything maps to $1$ and there is $1$ solution in this case.
Therefore there are $5\cdot(4+24+12+1)=205$ solutions in Case 1.

$\textbf{Case 2: two fixed points.}$
There are $\binom 5 2=10$ ways to choose the fixed points. WLOG let them be $1$ and $2$ . Then at least one of $3,4,5$ must map onto $1$ or $2$ .
Suppose exactly one of these values maps to $1$ or $2$ ; there are three ways to choose this value, and two ways to choose the value it maps to. WLOG let it be $3$ . Then both $4$ and $5$ must map to $3$ , for a total of $3\cdot 2=6$ solutions in this case.
Suppose exactly two of these values map to $1$ or $2$ ; there are $\binom 3 2=3$ ways to choose these values, and $2^2=4$ ways to choose the values they map to. WLOG let them be $3$ and $4$ . Then $5$ must map to one of $3$ and $4$ , for two possible choices. Therefore there are $3\cdot 2^2\cdot 2=24$ solutions in this case.
Suppose exactly three of these values map to $1$ or $2$ ; then everything maps to $1$ or $2$ and there are $2^3=8$ solutions in this case.
Therefore there are $10\cdot(6+24+8)=380$ solutions in Case 2.

$\textbf{Case 3: three fixed points.}$
There are $\binom 5 3=10$ ways to choose the fixed points. WLOG let them be $1$ , $2$ , and $3$ . Then at least one of $4$ and $5$ must map onto $1$ , $2$ , or $3$ .
Suppose exactly one of these values map to $1$ , $2$ , or $3$ ; there are two ways to choose this value, and three ways to choose the value is maps to. WLOG let it be $4$ . Then $5$ must map to $4$ , for a total of $2\cdot 3=6$ solutions in this case.
Suppose exactly two of these values map to $1$ , $2$ , or $3$ ; then everything maps to $1$ , $2$ , or $3$ , and there are $3^2=9$ solutions in this case.
Therefore there are $10\cdot(6+9)=150$ solutions in Case 3.

$\textbf{Case 4: four fixed points.}$
There are $\binom 5 4=5$ ways to choose the fixed points. WLOG let them to $1$ , $2$ , $3$ , and $4$ . Then $5$ must map to one of these values, for a total of $5\cdot 4=20$ solutions in Case 4.

$\textbf{Case 5: five fixed points.}$
Since everything is a fixed point, there is only one solution in Case 5.

Therefore there are a total of $205+380+150+20+1=\boxed{756}$ functions that satisfy the problem condition.

~Solution by ghghghghghghghgh

2018 AIME II (Problems • Answer Key • Resources)
Preceded by Problem 9	Followed by Problem 11
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2018 AIME II Problems/Problem 10

Problem

Solution