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 "2018 AIME II Problems/Problem 10"

(→‎Solution2)
(→‎Solution2)
Line 39: Line 39:
 
==Solution2==
 
==Solution2==
  
−
We can do some case work about the special points of function <math>f</math> for <math>x\in\{1,2,3,4,5\}</math>. Let <math>x</math>, <math>y</math> and <math>z</math> be three different elements in set <math>\{1,2,3,4,5\}</math>. There must be an element <math>k</math> in set <math>\{1,2,3,4,5\}</math> satisfies <math>f(k)=k</math>, and we call the point <math>(k,k)</math> on function <math>f</math> is a "Good Point" (Actually its academic name is "fixed-point"). The only thing we need to consider is the "steps" to get  "Good Points". Notice that the "steps" must less than <math>3</math> because the highest iterations of function <math>f</math> is <math>3</math>. Now we can classify <math>3</math> cases of “Good points” of <math>f</math>.
+
We can do some case work about the special points of functions <math>f</math> for <math>x\in\{1,2,3,4,5\}</math>. Let <math>x</math>, <math>y</math> and <math>z</math> be three different elements in set <math>\{1,2,3,4,5\}</math>. There must be elements such like <math>k</math> in set <math>\{1,2,3,4,5\}</math> satisfies <math>f(k)=k</math>, and we call the points such like <math>(k,k)</math> on functions <math>f</math> are "Good Points" (Actually its academic name is "fixed-points"). The only thing we need to consider is the "steps" to get  "Good Points". Notice that the "steps" must less than <math>3</math> because the highest iterations of function <math>f</math> is <math>3</math>. Now we can classify <math>3</math> cases of “Good points” of <math>f</math>.
  
 
<math>\textbf{Case 1:}</math> One "step" to "Good Points": Assume that <math>f(x)=x</math>, then we get <math>f(f(x))=f(x)=x</math>, and <math>f(f(f(x)))=f(f(x))=f(x)=x</math>, so <math>f(f(f(x)))=f(f(x))</math>.
 
<math>\textbf{Case 1:}</math> One "step" to "Good Points": Assume that <math>f(x)=x</math>, then we get <math>f(f(x))=f(x)=x</math>, and <math>f(f(f(x)))=f(f(x))=f(x)=x</math>, so <math>f(f(f(x)))=f(f(x))</math>.
Line 47: Line 47:
 
<math>\textbf{Case 3:}</math> Three "steps" to "Good Points": Assume that <math>f(x)=y</math>, <math>f(y)=z</math> and <math>f(z)=z</math>, then we get <math>f(f(x))=f(y)=z</math>, and <math>f(f(f(x)))=f(f(y))=f(z)=z</math>, so <math>f(f(f(x)))=f(f(x))</math>.
 
<math>\textbf{Case 3:}</math> Three "steps" to "Good Points": Assume that <math>f(x)=y</math>, <math>f(y)=z</math> and <math>f(z)=z</math>, then we get <math>f(f(x))=f(y)=z</math>, and <math>f(f(f(x)))=f(f(y))=f(z)=z</math>, so <math>f(f(f(x)))=f(f(x))</math>.
  
−
Divide set <math>\{1,2,3,4,5\}</math> into three parts which satisfy these three cases, respectively. Let the first part has <math>a</math> elements, the second part has <math>b</math> elements and the third part has <math>c</math> elements, it is easy to see that <math>a+b+c=5</math>. First, there are <math>\binom{5}{a}</math> ways to select <math>x</math> for Case 1. Second, we have <math>\binom{5-a}{b}</math> ways to select <math>x</math> for Case 2. After that we map all elements that satisfy Case 2 to Case 1, and the total number of ways of this operation is <math>a^b</math>. Finally, we map all the elements that satisfy Case 3 to Case 2, and the total number of ways of this operation is <math>b^c</math>. As a result, the number of such function <math>f</math> can be represented in an algebraic expression contains <math>a</math>, <math>b</math> and <math>c</math>: <math>\boxed{\binom{5}{a}\cdot \binom{5-a}{b}\cdot a^b\cdot b^c}</math>
+
Divide set <math>\{1,2,3,4,5\}</math> into three parts which satisfy these three cases, respectively. Let the first part has <math>a</math> elements, the second part has <math>b</math> elements and the third part has <math>c</math> elements, it is easy to see that <math>a+b+c=5</math>. First, there are <math>\binom{5}{a}</math> ways to select <math>x</math> for Case 1. Second, we have <math>\binom{5-a}{b}</math> ways to select <math>x</math> for Case 2. After that we map all elements that satisfy Case 2 to Case 1, and the total number of ways of this operation is <math>a^b</math>. Finally, we map all the elements that satisfy Case 3 to Case 2, and the total number of ways of this operation is <math>b^c</math>. As a result, the number of such functions <math>f</math> can be represented in an algebraic expression contains <math>a</math>, <math>b</math> and <math>c</math>: <math>\boxed{\binom{5}{a}\cdot \binom{5-a}{b}\cdot a^b\cdot b^c}</math>
  
−
Now it's time to talk about the value of <math>a</math>, <math>b</math> and <math>c</math>:
+
Now it's time to consider about the different values of <math>a</math>, <math>b</math> and <math>c</math> and the total number of functions <math>f</math> satisfy these values of <math>a</math>, <math>b</math> and <math>c</math>:
  
 
For <math>a=5</math>, <math>b=0</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{5}=1</math>
 
For <math>a=5</math>, <math>b=0</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{5}=1</math>

Revision as of 10:01, 7 July 2018

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

Solution2

We can do some case work about the special points of functions $f$ for $x\in\{1,2,3,4,5\}$. Let $x$, $y$ and $z$ be three different elements in set $\{1,2,3,4,5\}$. There must be elements such like $k$ in set $\{1,2,3,4,5\}$ satisfies $f(k)=k$, and we call the points such like $(k,k)$ on functions $f$ are "Good Points" (Actually its academic name is "fixed-points"). The only thing we need to consider is the "steps" to get "Good Points". Notice that the "steps" must less than $3$ because the highest iterations of function $f$ is $3$. Now we can classify $3$ cases of “Good points” of $f$.

$\textbf{Case 1:}$ One "step" to "Good Points": Assume that $f(x)=x$, then we get $f(f(x))=f(x)=x$, and $f(f(f(x)))=f(f(x))=f(x)=x$, so $f(f(f(x)))=f(f(x))$.

$\textbf{Case 2:}$ Two "steps" to "Good Points": Assume that $f(x)=y$ and $f(y)=y$, then we get $f(f(x))=f(y)=y$, and $f(f(f(x)))=f(f(y))=f(y)=y$, so $f(f(f(x)))=f(f(x))$.

$\textbf{Case 3:}$ Three "steps" to "Good Points": Assume that $f(x)=y$, $f(y)=z$ and $f(z)=z$, then we get $f(f(x))=f(y)=z$, and $f(f(f(x)))=f(f(y))=f(z)=z$, so $f(f(f(x)))=f(f(x))$.

Divide set $\{1,2,3,4,5\}$ into three parts which satisfy these three cases, respectively. Let the first part has $a$ elements, the second part has $b$ elements and the third part has $c$ elements, it is easy to see that $a+b+c=5$. First, there are $\binom{5}{a}$ ways to select $x$ for Case 1. Second, we have $\binom{5-a}{b}$ ways to select $x$ for Case 2. After that we map all elements that satisfy Case 2 to Case 1, and the total number of ways of this operation is $a^b$. Finally, we map all the elements that satisfy Case 3 to Case 2, and the total number of ways of this operation is $b^c$. As a result, the number of such functions $f$ can be represented in an algebraic expression contains $a$, $b$ and $c$: $\boxed{\binom{5}{a}\cdot \binom{5-a}{b}\cdot a^b\cdot b^c}$

Now it's time to consider about the different values of $a$, $b$ and $c$ and the total number of functions $f$ satisfy these values of $a$, $b$ and $c$:

For $a=5$, $b=0$ and $c=0$, the number of $f$ is $\binom{5}{5}=1$

For $a=4$, $b=1$ and $c=0$, the number of $f$ is $\binom{5}{4}\cdot \binom{1}{1}\cdot 4^1\cdot 1^0=20$

For $a=3$, $b=1$ and $c=1$, the number of $f$ is $\binom{5}{3}\cdot \binom{2}{1}\cdot 3^1\cdot 1^1=60$

For $a=3$, $b=2$ and $c=0$, the number of $f$ is $\binom{5}{3}\cdot \binom{2}{2}\cdot 3^2\cdot 2^0=90$

For $a=2$, $b=1$ and $c=2$, the number of $f$ is $\binom{5}{2}\cdot \binom{3}{1}\cdot 2^1\cdot 1^2=60$

For $a=2$, $b=2$ and $c=1$, the number of $f$ is $\binom{5}{2}\cdot \binom{3}{2}\cdot 2^2\cdot 2^1=240$

For $a=2$, $b=3$ and $c=0$, the number of $f$ is $\binom{5}{2}\cdot \binom{3}{3}\cdot 2^3\cdot 3^0=80$

For $a=1$, $b=1$ and $c=3$, the number of $f$ is $\binom{5}{1}\cdot \binom{4}{1}\cdot 1^1\cdot 1^3=20$

For $a=1$, $b=2$ and $c=2$, the number of $f$ is $\binom{5}{1}\cdot \binom{4}{2}\cdot 1^2\cdot 2^2=120$

For $a=1$, $b=3$ and $c=1$, the number of $f$ is $\binom{5}{1}\cdot \binom{4}{3}\cdot 1^3\cdot 3^1=60$

For $a=1$, $b=4$ and $c=0$, the number of $f$ is $\binom{5}{1}\cdot \binom{4}{4}\cdot 1^4\cdot 4^0=5$

Finally, we get the total number of function $f$, the number is $1+20+60+90+60+240+80+20+120+60+5=\boxed{756}$

~Solution by FYC

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_II_Problems/Problem_10&oldid=95992"