2013 AIME II Problems/Problem 11
Problem 11
Let , and let
be the number of functions
from set
to set
such that
is a constant function. Find the remainder when
is divided by
.
Solution 1
Any such function can be constructed by distributing the elements of on three tiers.
The bottom tier contains the constant value, for any
. (Obviously
.)
The middle tier contains elements
such that
, where
.
The top tier contains elements such that
equals an element on the middle tier.
There are choices for
. Then for a given
, there are
ways to choose the elements on the middle tier, and then
ways to draw arrows down from elements on the top tier to elements on the middle tier.
Thus , giving the answer
.
Solution 1 Clarified
Define the three layers as domain , codomain
, and codomain
. Each one of them is contained in the set
. We know that
is a constant function, or in other words, can only take on one value. So, we can start off by choosing that value
in
ways. So now, we choose the values that can be
for all those values should satisfy
. Let's
be that set of values. First things first, we must have
to be part of
, for the
is part of the domain of
. Since the values in
all satisfy
, we have
to be a value that
can be. Now, for the elements other than
:
If we have elements other than
that can be part of
, we will have
ways to choose those values. There will also be
ways for each of the elements in
other than
and those in set
(for when function
is applied on those values, we already know it would be
). There are
elements in
other than
and those in set
. So, there should be
ways to match the domain
to the values of
. So, summing up all possible values of
(
), we have
Multiplying that by the original for the choice of
, we have
~sml1809
Solution 2
Let the domain of be set
and the image of
be
. Essentially,
and
, where
is the constant.
See Also
2013 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.