Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "Mock AIME 2 2010 Problems/Problem 7"

(Created page with "YEET")
 
 
(4 intermediate revisions by 2 users not shown)
Line 1: Line 1:
−
YEET
+
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 <math>u = f(f(x)</math> in the equation <math>f(f(f(x))) = f(f(x))</math>, we get that <math>f(u) = u</math>.
 +
 
 +
Therefore, there must be at least one <math>u \in \{1,2,3,4,5 \}</math> such that <math>f(u) = u</math>. So we now do casework on the number of values of <math>u \in \{1,2,3,4,5 \}</math> are such that <math>f(u) = u</math>. :)
 +
 
 +
Case 1: One Value Of u for which that is true
 +
Then there are 5 ways to choose one number for <math>u</math> from <math>\{1,2,3,4,5 \}.</math> So let's assume <math>u = 1</math> and then multiply by <math>5</math> at the very end of this case. Then <math>u = f(f(x)) = 1</math> for <math>x \in \{ 2,3,4,5 \}.</math> Now we take casework on the number of numbers in the set <math>\{2,3,4,5 \}</math> for which <math>f(x) = 1</math>.
 +
 
 +
If there is only one number from that set such that <math>f(x) = 1</math>, there are only 4 ways to choose that number (so just assume we pick 2 to be that number), then since <math>f(3), f(4), f(5) \not = 1,</math> then <math>f(3),f(4), f(5) = 2</math> since <math>2</math> is the only other value of <math>x</math> for which <math>f(x) = 1</math>, so this produces <math>4 \cdot 1^3 = 4</math> cases as such.
 +
 
 +
If there are <math>2</math> numbers from the set <math>\{2,3,4,5 \}</math> such that <math>f(x) = 1</math>, then there are <math>\dbinom{4}{2} = 6</math> ways to choose those <math>2</math> numbers. (This time we will assume that we pick <math>2,3</math>, and multiply by <math>6</math> at the end.) Then since <math>2</math> and <math>3</math> are the only other values of <math>x</math> besides <math>x=1</math> such that <math>f(x) = 1</math>, we know that <math>f(4)</math> and <math>f(5)</math> cannot equal <math>1</math>, so <math>f(4)</math> and <math>f(5)</math> can each be either <math>2,3.</math> So the total number of cases for this subcase is <math>\dbinom{4}{2} \cdot 2^2</math>.
 +
 
 +
If there are <math>3</math> numbers from the set <math>\{2,3,4,5 \}</math> such that <math>f(x) = 1</math>, then there are <math>\dbinom{4}{3} = 4</math> ways to choose those <math>3</math> numbers. (This time we will assume that we pick <math>2,3,4</math>, and multiply by <math>4</math> at the end.) Then since <math>2,3,4</math> are the only other values of <math>x</math> besides <math>1</math> such that <math>f(x) = 1</math>, <math>f(5) \not = 1</math>, so <math>f(5)</math> can either be <math>2,3,</math> or <math>4</math>. This gives us <math>4 \cdot 3 = 12</math> cases.
 +
 
 +
If there are <math>4</math> numbers from the set <math>\{2,3,4,5 \}</math>  such that <math>f(x) = 1</math>, 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

Latest revision as of 21:44, 8 December 2020

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 the general approach 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

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Mock_AIME_2_2010_Problems/Problem_7&oldid=139315"