2007 AIME II Problems/Problem 10
Let be a set with six elements. Let be the set of all subsets of Subsets and of , not necessarily distinct, are chosen independently and at random from . The probability that is contained in one of or is where , , and are positive integers, is prime, and and are relatively prime. Find (The set is the set of all elements of which are not in )
- has 6 elements:
- must have either 0 or 6 elements, probability: .
- has 5 elements:
- must have either 0, 6, or 1, 5 elements. The total probability is .
- has 4 elements:
- must have either 0, 6; 1, 5; or 2,4 elements. If there are 1 or 5 elements, the set which contains 5 elements must have four emcompassing and a fifth element out of the remaining numbers. The total probability is .
We could just continue our casework. In general, the probability of picking B with elements is . Since the sum of the elements in the th row of Pascal's Triangle is , the probability of obtaining or which encompasses is . In addition, we must count for when is the empty set (probability: ), of which all sets of will work (probability: ).
Thus, the solution we are looking for is .
The answer is .
we need to be a subset of or we can divide each element of into 4 categories:
- it is in and
- it is in but not in
- it is not in but is in
- or it is not in and not in
these can be denoted as , ,, and
we note that if all of the elements are in , or we have that is a subset of which can happen in ways
similarly if the elements are in ,, or we have that is a subset of which can happen in ways as well
but we need to make sure we don't over-count ways that are in both sets these are when or which can happen in ways so our probability is .
so the final answer is .
must be in or must be in . This is equivalent to saying that must be in or is disjoint from . The probability of this is the sum of the probabilities of each event individually minus the probability of each event occurring simultaneously. There are ways to choose , where is the number of elements in . From those elements, there are ways to choose . Thus, the probability that is in is the sum of all the values for values of ranging from to . For the second probability, the ways to choose stays the same but the ways to choose is now . We see that these two summations are simply from the Binomial Theorem and that each of them is . We subtract the case where both of them are true. This only happens when is the null set. can be any subset of , so there are possibilities. Our final sum of possibilities is . We have total possibilities for both and , so there are total possibilities. . This reduces down to . The answer is thus .
Let denote the number of elements in a general set . We use complementary counting.
There is a total of elements in , so the total number of ways to choose and is .
Note that the number of -element subset of is . In general, for , in order for to be in neither nor , must have at least one element from both and . In other words, must contain any subset of and except for the empty set . This can be done in ways. As ranges from to , we can calculate the total number of unsuccessful outcomes to be So our desired answer is
To begin with, we note that there are subsets of (which we can assume is ), including the null set. This gives a total of total possibilities for A and B.
Case 1: B is contained in A only. If B has elements, which occurs in ways, A can be anything, giving us . If B has element, A must contain that element, and then the remaining 5 are free to be in A or not in A. This gives us . Summing, we end up with the binomial expansion of .
Case 2: B is contained in S-A only. By symmetry, this case is the same as Case 1, once again giving us possibilities.
Case 3: B is contained in both. We claim here that B can only be the null set. For contradiction, assume that there exists some element in B which satisfies this restriction. Then, A must contain as well, but we also know that contains , contradiction. Hence, B is the null set, whereas A can be anything. This gives us possibilities.
Since we have overcounted Case 3 in both of the other two cases, our final count is . This gives us the probability . Upon simplifying, we end up with , giving the desired answer of . - Spacesam
|2007 AIME II (Problems • Answer Key • Resources)|
|1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15|
|All AIME Problems and Solutions|