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