Difference between revisions of "2013 AIME II Problems/Problem 11"
m |
Xhypotenuse (talk | contribs) |
||
(2 intermediate revisions by 2 users not shown) | |||
Line 17: | Line 17: | ||
==Solution 1 Clarified== | ==Solution 1 Clarified== | ||
− | Define the three layers as [[domain]] <math>x</math>, [[codomain]] <math>f(x)</math>, and codomain <math>f(f(x))</math>. Each one of them is contained in the [[set]] <math>A</math>. We know that <math>f(f(x))</math> is a [[constant function]], or in other words, can only take on one value. So, we can start off by choosing that value <math>c</math> in <math>7</math> ways. So now, we choose the values that can be <math>f(x)</math> for all those values should satisfy <math>f(f(x))=c</math>. Let | + | Define the three layers as [[domain]] <math>x</math>, [[codomain]] <math>f(x)</math>, and codomain <math>f(f(x))</math>. Each one of them is contained in the [[set]] <math>A</math>. We know that <math>f(f(x))</math> is a [[constant function]], or in other words, can only take on one value. So, we can start off by choosing that value <math>c</math> in <math>7</math> ways. So now, we choose the values that can be <math>f(x)</math> for all those values should satisfy <math>f(f(x))=c</math>. Let <math>S</math> be that set of values. First things first, we must have <math>c</math> to be part of <math>S</math>, for the <math>S</math> is part of the domain of <math>x</math>. Since the values in <math>i\in S</math> all satisfy <math>f(i) = c</math>, we have <math>c</math> to be a value that <math>f(x)</math> can be. Now, for the elements other than <math>5</math>: |
− | If we have <math>k</math> elements other than <math>5</math> that can be part of <math>S</math>, we will have <math>\binom{6}{k}</math> ways to choose those values. There will also be <math>k</math> ways for each of the elements in <math>A</math> other than <math>c</math> and those in set <math>S</math> (for when [[function]] <math>f</math> is applied on those values, we already know it would be <math>c</math>). There are <math>6-k</math> elements in <math>A</math> other than <math>c</math> and those in set <math>S</math>. Thus, there should be <math> | + | If we have <math>k</math> elements other than <math>5</math> that can be part of <math>S</math>, we will have <math>\binom{6}{k}</math> ways to choose those values. There will also be <math>k</math> ways for each of the elements in <math>A</math> other than <math>c</math> and those in set <math>S</math> (for when [[function]] <math>f</math> is applied on those values, we already know it would be <math>c</math>). There are <math>6-k</math> elements in <math>A</math> other than <math>c</math> and those in set <math>S</math>. Thus, there should be <math>k^{6-k}</math> ways to match the domain <math>x</math> to the values of <math>f(x)</math>. Summing up all possible values of <math>k</math> (<math>[1,6]</math>), we have |
− | <cmath>\sum_{k=1}^6 k^{6-k} = 6\cdot 1 + 15\cdot 16 + 20\cdot 27 + 15\cdot 16 + 6\cdot 5 + 1 | + | <cmath>\sum_{k=1}^6 \binom{6}{k} k^{6-k} = 6\cdot 1 + 15\cdot 16 + 20\cdot 27 + 15\cdot 16 + 6\cdot 5 + 1 = 1057</cmath> |
Multiplying that by the original <math>7</math> for the choice of <math>c</math>, we have <math>7 \cdot 1057 = 7\boxed{399}.</math> | Multiplying that by the original <math>7</math> for the choice of <math>c</math>, we have <math>7 \cdot 1057 = 7\boxed{399}.</math> | ||
− | ~ | + | |
+ | ==Solution 2== | ||
+ | |||
+ | It is clear that we must have one fixed point (that is, <math>f(x)=x</math>). WLOG, let <math>x=1</math> be a fixed point, so <math>f(1)=1</math>. | ||
+ | |||
+ | Now, let's do casework on how many of the inputs <math>2, 3, 4, 5, 6 ,7</math> leads to <math>1</math>. Generally, if some values in that aforementioned list leads to <math>1</math>, then running it in the function again will yield <math>1</math>. All other values must be the the values that leads to <math>1</math>. | ||
+ | |||
+ | |||
+ | For example: | ||
+ | |||
+ | |||
+ | <math>\textbf{Case 1:}</math> All <math>6</math> of <math>2, 3, 4, 5, 6, 7</math> lead to <math>1</math>. | ||
+ | In this case, there is only <math>1</math> way. | ||
+ | |||
+ | <math>\textbf{Case 2:}</math> <math>5</math> of <math>6</math> of <math>2, 3, 4, 5, 6, 7</math> lead to <math>1</math>. | ||
+ | In this case, we choose <math>5</math> of the <math>6</math> to lead to <math>1</math>: <math>6\choose5</math>. | ||
+ | |||
+ | Then, the other value that does not lead to <math>1</math> should be one of the values that do: <math>5</math> ways. | ||
+ | |||
+ | <math>\binom{6}{5}\cdot5</math> | ||
+ | |||
+ | <math>\textbf{Case 3:}</math> <math>4</math> of <math>6</math> lead to <math>1</math>. | ||
+ | Choose which lead to <math>1</math>: <math>6\choose4</math> then the other values: <math>4^2</math> ways | ||
+ | |||
+ | <math>\binom{6}{4}\cdot4^2</math> | ||
+ | |||
+ | <math>\textbf{Case 4:}</math> <math>3</math> of <math>6</math> lead to <math>1</math>. | ||
+ | <math>\binom{6}{3}\cdot3^3</math> | ||
+ | |||
+ | <math>\textbf{Case 5:}</math> <math>2</math> of <math>6</math> lead to <math>1</math>. | ||
+ | <math>\binom{6}{2}\cdot2^4</math> | ||
+ | |||
+ | <math>\textbf{Case 6:}</math> <math>1</math> of <math>6</math> lead to <math>1</math>. | ||
+ | <math>\binom{6}{1}\cdot1^5</math> | ||
+ | |||
+ | |||
+ | Adding up all the cases, we have <math>1057</math> cases. But don't forget to account for the WLOG and multiply by <math>7</math>, yielding us the final answer of <math>7\boxed{399}.</math> | ||
+ | |||
+ | |||
+ | ~xHypotenuse | ||
+ | |||
Latest revision as of 22:20, 17 October 2024
Contents
[hide]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 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 . Thus, there should be ways to match the domain to the values of . Summing up all possible values of (), we have
Multiplying that by the original for the choice of , we have
Solution 2
It is clear that we must have one fixed point (that is, ). WLOG, let be a fixed point, so .
Now, let's do casework on how many of the inputs leads to . Generally, if some values in that aforementioned list leads to , then running it in the function again will yield . All other values must be the the values that leads to .
For example:
All of lead to .
In this case, there is only way.
of of lead to . In this case, we choose of the to lead to : .
Then, the other value that does not lead to should be one of the values that do: ways.
of lead to . Choose which lead to : then the other values: ways
of lead to .
of lead to .
of lead to .
Adding up all the cases, we have cases. But don't forget to account for the WLOG and multiply by , yielding us the final answer of
~xHypotenuse
Video Solution
https://youtu.be/aaO7abKG0BQ?si=KLfz6oyzVR0d8D13
~MathProblemSolvingSkills.com
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.