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)
m (→‎Solution 2: ; fix typo)
 
(39 intermediate revisions by 15 users not shown)
Line 3: Line 3:
 
Find the number of functions <math>f(x)</math> from <math>\{1, 2, 3, 4, 5\}</math> to <math>\{1, 2, 3, 4, 5\}</math> that satisfy <math>f(f(x)) = f(f(f(x)))</math> for all <math>x</math> in <math>\{1, 2, 3, 4, 5\}</math>.
 
Find the number of functions <math>f(x)</math> from <math>\{1, 2, 3, 4, 5\}</math> to <math>\{1, 2, 3, 4, 5\}</math> that satisfy <math>f(f(x)) = f(f(f(x)))</math> for all <math>x</math> in <math>\{1, 2, 3, 4, 5\}</math>.
  
−
==Solution==
+
==Solution 1==
  
−
We do casework on the number of fixed points of <math>f</math>, that is, the number of <math>x\in\{1,2,3,4,5\}</math> such that <math>f(x)=x</math>. We know that at least one such <math>x</math> exists, namely <math>x=f(f(1))</math>.
+
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:
  
−
;<math>\textbf{Case 1: one fixed point.}</math>
+
<cmath>(1,1) (1,2) (1,3) (1,4) (1,5)</cmath>
−
;There are five ways to choose the fixed point. WLOG let the fixed point be <math>1</math>. Then at least one of <math>2,3,4,5</math> must map onto <math>1</math>, the only fixed point.
+
<cmath>(2,1) (2,2) (2,3) (2,4) (2,5)</cmath>  
−
;Suppose exactly one of these values maps to <math>1</math>; there are four ways to choose such a value. WLOG let it be <math>2</math>. Then all of <math>3,4,5</math> must map to <math>2</math> in order to be mapped to <math>1</math> in the next iteration. There are <math>4</math> solutions in this case.
+
<cmath>(3,1) (3,2) (3,3) (3,4) (3,5)</cmath>  
−
;Suppose exactly two of these values map to <math>1</math>; there are <math>\binom 4 2=6</math> ways to choose such values. WLOG let them be <math>2</math> and <math>3</math>. Then <math>4</math> and <math>5</math> must map to one of <math>2</math> and <math>3</math>, where there are <math>2^2=4</math> ways to do so. Therefore there are <math>6\cdot 4=24</math> solutions in this case.
+
<cmath>(4,1) (4,2) (4,3) (4,4) (4,5)</cmath>
−
;Suppose exactly three of these values map to <math>1</math>; there are <math>\binom 4 3=4</math> ways to choose such values. WLOG let them be <math>2</math>, <math>3</math>, and <math>4</math>. Then <math>5</math> must map to one of <math>2</math>, <math>3</math>, and <math>4</math>, where there are <math>3</math> solutions. Therefore there are <math>4\cdot 3=12</math> solutions in this case.
+
<cmath>(5,1) (5,2) (5,3) (5,4) (5,5)</cmath>
−
;Suppose exactly four of these values map to <math>1</math>. Then everything maps to <math>1</math> and there is <math>1</math> solution in this case.
 
−
;Therefore there are <math>5\cdot(4+24+12+1)=205</math> solutions in Case 1.
 
  
−
;<math>\textbf{Case 2: two fixed points.}</math>
+
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
−
;There are <math>\binom 5 2=10</math> ways to choose the fixed points. WLOG let them be <math>1</math> and <math>2</math>. Then at least one of <math>3,4,5</math> must map onto <math>1</math> or <math>2</math>.
+
<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.
−
;Suppose exactly one of these values maps to <math>1</math> or <math>2</math>; there are three ways to choose this value, and two ways to choose the value it maps to. WLOG let it be <math>3</math>. Then both <math>4</math> and <math>5</math> must map to <math>3</math>, for a total of <math>3\cdot 2=6</math> solutions in this case.
+
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.
−
;Suppose exactly two of these values map to <math>1</math> or <math>2</math>; there are <math>\binom 3 2=3</math> ways to choose these values, and <math>2^2=4</math> ways to choose the values they map to. WLOG let them be <math>3</math> and <math>4</math>. Then <math>5</math> must map to one of <math>3</math> and <math>4</math>, for two possible choices. Therefore there are <math>3\cdot 2^2\cdot 2=24</math> solutions in this case.
+
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.
−
;Suppose exactly three of these values map to <math>1</math> or <math>2</math>; then everything maps to <math>1</math> or <math>2</math> and there are <math>2^3=8</math> solutions in this case.
 
−
;Therefore there are <math>10\cdot(6+24+8)=380</math> solutions in Case 2.
 
  
−
;<math>\textbf{Case 3: three fixed points.}</math>
+
So <math>1 + 20 + 150 + 380 + 205 = \framebox{756}</math>
−
;There are <math>\binom 5 3=10</math> ways to choose the fixed points. WLOG let them be <math>1</math>, <math>2</math>, and <math>3</math>. Then at least one of <math>4</math> and <math>5</math> must map onto <math>1</math>, <math>2</math>, or <math>3</math>.
 
−
;Suppose exactly one of these values map to <math>1</math>, <math>2</math>, or <math>3</math>; there are two ways to choose this value, and three ways to choose the value is maps to. WLOG let it be <math>4</math>. Then <math>5</math> must map to <math>4</math>, for a total of <math>2\cdot 3=6</math> solutions in this case.
 
−
;Suppose exactly two of these values map to <math>1</math>, <math>2</math>, or <math>3</math>; then everything maps to <math>1</math>, <math>2</math>, or <math>3</math>, and there are <math>3^2=9</math> solutions in this case.
 
−
;Therefore there are <math>10\cdot(6+9)=150</math> solutions in Case 3.
 
  
−
;<math>\textbf{Case 4: four fixed points.}</math>
+
==Solution 2==
−
;There are <math>\binom 5 4=5</math> ways to choose the fixed points. WLOG let them to <math>1</math>, <math>2</math>, <math>3</math>, and <math>4</math>. Then <math>5</math> must map to one of these values, for a total of <math>5\cdot 4=20</math> solutions in Case 4.
 
  
−
;<math>\textbf{Case 5: five fixed points.}</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.
−
;Since everything is a fixed point, there is only one solution in Case 5.
 
  
−
;Therefore there are a total of <math>205+380+150+20+1=\boxed{756}</math> functions that satisfy the problem condition.
+
'''Case 1:''' 5 fixed points
−
~Solution by ghghghghghghghgh
 
  
−
==Solution2==
+
:- Obviously, there must be <math>1</math> way to do so.
  
−
We can do some case work too, 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> is a "Good Point" (Actually it's 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.
+
'''Case 2:''' 4 fixed points
  
−
<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(f(f(x)))=f(x)</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.
 +
 
 +
'''Case 3:''' 3 fixed points
 +
 
 +
:- <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.
 +
 
 +
'''Case 4:''' 2 fixed points
 +
 
 +
:- <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.
 +
 
 +
'''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.
 +
 
 +
Therefore, the answer is <math>1+20+150+380+205 = \boxed{756}</math>
 +
 
 +
~First
 +
 
 +
==Solution 3==
 +
 
 +
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>.
 +
 
 +
<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 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>.
 
<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>.
Line 47: Line 89:
 
<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>.
  
−
Divided 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, and we have <math>\binom{5-a}{b}</math> ways to select <math>x</math> for Case 2; then we maps all elements that satisfy Case 2 to Case 1, Case 3 to Case 2, and we have total number of <math>a^b\cdot b^c</math>. As a result, the total number of <math>f</math> of one special <math>a</math> and one special <math>b</math> is <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> and <math>b</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>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> is <math>\binom{5}{4}\cdot \binom{1}{1}\cdot 4^1\cdot 1^0=20</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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
−
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>
+
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>
  
 
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>
 
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>
  
−
~Solution by FYC
+
~Solution by <math>BladeRunnerAUG</math> (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==
 
{{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"