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