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"

(→‎Solution 3)
m (→‎Solution 2: ; fix typo)
 
(15 intermediate revisions by 8 users not shown)
Line 5: Line 5:
 
==Solution 1==
 
==Solution 1==
  
−
Just to visualize solution 1. If we list all possible <math>(x,f(x))</math>, from <math>{1,2,3,4,5}</math> to <math>{1,2,3,4,5}</math> in a specific order, we get <math>5*5 = 25</math> different <math>(x,f(x))</math> 's.
+
Just to visualize solution 1. If we list all possible <math>(x,f(x))</math>, from <math>{1,2,3,4,5}</math> to <math>{1,2,3,4,5}</math> in a specific order, we get <math>5 \cdot 5 = 25</math> different <math>(x,f(x))</math> 's.
 
Namely:
 
Namely:
  
−
<math>(1,1) (1,2) (1,3) (1,4) (1,5)
+
<cmath>(1,1) (1,2) (1,3) (1,4) (1,5)</cmath>
−
(2,1) (2,2) (2,3) (2,4) (2,5)  
+
<cmath>(2,1) (2,2) (2,3) (2,4) (2,5)</cmath>
−
(3,1) (3,2) (3,3) (3,4) (3,5)
+
<cmath>(3,1) (3,2) (3,3) (3,4) (3,5)</cmath>
−
(4,1) (4,2) (4,3) (4,4) (4,5)
+
<cmath>(4,1) (4,2) (4,3) (4,4) (4,5)</cmath>
−
(5,1) (5,2) (5,3) (5,4) (5,5)</math>
+
<cmath>(5,1) (5,2) (5,3) (5,4) (5,5)</cmath>
  
 
To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of <math>(x,x)</math> where <math>x\in{1,2,3,4,5}</math> must exist.In this case I rather "go backwards". First fixing <math>5</math> pairs <math>(x,x)</math>, (the diagonal of our table) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{5!}{5!} = 1</math> way. Then fixing <math>4</math> pairs <math>(x,x)</math> (The diagonal minus <math>1</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in  
 
To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of <math>(x,x)</math> where <math>x\in{1,2,3,4,5}</math> must exist.In this case I rather "go backwards". First fixing <math>5</math> pairs <math>(x,x)</math>, (the diagonal of our table) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{5!}{5!} = 1</math> way. Then fixing <math>4</math> pairs <math>(x,x)</math> (The diagonal minus <math>1</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in  
−
<math>4\cdot\frac{5!}{4!} = 20</math> ways. Then fixing <math>3</math> pairs <math>(x,x)</math> (The diagonal minus <math>2</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{(5\cdot4\cdot3\cdot6\cdot3)}{3!2!} + \frac{(5\cdot4\cdot3\cdot6\cdot1)}{3!} = 150</math> ways.
+
<math>4\cdot\frac{5!}{4!} = 20</math> ways. Then fixing <math>3</math> pairs <math>(x,x)</math> (The diagonal minus <math>2</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\tfrac{(5\cdot4\cdot3\cdot6\cdot3)}{3!2!} + \tfrac{(5\cdot4\cdot3\cdot6\cdot1)}{3!} = 150</math> ways.
 
Fixing <math>2</math> pairs <math>(x,x)</math> (the diagonal minus <math>3</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!3!} + \frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!2!} + \frac{(5\cdot4\cdot6\cdot2\cdot1)}{2!2!} = 380</math> ways.
 
Fixing <math>2</math> pairs <math>(x,x)</math> (the diagonal minus <math>3</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!3!} + \frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!2!} + \frac{(5\cdot4\cdot6\cdot2\cdot1)}{2!2!} = 380</math> ways.
−
Lastely, fixing <math>1</math> pair <math>(x,x)</math> (the diagonal minus <math>4</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\frac{5!}{4!} + 4\cdot\frac{5!}{3!} + 5! = 205</math>
+
Lastly, fixing <math>1</math> pair <math>(x,x)</math> (the diagonal minus <math>4</math>) and map them to the other fitting pairs <math>(x,f(x))</math>. You can do this in <math>\tfrac{5!}{4!} + 4\cdot\tfrac{5!}{3!} + 5! = 205</math> ways.
  
 
So <math>1 + 20 + 150 + 380 + 205 = \framebox{756}</math>
 
So <math>1 + 20 + 150 + 380 + 205 = \framebox{756}</math>
Line 23: Line 23:
 
==Solution 2==
 
==Solution 2==
  
−
We can do some caseworks 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>.
+
We perform casework on the number of fixed points (the number of points where <math>f(x) = x</math>).  To better visualize this, use the grid from Solution 1.
  
−
<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>.
+
'''Case 1:''' 5 fixed points
  
−
<math>\textbf{Case 2:}</math> Two "steps" to "Good Points": Assume that <math>f(x)=y</math> and <math>f(y)=y</math>, then we get <math>f(f(x))=f(y)=y</math>, and <math>f(f(f(x)))=f(f(y))=f(y)=y</math>, so <math>f(f(f(x)))=f(f(x))</math>.
+
:- Obviously, there must be <math>1</math> way to do so.
  
−
<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>.
+
'''Case 2:''' 4 fixed points
  
−
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>
+
:- <math>\binom 54</math> ways to choose the <math>4</math> fixed points.  For the sake of conversation, let them be <math>(1, 1), (2, 2), (3, 3), (4, 4)</math>.
 +
:- The last point must be <math>(5, 1), (5, 2), (5, 3),</math> or <math>(5, 4)</math>.
 +
:- There are <math>\binom 54 \cdot 4 = 20</math> solutions for this case.
  
−
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>:
+
'''Case 3:''' 3 fixed points
  
−
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>
+
:- <math>\binom 53</math> ways to choose the <math>3</math> fixed points.  For the sake of conversation, let them be <math>(1, 1), (2, 2), (3, 3)</math>.
 +
:- '''Subcase 3.1:''' None of <math>4</math> or <math>5</math> map to each other
 +
::- The points must be <math>(4, 1), (4, 2), (4, 3)</math> and <math>(5, 1), (5, 2), (5, 3)</math>, giving <math>3 \cdot 3 = 9</math> solutions.
 +
:- '''Subcase 3.2:''' <math>4</math> maps to <math>5</math> or <math>5</math> maps to <math>4</math>
 +
::- The points must be <math>(4, 5)</math> and <math>(5, 1), (5, 2), (5, 3)</math> or <math>(5, 4)</math> and <math>(4, 1), (4, 2), (4, 3)</math>, giving <math>3+3 = 6</math> solutions.
 +
:- There are <math>\binom 53 \cdot (9+6) = 150</math> solutions for this case.
  
−
For <math>a=4</math>, <math>b=1</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{4}\cdot \binom{1}{1}\cdot 4^1\cdot 1^0=20</math>
+
'''Case 4:''' 2 fixed points
  
−
For <math>a=3</math>, <math>b=1</math> and <math>c=1</math>, the number of <math>f</math> is <math>\binom{5}{3}\cdot \binom{2}{1}\cdot 3^1\cdot 1^1=60</math>
+
:- <math>\binom 52</math> ways to choose the <math>2</math> fixed points.  For the sake of conversation, let them be <math>(1, 1), (2, 2)</math>.
 +
:- '''Subcase 4.1:''' None of <math>3</math>, <math>4</math>, or <math>5</math> map to each other
 +
::- There are <math>2 \cdot 2 \cdot 2 = 8</math> solutions for this case, by similar logic to '''Subcase 3.1'''.
 +
:- '''Subcase 4.2:''' exactly one of <math>3, 4, 5</math> maps to another.
 +
::- Example: <math>(3, 4), (4, 1), (5, 2)</math>
 +
::- <math>\binom 32 \cdot 2! = 6</math> ways to choose the 2 which map to each other, and <math>2\cdot 2</math> ways to choose which ones of <math>1</math> and <math>2</math> they map to, giving <math>24</math> solutions for this case.
 +
:- '''Subcase 4.3:''' two of <math>3, 4, 5</math> map to the third
 +
::- Example: <math>(3, 5), (4, 5), (5, 2)</math>
 +
::- <math>\binom 31</math> ways to choose which point is being mapped to, and <math>2</math> ways to choose which one of <math>1</math> and <math>2</math> it maps to, giving <math>6</math> solutions for this case.
 +
:- There are <math>\binom 52 \cdot (8+24+6) = 380</math> solutions.
  
−
For <math>a=3</math>, <math>b=2</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{3}\cdot \binom{2}{2}\cdot 3^2\cdot 2^0=90</math>
+
'''Case 5:''' 1 fixed point
 +
:- <math>\binom 51</math> ways to choose the fixed point.  For the sake of conversation, let it be <math>(1, 1)</math>.
 +
:- '''Subcase 5.1:''' None of <math>2, 3, 4, 5</math> map to each other
 +
::- Obviously, there is <math>1^4 = 1</math> solution to this; all of them map to <math>1</math>.
 +
:- '''Subcase 5.2:''' One maps to another, and the other two map to <math>1</math>.
 +
::- Example: <math>(2, 3), (3, 1), (4, 1), (5, 1)</math>
 +
::- There are <math>\binom 42 \cdot 2!</math> ways to choose which two map to each other, and since each must map to <math>1</math>, this gives <math>12</math>.
 +
:- '''Subcase 5.3:''' One maps to another, and of the other two, one maps to the other as well.
 +
::- Example: <math>(2, 3), (3, 1), (5, 4), (4, 1)</math>
 +
::- There are <math>\binom 42 \cdot 2! \cdot 2! / 2!</math> ways to choose which ones map to another.  This also gives <math>12</math>.
 +
:- '''Subcase 5.4:''' 2 map to a third, and the fourth maps to <math>1</math>.
 +
::- Example: <math>(4, 2), (5, 2), (2, 1), (3, 1)</math>
 +
::- There are <math>\binom 42 \cdot \binom 21 = 12</math> ways again.
 +
:- '''Subcase 5.5:''' 3 map to the fourth.
 +
::- Example: <math>(2, 4), (3, 4), (5, 4), (4, 1)</math>
 +
::- There are <math>\binom 41</math> ways to choose which one is being mapped to, giving <math>4</math> solutions.
 +
:- There are <math>\binom 51 \cdot (1+12+12+12+4) = 205</math> solutions.
  
−
For <math>a=2</math>, <math>b=1</math> and <math>c=2</math>, the number of <math>f</math> is <math>\binom{5}{2}\cdot \binom{3}{1}\cdot 2^1\cdot 1^2=60</math>
+
Therefore, the answer is <math>1+20+150+380+205 = \boxed{756}</math>
  
−
For <math>a=2</math>, <math>b=2</math> and <math>c=1</math>, the number of <math>f</math> is <math>\binom{5}{2}\cdot \binom{3}{2}\cdot 2^2\cdot 2^1=240</math>
+
~First
  
−
For <math>a=2</math>, <math>b=3</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{2}\cdot \binom{3}{3}\cdot 2^3\cdot 3^0=80</math>
+
==Solution 3==
  
−
For <math>a=1</math>, <math>b=1</math> and <math>c=3</math>, the number of <math>f</math> is <math>\binom{5}{1}\cdot \binom{4}{1}\cdot 1^1\cdot 1^3=20</math>
+
We can do some caseworks 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>.
  
−
For <math>a=1</math>, <math>b=2</math> and <math>c=2</math>, the number of <math>f</math> is <math>\binom{5}{1}\cdot \binom{4}{2}\cdot 1^2\cdot 2^2=120</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>.
  
−
For <math>a=1</math>, <math>b=3</math> and <math>c=1</math>, the number of <math>f</math> is <math>\binom{5}{1}\cdot \binom{4}{3}\cdot 1^3\cdot 3^1=60</math>
+
<math>\textbf{Case 2:}</math> Two "steps" to "Good Points": Assume that <math>f(x)=y</math> and <math>f(y)=y</math>, then we get <math>f(f(x))=f(y)=y</math>, and <math>f(f(f(x)))=f(f(y))=f(y)=y</math>, so <math>f(f(f(x)))=f(f(x))</math>.
  
−
For <math>a=1</math>, <math>b=4</math> and <math>c=0</math>, the number of <math>f</math> is <math>\binom{5}{1}\cdot \binom{4}{4}\cdot 1^4\cdot 4^0=5</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>.
  
−
Finally, we get the total number of function <math>f</math>, the number is <math>1+20+60+90+60+240+80+20+120+60+5=\boxed{756}</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 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>s is <math>\binom{5}{5}=1</math>
 +
 
 +
For <math>a=4</math>, <math>b=1</math> and <math>c=0</math>, the number of <math>f</math>s is <math>\binom{5}{4}\cdot \binom{1}{1}\cdot 4^1\cdot 1^0=20</math>
  
−
~Solution by <math>BladeRunnerAUG</math> (Frank FYC)
+
For <math>a=3</math>, <math>b=1</math> and <math>c=1</math>, the number of <math>f</math>s is <math>\binom{5}{3}\cdot \binom{2}{1}\cdot 3^1\cdot 1^1=60</math>
  
−
==Solution 3==
+
For <math>a=3</math>, <math>b=2</math> and <math>c=0</math>, the number of <math>f</math>s is <math>\binom{5}{3}\cdot \binom{2}{2}\cdot 3^2\cdot 2^0=90</math>
  
−
Note that there are <math>5^5</math> possible functions <math>f(x)</math>.
+
For <math>a=2</math>, <math>b=1</math> and <math>c=2</math>, the number of <math>f</math>s is <math>\binom{5}{2}\cdot \binom{3}{1}\cdot 2^1\cdot 1^2=60</math>
  
−
Now consider the probability of picking a function from those <math>3125</math> functions that satisfies, exclusively, one of the following criteria:
+
For <math>a=2</math>, <math>b=2</math> and <math>c=1</math>, the number of <math>f</math>s is <math>\binom{5}{2}\cdot \binom{3}{2}\cdot 2^2\cdot 2^1=240</math>
  
−
<math>P(x = f(x) = f(f(x)) = f(f(f(x)))) = \frac{1}{5^5}</math>
+
For <math>a=2</math>, <math>b=3</math> and <math>c=0</math>, the number of <math>f</math>s is <math>\binom{5}{2}\cdot \binom{3}{3}\cdot 2^3\cdot 3^0=80</math>
  
−
<math>P(x \neq{f(x)} = f(f(x)) = f(f(f(x)))) = \frac{1}{5^4}</math>
+
For <math>a=1</math>, <math>b=1</math> and <math>c=3</math>, the number of <math>f</math>s is <math>\binom{5}{1}\cdot \binom{4}{1}\cdot 1^1\cdot 1^3=20</math>
  
−
<math>P(x = f(x) \neq{f(f(x))} = f(f(f(x)))) = \frac{1}{5^2}</math>
+
For <math>a=1</math>, <math>b=2</math> and <math>c=2</math>, the number of <math>f</math>s is <math>\binom{5}{1}\cdot \binom{4}{2}\cdot 1^2\cdot 2^2=120</math>
  
−
<math>P(x \neq{f(x)} \neq{f(f(x))} = f(f(f(x)))) = \frac{1}{5}</math>
+
For <math>a=1</math>, <math>b=3</math> and <math>c=1</math>, the number of <math>f</math>s is <math>\binom{5}{1}\cdot \binom{4}{3}\cdot 1^3\cdot 3^1=60</math>
  
−
Thus the number of functions <math>f(x)</math> satisfying the condition stated in the problem is given by:
+
For <math>a=1</math>, <math>b=4</math> and <math>c=0</math>, the number of <math>f</math>s is <math>\binom{5}{1}\cdot \binom{4}{4}\cdot 1^4\cdot 4^0=5</math>
  
−
<math>\frac{5^5}{5^5} + \frac{5^5}{5^4} + \frac{5^5}{5^2} + \frac{5^5}{5} = 1 + 5 + 125 + 625 = \boxed{756}</math>
+
Finally, we get the total number of function <math>f</math>, the number is <math>1+20+60+90+60+240+80+20+120+60+5=\boxed{756}</math>
  
−
~ anellipticcurveoverq
+
~Solution by <math>BladeRunnerAUG</math> (Frank FYC)
  
 
==Note (fun fact)==
 
==Note (fun fact)==
 
This exact problem showed up earlier on the 2011 Stanford Math Tournament, Advanced Topics Test.
 
This exact problem showed up earlier on the 2011 Stanford Math Tournament, Advanced Topics Test.
 
This problem also showed up on the 2010 Mock AIME 2 here: https://artofproblemsolving.com/wiki/index.php/Mock_AIME_2_2010_Problems
 
This problem also showed up on the 2010 Mock AIME 2 here: https://artofproblemsolving.com/wiki/index.php/Mock_AIME_2_2010_Problems
 +
 +
==See Also==
 
{{AIME box|year=2018|n=II|num-b=9|num-a=11}}
 
{{AIME box|year=2018|n=II|num-b=9|num-a=11}}
 
{{MAA Notice}}
 
{{MAA Notice}}
 +
 +
[[Category: Intermediate Combinatorics Problems]]

Latest revision as of 13:39, 5 November 2022

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 1

Just to visualize solution 1. If we list all possible $(x,f(x))$, from ${1,2,3,4,5}$ to ${1,2,3,4,5}$ in a specific order, we get $5 \cdot 5 = 25$ different $(x,f(x))$ 's. Namely:

\[(1,1) (1,2) (1,3) (1,4) (1,5)\] \[(2,1) (2,2) (2,3) (2,4) (2,5)\] \[(3,1) (3,2) (3,3) (3,4) (3,5)\] \[(4,1) (4,2) (4,3) (4,4) (4,5)\] \[(5,1) (5,2) (5,3) (5,4) (5,5)\]

To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of $(x,x)$ where $x\in{1,2,3,4,5}$ must exist.In this case I rather "go backwards". First fixing $5$ pairs $(x,x)$, (the diagonal of our table) and map them to the other fitting pairs $(x,f(x))$. You can do this in $\frac{5!}{5!} = 1$ way. Then fixing $4$ pairs $(x,x)$ (The diagonal minus $1$) and map them to the other fitting pairs $(x,f(x))$. You can do this in $4\cdot\frac{5!}{4!} = 20$ ways. Then fixing $3$ pairs $(x,x)$ (The diagonal minus $2$) and map them to the other fitting pairs $(x,f(x))$. You can do this in $\tfrac{(5\cdot4\cdot3\cdot6\cdot3)}{3!2!} + \tfrac{(5\cdot4\cdot3\cdot6\cdot1)}{3!} = 150$ ways. Fixing $2$ pairs $(x,x)$ (the diagonal minus $3$) and map them to the other fitting pairs $(x,f(x))$. You can do this in $\frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!3!} + \frac{(5\cdot4\cdot6\cdot4\cdot2)}{2!2!} + \frac{(5\cdot4\cdot6\cdot2\cdot1)}{2!2!} = 380$ ways. Lastly, fixing $1$ pair $(x,x)$ (the diagonal minus $4$) and map them to the other fitting pairs $(x,f(x))$. You can do this in $\tfrac{5!}{4!} + 4\cdot\tfrac{5!}{3!} + 5! = 205$ ways.

So $1 + 20 + 150 + 380 + 205 = \framebox{756}$

Solution 2

We perform casework on the number of fixed points (the number of points where $f(x) = x$). To better visualize this, use the grid from Solution 1.

Case 1: 5 fixed points

- Obviously, there must be $1$ way to do so.

Case 2: 4 fixed points

- $\binom 54$ ways to choose the $4$ fixed points. For the sake of conversation, let them be $(1, 1), (2, 2), (3, 3), (4, 4)$.
- The last point must be $(5, 1), (5, 2), (5, 3),$ or $(5, 4)$.
- There are $\binom 54 \cdot 4 = 20$ solutions for this case.

Case 3: 3 fixed points

- $\binom 53$ ways to choose the $3$ fixed points. For the sake of conversation, let them be $(1, 1), (2, 2), (3, 3)$.
- Subcase 3.1: None of $4$ or $5$ map to each other
- The points must be $(4, 1), (4, 2), (4, 3)$ and $(5, 1), (5, 2), (5, 3)$, giving $3 \cdot 3 = 9$ solutions.
- Subcase 3.2: $4$ maps to $5$ or $5$ maps to $4$
- The points must be $(4, 5)$ and $(5, 1), (5, 2), (5, 3)$ or $(5, 4)$ and $(4, 1), (4, 2), (4, 3)$, giving $3+3 = 6$ solutions.
- There are $\binom 53 \cdot (9+6) = 150$ solutions for this case.

Case 4: 2 fixed points

- $\binom 52$ ways to choose the $2$ fixed points. For the sake of conversation, let them be $(1, 1), (2, 2)$.
- Subcase 4.1: None of $3$, $4$, or $5$ map to each other
- There are $2 \cdot 2 \cdot 2 = 8$ solutions for this case, by similar logic to Subcase 3.1.
- Subcase 4.2: exactly one of $3, 4, 5$ maps to another.
- Example: $(3, 4), (4, 1), (5, 2)$
- $\binom 32 \cdot 2! = 6$ ways to choose the 2 which map to each other, and $2\cdot 2$ ways to choose which ones of $1$ and $2$ they map to, giving $24$ solutions for this case.
- Subcase 4.3: two of $3, 4, 5$ map to the third
- Example: $(3, 5), (4, 5), (5, 2)$
- $\binom 31$ ways to choose which point is being mapped to, and $2$ ways to choose which one of $1$ and $2$ it maps to, giving $6$ solutions for this case.
- There are $\binom 52 \cdot (8+24+6) = 380$ solutions.

Case 5: 1 fixed point

- $\binom 51$ ways to choose the fixed point. For the sake of conversation, let it be $(1, 1)$.
- Subcase 5.1: None of $2, 3, 4, 5$ map to each other
- Obviously, there is $1^4 = 1$ solution to this; all of them map to $1$.
- Subcase 5.2: One maps to another, and the other two map to $1$.
- Example: $(2, 3), (3, 1), (4, 1), (5, 1)$
- There are $\binom 42 \cdot 2!$ ways to choose which two map to each other, and since each must map to $1$, this gives $12$.
- Subcase 5.3: One maps to another, and of the other two, one maps to the other as well.
- Example: $(2, 3), (3, 1), (5, 4), (4, 1)$
- There are $\binom 42 \cdot 2! \cdot 2! / 2!$ ways to choose which ones map to another. This also gives $12$.
- Subcase 5.4: 2 map to a third, and the fourth maps to $1$.
- Example: $(4, 2), (5, 2), (2, 1), (3, 1)$
- There are $\binom 42 \cdot \binom 21 = 12$ ways again.
- Subcase 5.5: 3 map to the fourth.
- Example: $(2, 4), (3, 4), (5, 4), (4, 1)$
- There are $\binom 41$ ways to choose which one is being mapped to, giving $4$ solutions.
- There are $\binom 51 \cdot (1+12+12+12+4) = 205$ solutions.

Therefore, the answer is $1+20+150+380+205 = \boxed{756}$

~First

Solution 3

We can do some caseworks 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$s is $\binom{5}{5}=1$

For $a=4$, $b=1$ and $c=0$, the number of $f$s 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$s 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$s 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$s 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$s 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$s 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$s 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$s 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$s 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$s 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 $BladeRunnerAUG$ (Frank FYC)

Note (fun fact)

This exact problem showed up earlier on the 2011 Stanford Math Tournament, Advanced Topics Test. This problem also showed up on the 2010 Mock AIME 2 here: https://artofproblemsolving.com/wiki/index.php/Mock_AIME_2_2010_Problems

See Also

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=180219"