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)
 
(One intermediate revision by the same user not shown)
Line 13: Line 13:
 
'''Method 2:''' Each element of <math>\mathcal{S}</math> has <math>3</math> options: be in neither <math>A</math> nor <math>B</math>, be in just <math>B</math>, or be in both <math>A</math> and <math>B</math>. All elements assort independently, so there are <math>3^{10}</math> valid pairs of subsets.
 
'''Method 2:''' Each element of <math>\mathcal{S}</math> has <math>3</math> options: be in neither <math>A</math> nor <math>B</math>, be in just <math>B</math>, or be in both <math>A</math> and <math>B</math>. All elements assort independently, so there are <math>3^{10}</math> valid pairs of subsets.
  
−
Then the answer is <math>\frac{3^10}{2^20} \Rightarrow \boxed{205}.</math>
+
Then the answer is <math>\frac{3^{10}}{2^{20}} \Rightarrow \boxed{205}.</math>

Latest revision as of 13: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"