Summer Problem Solving Marathon Solution #26

We solve the problem by casework on the size of B. For convenience, let S = {1,2,3,4,5,6}.

If the size of B is zero, then A is definitely a subset of S - B = S. There are 2⁶ = 64 subsets of S, so there is a 1/64 chance that the size of B is zero. This gives us a 1/64 chance of success from this option.

The case when the size of B is six is similar -- in this case, A is definitely a subset of S. And there is a 1/64 chance that the size of B is 6. More generally, we will get the same results for size of B = 1 and size of B = 5, and for size of B = 2 and size of B = 4.

So far we have 1/64 + 1/64 chance of success, from the cases size B = 0 and size B = 6. Now consider the case when the size of B = 1. There are 6 subsets of size 1, so the chance of choosing such a subset is 6/64. If the size of B is 1, then there are two choice of A that are subsets of B. S - B is then of size 5, so there are 32 choices of A that are subsets of S - B. That makes a total of 32 + 2 - 34. However, we have counted the empty set twice, so in fact there are 33 choices of A. So we have a 6/64 chance of picking B of size 1, and then a 33/64 chance of picking A that works. This gives us a (33 x 6)/64² = 198/64² chance of success. Since the case when size B = 5 is the same, we double this to get 396/64².

Next we consider the case when the size of B is 2. There are 6 choose 2 = 15 ways of picking such a subset. There are then 4 choices of A that are subsets of B, and 16 choices of A that are subsets of S - B, for a total of 20. Again, we have double-counted the empty set, so we subtract 1 to get 19. So the chance of success when size B = 2 is (15 x 19)/64² = 285/64². Again we double this for the case size B = 4, to get 570/64².

Finally, we consider the case when the size of B is 3. There are 6 choose 3 = 20 ways of picking such a subset. There are then 8 choices of A that are subsets of B, and 8 choices of A that are subsets of S - B, for a total of 16. Subtracting the double-counted empty set, we get 15 choices of A. So the probability of success here is (20 x 15)/64² = 300/64².

Adding up the cases, we have (64 + 64 + 396 + 570 + 300)/64² = 1394/2¹² = 697/2¹¹ = 697/2048.