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.

Note: This problem actually also appeared on the 2011 HMMT and the 2018 AIME II. Here is the basic outline for the approach on how to solve it though.

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

Page

Toolbox

Search

Mock AIME 2 2010 Problems/Problem 7