Difference between revisions of "2007 AIME II Problems/Problem 10"
(→Solution) |
|||
Line 2: | Line 2: | ||
Let <math>S</math> be a [[set]] with six [[element]]s. Let <math>P</math> be the set of all [[subset]]s of <math>S.</math> Subsets <math>A</math> and <math>B</math> of <math>S</math>, not necessarily distinct, are chosen independently and at random from <math>P</math>. The [[probability]] that <math>B</math> is contained in at least one of <math>A</math> or <math>S-A</math> is <math>\frac{m}{n^{r}},</math> where <math>m</math>, <math>n</math>, and <math>r</math> are [[positive]] [[integer]]s, <math>n</math> is [[prime]], and <math>m</math> and <math>n</math> are [[relatively prime]]. Find <math>m+n+r.</math> (The set <math>S-A</math> is the set of all elements of <math>S</math> which are not in <math>A.</math>) | Let <math>S</math> be a [[set]] with six [[element]]s. Let <math>P</math> be the set of all [[subset]]s of <math>S.</math> Subsets <math>A</math> and <math>B</math> of <math>S</math>, not necessarily distinct, are chosen independently and at random from <math>P</math>. The [[probability]] that <math>B</math> is contained in at least one of <math>A</math> or <math>S-A</math> is <math>\frac{m}{n^{r}},</math> where <math>m</math>, <math>n</math>, and <math>r</math> are [[positive]] [[integer]]s, <math>n</math> is [[prime]], and <math>m</math> and <math>n</math> are [[relatively prime]]. Find <math>m+n+r.</math> (The set <math>S-A</math> is the set of all elements of <math>S</math> which are not in <math>A.</math>) | ||
− | == Solution == | + | == Solution 1 == |
Use [[casework]]: | Use [[casework]]: | ||
Line 20: | Line 20: | ||
The answer is <math>697 + 2 + 11 = 710</math>. | The answer is <math>697 + 2 + 11 = 710</math>. | ||
+ | |||
+ | == Solution 2 == | ||
+ | we need <math>B</math> to be a subset of <math>A</math> or <math>S-A</math> | ||
+ | we can divide each element of <math>S</math> into 4 categories: | ||
+ | *it is in <math>A</math> and <math>B</math> | ||
+ | *it is in <math>A</math> but not in <math>B</math> | ||
+ | *it is not in <math>A</math> but is in <math>B</math> | ||
+ | *or it is not in <math>A</math> and not in <math>B</math> | ||
+ | these can be denoted as <math>+A+B</math>, <math>+A-B</math>,<math>-A+B</math>, and <math>-A-B</math> | ||
+ | |||
+ | we note that if all of the elements are in <math>+A+B</math>, <math>+A-B</math> and <math>-A-B</math> | ||
+ | we have that <math>B</math> is a subset of <math>A</math> | ||
+ | which can happen in <math>\dfrac{3^6}{4^6}</math> ways | ||
+ | |||
+ | similarly if the elements are in <math>+A-B</math>,<math>-A+B</math>, and <math>-A-B</math> | ||
+ | we have that <math>B</math> is a subset of <math>S-A</math> | ||
+ | which can happen in <math>\dfrac{3^6}{4^6}</math> ways as well | ||
+ | |||
+ | but we need to make sure we don't over-count ways that are in both sets these are when <math>+A-B</math> and <math>-A-B</math> | ||
+ | which can happen in <math>\dfrac{2^6}{4^6}</math> ways | ||
+ | so our probability is <math>\dfrac{2*3^6-2^6}{4^6}= \dfrac{3^6-2^5}{2^11}=\dfrac{697}{2^{11}}</math>. | ||
+ | |||
+ | so the final answer is <math>697 + 2 + 11 = 710</math>. | ||
== See also == | == See also == | ||
{{AIME box|year=2007|n=II|num-b=9|num-a=11}} | {{AIME box|year=2007|n=II|num-b=9|num-a=11}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 19:04, 8 March 2014
Contents
Problem
Let be a set with six elements. Let
be the set of all subsets of
Subsets
and
of
, not necessarily distinct, are chosen independently and at random from
. The probability that
is contained in at least one of
or
is
where
,
, and
are positive integers,
is prime, and
and
are relatively prime. Find
(The set
is the set of all elements of
which are not in
)
Solution 1
Use casework:
has 6 elements:
- Probability:
must have either 0 or 6 elements, probability:
.
- Probability:
has 5 elements:
- Probability:
must have either 0, 6, or 1, 5 elements. The total probability is
.
- Probability:
has 4 elements:
- Probability:
must have either 0, 6; 1, 5; or 2,4 elements. If there are 1 or 5 elements, the set which contains 5 elements must have four emcompassing
and a fifth element out of the remaining
numbers. The total probability is
.
- Probability:
We could just continue our casework. In general, the probability of picking B with elements is
. Since the sum of the elements in the
th row of Pascal's Triangle is
, the probability of obtaining
or
which encompasses
is
. In addition, we must count for when
is the empty set (probability:
), of which all sets of
will work (probability:
).
Thus, the solution we are looking for is .
The answer is .
Solution 2
we need to be a subset of
or
we can divide each element of
into 4 categories:
- it is in
and
- it is in
but not in
- it is not in
but is in
- or it is not in
and not in
these can be denoted as ,
,
, and
we note that if all of the elements are in ,
and
we have that
is a subset of
which can happen in
ways
similarly if the elements are in ,
, and
we have that
is a subset of
which can happen in
ways as well
but we need to make sure we don't over-count ways that are in both sets these are when and
which can happen in
ways
so our probability is
.
so the final answer is .
See also
2007 AIME II (Problems • Answer Key • Resources) | ||
Preceded by Problem 9 |
Followed by Problem 11 | |
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.