Difference between revisions of "2018 AIME II Problems/Problem 10"
(→Solution2) |
(→Solution2) |
||
Line 47: | Line 47: | ||
<math>\textbf{Case 3:}</math> Three "steps" to "Good Points": Assume that <math>f(x)=y</math>, <math>f(y)=z</math> and <math>f(z)=z</math>, then we get <math>f(f(x))=f(y)=z</math>, and <math>f(f(f(x)))=f(f(y))=f(z)=z</math>, so <math>f(f(f(x)))=f(f(x))</math>. | <math>\textbf{Case 3:}</math> Three "steps" to "Good Points": Assume that <math>f(x)=y</math>, <math>f(y)=z</math> and <math>f(z)=z</math>, then we get <math>f(f(x))=f(y)=z</math>, and <math>f(f(f(x)))=f(f(y))=f(z)=z</math>, so <math>f(f(f(x)))=f(f(x))</math>. | ||
− | Divide set <math>\{1,2,3,4,5\}</math> into three parts which satisfy these three cases, respectively. Let the first part has <math>a</math> elements, the second part has <math>b</math> elements and the third part has <math>c</math> elements, it is easy to see that <math>a+b+c=5</math>. First, there are <math>\binom{5}{a}</math> ways to select <math>x</math> for Case 1, | + | Divide set <math>\{1,2,3,4,5\}</math> into three parts which satisfy these three cases, respectively. Let the first part has <math>a</math> elements, the second part has <math>b</math> elements and the third part has <math>c</math> elements, it is easy to see that <math>a+b+c=5</math>. First, there are <math>\binom{5}{a}</math> ways to select <math>x</math> for Case 1. Second, we have <math>\binom{5-a}{b}</math> ways to select <math>x</math> 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 <math>a^b</math>. Finally, we map all the elements that satisfy Case 3 to Case 2, and the total number of ways of this operation is <math>b^c</math>. As a result, the number of such function <math>f</math> can be represented in an algebraic expression contains <math>a</math>, <math>b</math> and <math>c</math>: <math>\boxed{\binom{5}{a}\cdot \binom{5-a}{b}\cdot a^b\cdot b^c}</math> |
Now it's time to talk about the value of <math>a</math>, <math>b</math> and <math>c</math>: | Now it's time to talk about the value of <math>a</math>, <math>b</math> and <math>c</math>: |
Revision as of 09:55, 7 July 2018
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 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 on function is a "Good Point" (Actually its 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 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 function can be represented in an algebraic expression contains , and :
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.