2013 AIME II Problems/Problem 11
Contents
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
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 .
Solution 2
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 .
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.