Difference between revisions of "2010 AIME II Problems/Problem 8"
m (Created page with '== Problem 8 == Let <math>N</math> be the number of ordered pairs of nonempty sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> that have the following properties: <UL>…') |
m (→Solution 2: typo) |
||
(11 intermediate revisions by 6 users not shown) | |||
Line 1: | Line 1: | ||
− | == Problem | + | == Problem == |
− | Let <math>N</math> be the number of ordered | + | Let <math>N</math> be the number of [[ordered pair]]s of nonempty sets <math>\mathcal{A}</math> and <math>\mathcal{B}</math> that have the following properties: |
<UL> | <UL> | ||
Line 11: | Line 11: | ||
Find <math>N</math>. | Find <math>N</math>. | ||
− | == | + | == Solution== |
+ | Let us [[partition]] the set <math>\{1,2,\cdots,12\}</math> into <math>n</math> numbers in <math>A</math> and <math>12-n</math> numbers in <math>B</math>, | ||
− | + | Since <math>n</math> must be in <math>B</math> and <math>12-n</math> must be in <math>A</math> (<math>n\ne6</math>, we cannot partition into two sets of 6 because <math>6</math> needs to end up somewhere, <math>n\ne 0</math> or <math>12</math> either). | |
− | + | We have <math>\dbinom{10}{n-1}</math> ways of picking the numbers to be in <math>A</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>. | ||
− | + | == 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>. | ||
+ | |||
+ | 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> | |
== See also == | == See also == | ||
{{AIME box|year=2010|num-b=7|num-a=9|n=II}} | {{AIME box|year=2010|num-b=7|num-a=9|n=II}} | ||
+ | |||
+ | [[Category:Intermediate Combinatorics Problems]] | ||
+ | {{MAA Notice}} |
Revision as of 17:43, 6 July 2020
Contents
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 .
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
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.