Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

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 18:04, 8 March 2014

Problem

Let $S$ be a set with six elements. Let $P$ be the set of all subsets of $S.$ Subsets $A$ and $B$ of $S$, not necessarily distinct, are chosen independently and at random from $P$. The probability that $B$ is contained in at least one of $A$ or $S-A$ is $\frac{m}{n^{r}},$ where $m$, $n$, and $r$ are positive integers, $n$ is prime, and $m$ and $n$ are relatively prime. Find $m+n+r.$ (The set $S-A$ is the set of all elements of $S$ which are not in $A.$)

Solution 1

Use casework:

  • $B$ has 6 elements:
    • Probability: $\frac{1}{2^6} = \frac{1}{64}$
    • $A$ must have either 0 or 6 elements, probability: $\frac{2}{2^6} = \frac{2}{64}$.
  • $B$ has 5 elements:
    • Probability: ${6\choose5}/64 = \frac{6}{64}$
    • $A$ must have either 0, 6, or 1, 5 elements. The total probability is $\frac{2}{64} + \frac{2}{64} = \frac{4}{64}$.
  • $B$ has 4 elements:
    • Probability: ${6\choose4}/64 = \frac{15}{64}$
    • $A$ 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 $B$ and a fifth element out of the remaining $2$ numbers. The total probability is $\frac{2}{64}\left({2\choose0} + {2\choose1} + {2\choose2}\right) = \frac{2}{64} + \frac{4}{64} + \frac{2}{64} = \frac{8}{64}$.

We could just continue our casework. In general, the probability of picking B with $n$ elements is $\frac{{6\choose n}}{64}$. Since the sum of the elements in the $k$th row of Pascal's Triangle is $2^k$, the probability of obtaining $A$ or $S-A$ which encompasses $B$ is $\frac{2^{7-n}}{64}$. In addition, we must count for when $B$ is the empty set (probability: $\frac{1}{64}$), of which all sets of $A$ will work (probability: $1$).

Thus, the solution we are looking for is $\left(\sum_{i=1}^6 \frac{{6\choose i}}{64} \cdot \frac{2^{7-i}}{64}\right) + \frac{1}{64} \cdot \frac{64}{64}<cmath>=\frac{(1)(64)+(6)(64)+(15)(32)+(20)(16)+(15)(8)+(6)(4)+(1)(2)}{(64)(64)}</cmath>=\frac{1394}{2^{12}}$$=\frac{697}{2^{11}}$.

The answer is $697 + 2 + 11 = 710$.

Solution 2

we need $B$ to be a subset of $A$ or $S-A$ we can divide each element of $S$ into 4 categories:

  • it is in $A$ and $B$
  • it is in $A$ but not in $B$
  • it is not in $A$ but is in $B$
  • or it is not in $A$ and not in $B$

these can be denoted as $+A+B$, $+A-B$,$-A+B$, and $-A-B$

we note that if all of the elements are in $+A+B$, $+A-B$ and $-A-B$ we have that $B$ is a subset of $A$ which can happen in $\dfrac{3^6}{4^6}$ ways

similarly if the elements are in $+A-B$,$-A+B$, and $-A-B$ we have that $B$ is a subset of $S-A$ which can happen in $\dfrac{3^6}{4^6}$ ways as well

but we need to make sure we don't over-count ways that are in both sets these are when $+A-B$ and $-A-B$ which can happen in $\dfrac{2^6}{4^6}$ ways so our probability is $\dfrac{2*3^6-2^6}{4^6}= \dfrac{3^6-2^5}{2^11}=\dfrac{697}{2^{11}}$.

so the final answer is $697 + 2 + 11 = 710$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_AIME_II_Problems/Problem_10&oldid=60759"