Difference between revisions of "2013 AIME II Problems/Problem 11"
Isundaylee (talk | contribs) (Remove the "needing solution" mark.) |
|||
Line 43: | Line 43: | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2013|n=II|num-b=10|num-a=12}} | {{AIME box|year=2013|n=II|num-b=10|num-a=12}} | ||
+ | {{MAA Notice}} | ||
[[Category:Intermediate Combinatorics Problems]] | [[Category:Intermediate Combinatorics Problems]] |
Revision as of 13:56, 4 July 2013
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
Let the range be
Let the constant function be , clearly,
For every , since , we must have .
Now we enumerate through possible sizes of . cannot be more than 4 since all the numbers in must map to and any number other than in must have at least one number mapped to it.
1.
We have choices for , choices for , and only 1 way to map the 6 numbers that are not in (remaining numbers) since the range is size 1. In total we have choices.
2.
We have choices for , choices for .
Assigning the 5 numbers to the two elements in yields choices. However, one of these choices is to assign all 5 remaining numbers to , resulting in being only of size 1. Exclude that and we have choices.
In total we have choices.
3.
We have choices for , choices for .
Notice that assigning the remaining numbers is equivalent to distributing 4 numbers into three groups where two of the three groups must receive at least 1 number (since we already have all numbers in mapped to , the restriction is not necessary for the group). Ignoring the restrictions we have ways. Now minus the two cases where one of the two restricted group is left empty. There are 2 ways to choose the left-out group, and ways to distribute numbers for each choice. Finally, by inclusion-exclusion principle, we need to add back the case in which both restricted groups are left empty, which has only occurrence. In all, we have ways to assign the remaining numbers.
In total, we have choices for this case.
4.
We have choices for , choices for .
Now we have 3 "groups" to fill and only 3 remaining numbers. Thus each group must receive exactly 1 number. However, we still have ways to permute the mappings.
Thus, we have choices in total.
To summarize, we have different mappings possible. So the answer is .
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.