2018 AIME II Problems/Problem 10
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 , from to in a specific order, we get different 's. Namely:
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 where must exist.In this case I rather "go backwards". First fixing pairs , (the diagonal of our table) and map them to the other fitting pairs . You can do this in way. Then fixing pairs (The diagonal minus ) and map them to the other fitting pairs . You can do this in ways. Then fixing pairs (The diagonal minus ) and map them to the other fitting pairs . You can do this in ways. Fixing pairs (the diagonal minus ) and map them to the other fitting pairs . You can do this in ways. Lastly, fixing pair (the diagonal minus ) and map them to the other fitting pairs . You can do this in ways.
So
Solution 2
We perform casework on the number of fixed points (the number of points where ). To better visualize this, use the grid from Solution 1.
Case 1: 5 fixed points
- - Obviously, there must be way to do so.
Case 2: 4 fixed points
- - ways to choose the fixed points. For the sake of conversation, let them be .
- - The last point must be or .
- - There are solutions for this case.
Case 3: 3 fixed points
- - ways to choose the fixed points. For the sake of conversation, let them be .
- - Subcase 3.1: None of or map to each other
- - The points must be and , giving solutions.
- - Subcase 3.2: maps to or maps to
- - The points must be and or and , giving solutions.
- - There are solutions for this case.
Case 4: 4 fixed points
- - ways to choose the fixed points. For the sake of conversation, let them be .
- - Subcase 4.1: None of , , or map to each other
- - There are solutions for this case, by similar logic to Subcase 3.1.
- - Subcase 4.2: exactly one of maps to another.
- - Example:
- - ways to choose the 2 which map to each other, and ways to choose which ones of and they map to, giving solutions for this case.
- - Subcase 4.3: two of map to the third
- - Example:
- - ways to choose which point is being mapped to, and ways to choose which one of and it maps to, giving solutions for this case.
- - There are solutions.
Case 5: 1 fixed point
- - ways to choose the fixed point. For the sake of conversation, let it be .
- - Subcase 5.1: None of map to each other
- - Obviously, there is solution to this; all of them map to .
- - Subcase 5.2: One maps to another, and the other two map to .
- - Example:
- - There are ways to choose which two map to each other, and since each must map to , this gives .
- - Subcase 5.3: One maps to another, and of the other two, one maps to the other as well.
- - Example:
- - There are ways to choose which ones map to another. This also gives .
- - Subcase 5.4: 2 map to a third, and the fourth maps to .
- - Example:
- - There are ways again.
- - Subcase 5.5: 3 map to the fourth.
- - Example:
- - There are ways to choose which one is being mapped to, giving solutions.
- - There are solutions.
Therefore, the answer is
~First
Solution 3
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 s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s is
For , and , the number of s 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. This problem also showed up on the 2010 Mock AIME 2 here: https://artofproblemsolving.com/wiki/index.php/Mock_AIME_2_2010_Problems
See Also
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.