Mock AIME 2 2010 Problems/Problem 7

As the functions map 1,2,3,4,5 to itself,, the condition reduces to f(x)=x, which counts as 1 function.


Few Quick SideNotes:

This problem actually also appeared on the 2011 HMMT and the 2018 AIME II.

However, here is [b]the general approach[/b] on how to solve it for those interested and for questions similar to this one. :)

First of all, if we let $u = f(f(x)$ in the equation $f(f(f(x))) = f(f(x))$, we get that $f(u) = u$.

Therefore, there must be at least one $u \in \{1,2,3,4,5 \}$ such that $f(u) = u$. So we now do casework on the number of values of $u \in \{1,2,3,4,5 \}$ are such that $f(u) = u$. :)

Case 1: One Value Of u for which that is true Then there are 5 ways to choose one number for $u$ from $\{1,2,3,4,5 \}.$ So let's assume $u = 1$ and then multiply by $5$ at the very end of this case. Then $u = f(f(x)) = 1$ for $x \in \{ 2,3,4,5 \}.$ Now we take casework on the number of numbers in the set $\{2,3,4,5 \}$ for which $f(x) = 1$.

If there is only one number from that set such that $f(x) = 1$, there are only 4 ways to choose that number (so just assume we pick 2 to be that number), then since $f(3), f(4), f(5) \not = 1,$ then $f(3),f(4), f(5) = 2$ since $2$ is the only other value of $x$ for which $f(x) = 1$, so this produces $4 \cdot 1^3 = 4$ cases as such.

If there are $2$ numbers from the set $\{2,3,4,5 \}$ such that $f(x) = 1$, then there are $\dbinom{4}{2} = 6$ ways to choose those $2$ numbers. (This time we will assume that we pick $2,3$, and multiply by $6$ at the end.) Then since $2$ and $3$ are the only other values of $x$ besides $x=1$ such that $f(x) = 1$, we know that $f(4)$ and $f(5)$ cannot equal $1$, so $f(4)$ and $f(5)$ can each be either $2,3.$ So the total number of cases for this subcase is $\dbinom{4}{2} \cdot 2^2$.

If there are $3$ numbers from the set $\{2,3,4,5 \}$ such that $f(x) = 1$, then there are $\dbinom{4}{3} = 4$ ways to choose those $3$ numbers. (This time we will assume that we pick $2,3,4$, and multiply by $4$ at the end.) Then since $2,3,4$ are the only other values of $x$ besides $1$ such that $f(x) = 1$, $f(5) \not = 1$, so $f(5)$ can either be $2,3,$ or $4$. This gives us $4 \cdot 3 = 12$ cases.

If there are $4$ numbers from the set $\{2,3,4,5 \}$ such that $f(x) = 1$, then there is only 1 way to do that. XD

To be honest, the rest of the cases should be pretty similar to the first case, so I will let the aops users who visit this problem's solution think about it themselves and connect the dots for the remaining cases. :)

Case 2: Two Values Of u for which that is true

Case 3: Three Values Of u for which that is true

Case 4: Four Values Of u for which that is true

Case 5: Five Values Of u for which that is true


Hope this helps! :) ~Professor-Mom