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 "Northeastern WOOTers Mock AIME I Problems/Problem 6"

m (→‎Solution)
m (→‎Solution)
 
Line 7: Line 7:
  
 
'''Claim:''' The number of pairs <math>A</math> and <math>B</math> such that <math>A \subseteq B</math> is <math>3^{10}</math>.
 
'''Claim:''' The number of pairs <math>A</math> and <math>B</math> such that <math>A \subseteq B</math> is <math>3^{10}</math>.
 +
 
'''Method 1:''' If <math>B</math> has <math>k</math> elements, then there are <math>2^k</math> choices for <math>A</math>. Since <math>B</math> has <math>k</math> elements <math>\binom{10}{k}</math> times as <math>B</math> ranges over all possible subsets of <math>\mathcal{S}</math>, the desired quantity is
 
'''Method 1:''' If <math>B</math> has <math>k</math> elements, then there are <math>2^k</math> choices for <math>A</math>. Since <math>B</math> has <math>k</math> elements <math>\binom{10}{k}</math> times as <math>B</math> ranges over all possible subsets of <math>\mathcal{S}</math>, the desired quantity is
 
<cmath> \sum_{k = 1}^{10} \binom{10}{k} \cdot 2^k = (2^1 + 1)^{10} = 3^{10}. </cmath>
 
<cmath> \sum_{k = 1}^{10} \binom{10}{k} \cdot 2^k = (2^1 + 1)^{10} = 3^{10}. </cmath>

Latest revision as of 14:20, 9 August 2021

Problem 6

Let $\mathcal{S}=\{1,...,10\}$. Two subsets, $A$ and $B$, of $S$ are chosen randomly with replacement, with $B$ chosen after $A$. The probability that $A$ is a subset of $B$ can be written as $\frac {p^a}{q^b}$, for some primes $p$ and $q$. Find $ab+p+q$.


Solution

Claim: The number of pairs $A$ and $B$ such that $A \subseteq B$ is $3^{10}$.

Method 1: If $B$ has $k$ elements, then there are $2^k$ choices for $A$. Since $B$ has $k$ elements $\binom{10}{k}$ times as $B$ ranges over all possible subsets of $\mathcal{S}$, the desired quantity is \[\sum_{k = 1}^{10} \binom{10}{k} \cdot 2^k = (2^1 + 1)^{10} = 3^{10}.\]

Method 2: Each element of $\mathcal{S}$ has $3$ options: be in neither $A$ nor $B$, be in just $B$, or be in both $A$ and $B$. All elements assort independently, so there are $3^{10}$ valid pairs of subsets.

Then the answer is $\frac{3^{10}}{2^{20}} \Rightarrow \boxed{205}.$

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=Northeastern_WOOTers_Mock_AIME_I_Problems/Problem_6&oldid=159886"