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
Solution2
We can do some case work too, about the special points of function for
. Let
,
and
be three different elements in set
. There must be an element
in set
satisfies
, and we call the point
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
because the highest iterations of function
is
. Now we can classify
cases.
One "step" to "Good Points": Assume that
, then we get
.
Two "steps" to "Good Points": Assume that
and
, then we get
, and
, so
.
Three "steps" to "Good Points": Assume that
,
and
, then we get
, and
, so
.
Divided set into three parts which satisfy these three cases, respectively. Let the first part has
elements, the second part has
elements and the third part has
elements, it is easy to see that
. First, there are
ways to select
for Case 1, and we have
ways to select
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
. As a result, the total number of
of one special
and one special
is
Now it's time to talk about the value of and
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
For ,
and
, the number of
is
Finally, we get the total number of function , the number is
~Solution by FYC
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.