Difference between revisions of "2018 AIME II Problems/Problem 10"
m (→Problem) |
m (→Solution 1) |
||
Line 14: | Line 14: | ||
(5,1) (5,2) (5,3) (5,4) (5,5) | (5,1) (5,2) (5,3) (5,4) (5,5) | ||
− | To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of (x,x) where x€{1,2,3,4,5} must exist.In this case I rather "go backwards". First fixing 5 pairs (x,x), (the diagonal of our table) and map them to the other fitting pairs (x,f(x)). You can do this in 5!/5! = 1 way. Then fixing 4 pairs (x,x) (The diagonal minus | + | To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of (x,x) where x€{1,2,3,4,5} must exist.In this case I rather "go backwards". First fixing 5 pairs (x,x), (the diagonal of our table) and map them to the other fitting pairs (x,f(x)). You can do this in 5!/5! = 1 way. Then fixing 4 pairs (x,x) (The diagonal minus 1) and map them to the other fitting pairs (x,f(x)). You can do this in |
4x(5!/4!) = 20 ways. Then fixing 3 pairs (x,x) (The diagonal minus 2) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x3x6x3)/3!2! + (5x4x3x6x1)/3! = 150 ways. | 4x(5!/4!) = 20 ways. Then fixing 3 pairs (x,x) (The diagonal minus 2) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x3x6x3)/3!2! + (5x4x3x6x1)/3! = 150 ways. | ||
Fixing 2 pairs (x,x) (the diagonal minus 3) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x6x4x2)/2!3! + (5x4x6x4x2)/2!2! + (5x4x6x2x1)/2!2! = 380 ways. | Fixing 2 pairs (x,x) (the diagonal minus 3) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x6x4x2)/2!3! + (5x4x6x4x2)/2!2! + (5x4x6x2x1)/2!2! = 380 ways. |
Revision as of 08:54, 4 March 2019
Problem
Find the number of functions from
to
that satisfy
for all
in
.
Solution 1
Just to visualize solution 1. If we list all possible (x,f(x)), from {1,2,3,4,5} to {1,2,3,4,5} in a specific order, we get 5*5 = 25 different (x,f(x))'s. Namely:
(1,1) (1,2) (1,3) (1,4) (1,5) (2,1) (2,2) (2,3) (2,4) (2,5) (3,1) (3,2) (3,3) (3,4) (3,5) (4,1) (4,2) (4,3) (4,4) (4,5) (5,1) (5,2) (5,3) (5,4) (5,5)
To list them in this specific order makes it a lot easier to solve this problem. We notice, In order to solve this problem at least one pair of (x,x) where x€{1,2,3,4,5} must exist.In this case I rather "go backwards". First fixing 5 pairs (x,x), (the diagonal of our table) and map them to the other fitting pairs (x,f(x)). You can do this in 5!/5! = 1 way. Then fixing 4 pairs (x,x) (The diagonal minus 1) and map them to the other fitting pairs (x,f(x)). You can do this in 4x(5!/4!) = 20 ways. Then fixing 3 pairs (x,x) (The diagonal minus 2) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x3x6x3)/3!2! + (5x4x3x6x1)/3! = 150 ways. Fixing 2 pairs (x,x) (the diagonal minus 3) and map them to the other fitting pairs (x,f(x)). You can do this in (5x4x6x4x2)/2!3! + (5x4x6x4x2)/2!2! + (5x4x6x2x1)/2!2! = 380 ways. Lastely, fixing 1 pair (x,x) (the diagonal minus 4) and map them to the other fitting pairs (x,f(x)). You can do this in 5!/4! + 4x(5!/3!) + 5! = 205
So 1 + 20 + 150 + 380 + 205 = 756
Solution 2
We can do some caseworks about the special points of functions for
. Let
,
and
be three different elements in set
. There must be elements such like
in set
satisfies
, and we call the points such like
on functions
are "Good Points" (Actually its academic name is "fixed-points"). 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 of “Good points” of
.
One "step" to "Good Points": Assume that
, then we get
, and
, so
.
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
.
Divide 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. Second, we have
ways to select
for Case 2. After that we map all elements that satisfy Case 2 to Case 1, and the total number of ways of this operation is
. Finally, we map all the elements that satisfy Case 3 to Case 2, and the total number of ways of this operation is
. As a result, the number of such functions
can be represented in an algebraic expression contains
,
and
:
Now it's time to consider about the different values of ,
and
and the total number of functions
satisfy these values 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 (Frank FYC)
Note (fun fact)
This exact problem showed up earlier on the 2011 Stanford Math Tournament, Advanced Topics Test.
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.