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 14:59, 24 March 2018
Problem
Find the number of functions from
to
that satisfy
for all
in
.
Solution
We do casework on the number of fixed points of , that is, the number of
such that
. We know that at least one such
exists, namely
.
- There are five ways to choose the fixed point. WLOG let the fixed point be
. Then at least one of
must map onto
, the only fixed point.
- Suppose exactly one of these values maps to
; there are four ways to choose such a value. WLOG let it be
. Then all of
must map to
in order to be mapped to
in the next iteration. There are
solutions in this case.
- Suppose exactly two of these values map to
; there are
ways to choose such values. WLOG let them be
and
. Then
and
must map to one of
and
, where there are
ways to do so. Therefore there are
solutions in this case.
- Suppose exactly three of these values map to
; there are
ways to choose such values. WLOG let them be
,
, and
. Then
must map to one of
,
, and
, where there are
solutions. Therefore there are
solutions in this case.
- Suppose exactly four of these values map to
. Then everything maps to
and there is
solution in this case.
- Therefore there are
solutions in Case 1.
- There are
ways to choose the fixed points. WLOG let them be
and
. Then at least one of
must map onto
or
.
- Suppose exactly one of these values maps to
or
; there are three ways to choose this value, and two ways to choose the value it maps to. WLOG let it be
. Then both
and
must map to
, for a total of
solutions in this case.
- Suppose exactly two of these values map to
or
; there are
ways to choose these values, and
ways to choose the values they map to. WLOG let them be
and
. Then
must map to one of
and
, for two possible choices. Therefore there are
solutions in this case.
- Suppose exactly three of these values map to
or
; then everything maps to
or
and there are
solutions in this case.
- Therefore there are
solutions in Case 2.
- There are
ways to choose the fixed points. WLOG let them be
,
, and
. Then at least one of
and
must map onto
,
, or
.
- Suppose exactly one of these values map to
,
, or
; there are two ways to choose this value, and three ways to choose the value is maps to. WLOG let it be
. Then
must map to
, for a total of
solutions in this case.
- Suppose exactly two of these values map to
,
, or
; then everything maps to
,
, or
, and there are
solutions in this case.
- Therefore there are
solutions in Case 3.
- There are
ways to choose the fixed points. WLOG let them to
,
,
, and
. Then
must map to one of these values, for a total of
solutions in Case 4.
- Since everything is a fixed point, there is only one solution in Case 5.
- Therefore there are a total of
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.