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

Page

Toolbox

Search

Mock AIME 2 2010 Problems/Problem 7