Problem:
Let S be a set with six elements. Let P be the set of all subsets of S. Subsets A and B of S, not necessarily distinct, are chosen independently and at random from P. The probability that B is contained in at least one of A or S−A is nrm, where m,n, and r are positive integers, n is prime, and m and n are relatively prime. Find m+n+r. (The set S−A is the set of all elements of S which are not in A.)
Solution:
There are 26 subsets of S, and for 0≤k≤6, there are (k6) subsets with k elements, so the probability that A has k elements is (k6)/26. If A has k elements, there are 2k subsets of S contained in A and 26−k subsets contained in S−A. One of these, the empty set, is contained in both A and S−A, so the probability that B is contained in either A or S−A is 262k+26−k−1. The requested probability is therefore
k=0∑626(k6)⋅262k+26−k−1=2121(k=0∑62k(k6)+k=0∑626−k(k6)−k=0∑6(k6))=2121(2k=0∑62k(k6)−k=0∑6(k6))=2121(2⋅36−26)=21136−25=211697
Thus m+n+r=697+2+11=710.
OR
Let S={1,2,3,4,5,6}. With S1=A and S2=B, let M be the 6×2 matrix in which mij=1 if i∈Sj and 0 otherwise. There are 212 such matrices. Observe that B⊆A precisely when each row of M is 11,10, or 00. There are 36 such matrices. Similarly, B⊆S−A precisely when each row of M is 01,00 or 10, and again there are 36 such matrices. The intersection of these two types of matrices are those in which each row is 00 or 10, and there are 26 such matrices. The requested probability is therefore
21236+36−26=2122⋅36−26=21136−25=211697, as before
The problems on this page are the property of the MAA's American Mathematics Competitions