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"

(→‎Problem)
(→‎Solution)
Line 4: Line 4:
  
 
==Solution==
 
==Solution==
 +
 +
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>.
 +
 +
;<math>\textbf{Case 1: one fixed point.}</math>
 +
;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.
 +
;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.
 +
;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.
 +
;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.
 +
;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>
 +
;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>.
 +
;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.
 +
;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.
 +
;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>
 +
;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>
 +
;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>
 +
;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.
 +
~Solution by ghghghghghghghgh
 +
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{AIME box|year=2018|n=II|num-b=10|num-a=12}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 15:59, 24 March 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

2018 AIME II (Problems • Answer Key • Resources)
Preceded by
Problem 10 		Followed by
Problem 12
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=93475"