Difference between revisions of "2010 AIME II Problems/Problem 8"
Magnetoninja (talk | contribs) (→Solution 2) |
Magnetoninja (talk | contribs) (→Solution 3 (PIE and Complementary Counting)) |
||
Line 51: | Line 51: | ||
Adding this with case one gives us <math>2^{11}+2^{10}+250</math>. Subtracting this from <math>2^{12}-2</math> gives <math>1024-252=772</math> | Adding this with case one gives us <math>2^{11}+2^{10}+250</math>. Subtracting this from <math>2^{12}-2</math> gives <math>1024-252=772</math> | ||
+ | |||
+ | -Magnetoninja | ||
== See also == | == See also == |
Revision as of 22:49, 10 May 2023
Contents
[hide]Problem
Let be the number of ordered pairs of nonempty sets and that have the following properties:
- ,
- ,
- The number of elements of is not an element of ,
- The number of elements of is not an element of .
Find .
Solution
Let us partition the set into numbers in and numbers in ,
Since must be in and must be in (, we cannot partition into two sets of 6 because needs to end up somewhere, or either).
We have ways of picking the numbers to be in .
So the answer is .
Note: We have ways of picking the numbers to be in because there are numbers in and since is already a term in the set we simply have to choose another numbers from the numbers that are available.
Solution 2
Regardless of the size of (ignoring the case when ), must not be in and must be in .
There are remaining elements whose placements have yet to be determined. Note that the actual value of does not matter; there is always necessary element, forbidden element, and other elements that need to be distributed. There are places to put each of these elements, for possibilities.
However, there is the edge case of is forced not the be in either set, so we must subtract the cases where and have size .
Thus, our answer is
Solution 3 (PIE and Complementary Counting)
The total number of possible subsets is , which is . Note that picking a subset from the set leaves the rest of the set to be in the other subset. We exclude and since they leave a set empty. We proceed with complementary counting and casework:
We apply the Principle of Inclusion and Exclusion for casework on the complementary cases. We find the ways where the element #elements in is in , which violates the first condition. Then we find the ways where the elements #elements in and 12-#elements in are in set , which violates only the second condition, and not the first (If we did, we would overcount the union of both cases). This ensures all possible cases are covered.
Case 1: #elements in is an element in
There are = ways in this case.
Case 2: #elements in and 12-#elements are in
We introduce a subcase where #elements in is not , since it would also result in for the other element. There are items to choose from , the being the mandatory elements in . Therefore, can be from 2 to 11. There are ways. The other subcase is when #elements in are equal to . There are ways for this case, which equals . Adding the subcases gives us .
Adding this with case one gives us . Subtracting this from gives
-Magnetoninja
See also
2010 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 7 |
Followed by Problem 9 | |
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.