Difference between revisions of "2013 AIME II Problems/Problem 11"
(→Solution 2) |
|||
Line 2: | Line 2: | ||
Let <math>A = \{1, 2, 3, 4, 5, 6, 7\}</math>, and let <math>N</math> be the number of functions <math>f</math> from set <math>A</math> to set <math>A</math> such that <math>f(f(x))</math> is a constant function. Find the remainder when <math>N</math> is divided by <math>1000</math>. | Let <math>A = \{1, 2, 3, 4, 5, 6, 7\}</math>, and let <math>N</math> be the number of functions <math>f</math> from set <math>A</math> to set <math>A</math> such that <math>f(f(x))</math> is a constant function. Find the remainder when <math>N</math> is divided by <math>1000</math>. | ||
− | ==Solution | + | ==Solution== |
Any such function can be constructed by distributing the elements of <math>A</math> on three tiers. | Any such function can be constructed by distributing the elements of <math>A</math> on three tiers. | ||
Revision as of 19:37, 23 June 2020
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
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
.
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.