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"

(Created page with "== Problem 6 == Let <math>\mathcal{S}=\{1,...,10\}</math>. Two subsets, <math>A</math> and <math>B</math>, of <math>S</math> are chosen randomly with replacement, with <math>...")
 
m (→‎Solution)
 
(2 intermediate revisions by the same user not shown)
Line 6: Line 6:
 
== Solution ==
 
== Solution ==
  
−
'''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>
  
−
'''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"