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