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) |
||
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> | + | '''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. | ||
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> |
Revision as of 13:19, 9 August 2021
Problem 6
Let . Two subsets, and , of are chosen randomly with replacement, with chosen after . The probability that is a subset of can be written as , for some primes and . Find .
Solution
Claim: The number of pairs and such that is .
Method 1: If has elements, then there are choices for . Since has elements times as ranges over all possible subsets of , the desired quantity is
Method 2: Each element of has options: be in neither nor , be in just , or be in both and . All elements assort independently, so there are valid pairs of subsets.
Then the answer is