Let R=(1,2,...,n) be a set with n elements. Let S be a set of all subsets. There are 2^n such subsets. Pick 2 at random call A and B. Show probability that A contained in B is (3/4)^n
Something to help you get started: if S is the power set on R, then for any two randomly selected subsets A and B there are four possibilities: A is a subset of B, B is a subset of A, A is equal to B and A and B are disjoint sets (meaning they have no intersection - for example S= {1,2,3}, A could be {1} and B could be {2,3} - both subsets on S, neither containing the other).
Hopefully that is a step in the right direction.
I think the question can be answered like this.
I assume A and B are not necessarily distinct sets.
Let mean powerset of a set . So in the question statement, . Not to be confused with which I'll use for probability of event .
So for randomly selected subset of , there is a probability that , a probability that , etc.
Suppose . How many (not necessarily proper) supersets does have that are in ? It is . (Each element in the complement of can be either in the superset, or not.) So the probability that is a superset of is .
So we have
Someone please help me with the last step: How to prove that ? I'm guessing it's easy for people more used to working with sums of this nature..
Nice indeed. Here is another approach: induction over n.
The case n=1 is easy to verify.
Suppose that when A and B are randomly chosen subsets of a set of size n that .
Now consider the case where there are n+1 elements , and suppose A and B are randomly chosen subsets. We know , and the events and are independent.
If and , which happens with probability 1/4, then by the inductive hypothesis.
If and , which happens with probability 1/4, then .
If and , which happens with probability 1/4, then .
If and , which happens with probability 1/4, then .
Putting all these cases together,
,
which completes the proof.