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 . 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