Difference between revisions of "2010 AIME II Problems/Problem 8"
(→Solution) |
Magnetoninja (talk | contribs) (→Solution 3 (PIE and Complementary Counting)) |
||
(24 intermediate revisions by 5 users not shown) | |||
Line 19: | Line 19: | ||
So the answer is <math>\left(\sum_{n=1}^{11} \dbinom{10}{n-1}\right) - \dbinom{10}{5}=2^{10}-252= \boxed{772}</math>. | So the answer is <math>\left(\sum_{n=1}^{11} \dbinom{10}{n-1}\right) - \dbinom{10}{5}=2^{10}-252= \boxed{772}</math>. | ||
+ | |||
+ | Note: We have <math>\dbinom{10}{n-1}</math> ways of picking the numbers to be in <math>A</math> because there are <math>n</math> numbers in <math>A</math> and since <math>12-n</math> is already a term in the set we simply have to choose another <math>n-1</math> numbers from the <math>10</math> numbers that are available. | ||
== Solution 2== | == Solution 2== | ||
Regardless of the size <math>n</math> of <math>A</math> (ignoring the case when <math>n = 6</math>), <math>n</math> must not be in <math>A</math> and <math>12 - n</math> must be in <math>A</math>. | Regardless of the size <math>n</math> of <math>A</math> (ignoring the case when <math>n = 6</math>), <math>n</math> must not be in <math>A</math> and <math>12 - n</math> must be in <math>A</math>. | ||
− | There are <math>10</math> remaining elements | + | There are <math>10</math> remaining elements whose placements have yet to be determined. Note that the actual value of <math>n</math> does not matter; there is always <math>1</math> necessary element, <math>1</math> forbidden element, and <math>10</math> other elements that need to be distributed. There are <math>2</math> places to put each of these elements, for <math>2^{10}</math> possibilities. |
+ | |||
+ | However, there is the edge case of <math>n = 6; 6</math> is forced not the be in either set, so we must subtract the <math>\dbinom{10}{5}</math> cases where <math>A</math> and <math>B</math> have size <math>6</math>. | ||
+ | |||
+ | Thus, our answer is <math>2^{10} - \dbinom{10}{5} = 1024 - 252 = \boxed{772}</math> | ||
+ | |||
+ | |||
+ | == Solution 3 (PIE and Complementary Counting) == | ||
+ | |||
+ | The total number of possible subsets is <math>\sum_{i=1}^{11}\dbinom{12}{i}</math>, which is <math>2^{12}-2</math>. Note that picking a subset from the set leaves the rest of the set to be in the other subset. We exclude <math>i=0</math> and <math>i=12</math> 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 <math>|A|</math> is in <math>A</math>, which violates the first condition. Then we find the ways where the elements <math>|B|</math> and <math>12-|B|</math> are in set <math>B</math>, which violates only the second condition, and not the first. This ensures we do not overcount. | ||
+ | |||
+ | Case 1: <math>|A|</math> is an element in <math>A</math> | ||
+ | |||
+ | There are <math>\sum_{i=1}^{11}\dbinom{11}{i-1}</math> = <math>2^{11}-1</math> ways in this case. | ||
+ | |||
+ | Case 2: <math>|B|</math> and <math>12-|B|</math> are in <math>B</math> | ||
+ | |||
+ | We introduce a subcase where <math>|B|</math> is not 6, since the other element would also be 6. | ||
+ | There are <math>B-2</math> elements to choose from 10 elements. Therefore, <math>|B|</math> can be from 2 to 11. | ||
+ | There are <math>\sum_{i=2}^{11}\dbinom{10}{i-2}-\dbinom{10}{4} = 2^{10}-211</math> ways. | ||
+ | The other subcase is when <math>|B|</math> is equal to 6. There are <math>\dbinom{11}{5}=462</math> ways. | ||
+ | Adding the subcases gives us <math>2^{10}+251</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=\boxed{772}</math>. | |
− | + | ~[https://artofproblemsolving.com/wiki/index.php/User:Magnetoninja Magnetoninja] | |
== See also == | == See also == |
Latest revision as of 20:57, 20 July 2023
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 is in
, which violates the first condition. Then we find the ways where the elements
and
are in set
, which violates only the second condition, and not the first. This ensures we do not overcount.
Case 1: is an element in
There are =
ways in this case.
Case 2: and
are in
We introduce a subcase where is not 6, since the other element would also be 6.
There are
elements to choose from 10 elements. Therefore,
can be from 2 to 11.
There are
ways.
The other subcase is when
is equal to 6. There are
ways.
Adding the subcases gives us
.
Adding this with case one gives us . Subtracting this from
gives
.
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.