2018 AIME I Problems/Problem 12
Contents
Problem
For every subset of , let be the sum of the elements of , with defined to be . If is chosen at random among all subsets of , the probability that is divisible by is , where and are relatively prime positive integers. Find .
Solution
Ignore the 's because we're gonna multiply at the end. Let be the and be the . The key here is that so the difference between the number of and is a multiple of .
1. Counted twice because and can be switched: 2. Counted once: ...
By Vandermonde's identity on the second case, this is
Solution 1
Rewrite the set after mod 3
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0
All 0s can be omitted
Case 1 No 1 No 2
Case 2
Case 3
Case 4
Case 5
Case 6
Case 7
Case 8
Case 9
Case 10
Case 11
Case 12
Case 13
Case 14
Case 15
Case 16
Case 17
Total
ANS=
By SpecialBeing2017
Solution 2
Consider the numbers . Each of those are congruent to . There is way to choose zero numbers ways to choose and so on. There ends up being possible subsets congruent to . There are possible subsets of these numbers. By symmetry there are subsets each for and .
We get the same numbers for the subsets of .
For , all subsets are .
So the probability is:
Solution 3
Notice that six numbers are , six are , and six are . Having numbers will not change the remainder when is divided by , so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are , minus the number of numbers that are , must be a multiple of , possibly zero or negative. We can now split into cases based on how many numbers that are are in the set.
Case 1- , , or integers: There can be , , or integers that are . We can choose these in ways.
Case 2- or integers: There can be or integers that are . We can choose these in ways.
Case 3- or integers: There can be or integers that are . We can choose these in ways.
Adding these up, we get that there are ways to choose the numbers such that their sum is a multiple of three. Putting back in the possibility that there can be multiples of in our set, we have that there are subsets with a sum that is a multiple of . Since there are total subsets, the probability is , so the answer is .
Solution 4
We use generating functions. Each element of has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given , the probability generating function is Therefore, in the generating function the coefficient of represents the probability of obtaining a sum of . We wish to find the sum of the coefficients of all terms of the form . If is a cube root of unity, then it is well know that for a polynomial , will yield the sum of the coefficients of the terms of the form . Then we find To evaluate the last two products, we utilized the facts that and . Therefore, the desired probability is Thus the answer is .
Solution 5
Define a set that "works" to be a set for which the sum of the terms is mod . The given set mod is Let be the number of subsets of the first terms of this set that "work." Consider just the first terms: There are total subsets, and (the subsets are and ). Now consider the first terms: To find , we set aside the last terms as a "reserve" that we can pair with subsets of the first terms (which we looked at earlier).
First, all subsets of the first terms can either be paired with a or a (or nothing) from the "reserve" terms so that they "work," creating subsets that "work" already. But for each of these, we have the option to add a from the reserve, so we now have subsets that "work." For each of the subsets of the first terms that "work", we can also add on a or a from the reserves, creating new subsets that "work." And that covers all of them. With all of this information, we can write as The same process can be used to calculate then etc. so we can generalize it to Thus, we calculate with this formula: Because there are total possible subsets, the desired probability is so the answer is
Solution 6
Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if is of a small size.
If , then out of subsets work, for a probability of .
If , then out of subsets work, for a probability of .
If , then out of subsets work, for a probability of .
Let be the numerator of the desired probability if is of size . Then and . Noticing that the denominators are multiplied by each time, we can conclude that the pattern of the numerators is , so .
Solution 7 (Quick guesswork for about 2 minutes remaining)
We conjecture that the difference from the probability will be as small as possible from 1/3
(The value approached as n-->infinity, where n is the number of terms in the largest subset.)
We also see that there are 2^18 subsets and know the denominator will be a power of 2
(since the numerator is an integer).
We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 <1000 can be plugged in to get the solution of round(2^n/3)
We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.
See Also
2018 AIME I (Problems • Answer Key • Resources) | ||
Preceded by Problem 11 |
Followed by Problem 13 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 | ||
All AIME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.