2018 AIME I Problems/Problem 12
Contents
- 1 Problem
- 2 Solution 1
- 3 Solution 2
- 4 Solution 3 (Triple Vandermonde's)
- 5 Solution 4 (Symmetry)
- 6 Solution 5
- 7 Solution 6
- 8 Solution 7
- 9 Solution 8 (Generating Functions)
- 10 Solution 9
- 11 Solution 10
- 12 Solution 11 (Quick guesswork for about 2 minutes remaining)
- 13 Solution 12 (Very quick recursion)
- 14 Solution 13
- 15 See Also
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 1
The question asks us for the probability that a randomly chosen subset of the set of the first 18 positive integers has the property that the sum of its elements is divisible by 3. Note that the total number of subsets is because each element can either be in or not in the subset. To find the probability, we will find the total numbers of ways the problem can occur and divide by
.
To simplify the problem, let’s convert the set to mod 3:
Note that there are six elements congruent to 0 mod 3, 6 congruent to 1 mod 3, and 6 congruent to 2 mod 3. After conversion to mod three, the problem is the same but we’re dealing with much simpler numbers. Let’s apply casework on this converted set based on , the sum of the elements of a subset
of
.
In this case, we can restrict the subsets to subsets that only contain 0. There are six 0’s and each one can be in or out of the subset, for a total of subsets. In fact, for every case we will have, we can always add a sequence of 0’s and the total sum will not change, so we will have to multiply by 64 for each case. Therefore, let’s just calculate the total number of ways we can have each case and remember to multiply it in after summing up the cases. This is equivalent to finding the number of ways you can choose such subsets without including the 0's. Therefore this case gives us
way.
In this case and each of the subsequent cases, we denote the number of 1’s in the case and the number of two’s in the case as respectively. Then in this case we have two subcases;
This case has
ways.
This case has
ways.
In total, this case has ways.
In this case, there are 4 subcases;
This case has
way.
This case has
ways.
This case has
ways.
This case has
ways.
In total, this case has ways.
Note that for each case, the # of 1’s goes down by 2 and the # of 2’s goes up by 1. This is because the sum is fixed, so when we change one it must be balanced out by the other. This is similar to the Diophantine equation and the total number of solutions will be
. From here we continue our casework, and our subcases will be coming out quickly as we have realized this relation.
In this case we have 3 subcases:
This case has
ways.
This case has
ways.
This case has
ways.
In total, this case has ways.
In this case we have 4 subcases:
This case has
ways.
This case has
ways.
This case has
ways.
This case has
way.
Therefore the total number of ways in this case is .
Here we notice something interesting. Not only is the answer the same as Case 3, the subcases deliver the exact same answers, just in reverse order. Why is that?
We discover the pattern that the values of of each subcase of Case 5 can be obtained by subtracting the corresponding values of
of each subcase in Case 3 from 6 ( For example, the subcase 0, 6 in Case 5 corresponds to the subcase 6, 0 in Case 3). Then by the combinatorial identity,
, which is why each subcase evaluates to the same number. But can we extend this reasoning to all subcases to save time?
Let’s write this proof formally. Let be the number of subsets of the set
(where each 1 and 2 is distinguishable) such that the sum of the elements of the subset is
and
is divisible by 3. We define the empty set as having a sum of 0. We claim that
.
if and only if there exists
that satisfy
,
,
, and
is the set of the pairs
. This is because for each pair
,
there are six elements of the same residue mod(3) to choose
and
numbers from, and their value sum must be
.
Let all ,
satisfy
and
.
We can rewrite the equation
Therefore, since and
and
,
. As shown above,
and since
and 18 are divisible by 3, 18 -
is divisible by 3. Therefore, by the fact that
, we have that;
, proving our claim.
We have found our shortcut, so instead of bashing out the remaining cases, we can use this symmetry. The total number of ways over all the cases is . The final answer is
There are no more 2’s left to factor out of the numerator, so we are done and the answer is .
~KingRavi
Solution 2
Consider the elements of modulo
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 3 (Triple Vandermonde's)
Elements can either be included or excluded, for a total of
. Then, like the previous solution, let
be the number of elements
and
be the number of elements
. Then,
. Since
, there are 3 cases:
Then, we have,
Using the substitution on every second binomial coefficient, it is clear that the bottom numbers sum to
, and the ones above sum to
. Apply Vandermonde's, we obtain
For , using the same substitution and applying Vandermonde's, we get:
Then, for , it is completely symmetric with
. We get
We have
We get .
Solution 4 (Symmetry)
Note that in general, the answer will be around a third of . We will use this to our advantage. Partition
into disjoint subsets
. Within each of these subsets, there are 3 possible remainders
depending on what elements we choose to include into
: (Using set
for demonstration purposes)
Remainder of zero: Include
Remainder of one: Include
Remainder of two: Include
Suppose there all subsets are of the form . Then, since both choices are
, we can choose either for all siz subsets, giving us
combinations.
On the other hand, suppose there exists a subset that isn't of the form
. Then, it is equally likely that a remainder of zero, one, or two is chosen, i.e. there is a
chance for each. Consider the sum of the other subsets
. They are either
. Whatever that remainder
might be, we can always choose
as the remainder for our set
, giving us a total of
. The probability we choose remainder
is
as previously mentioned. So, we get
total combinations.
Therefore, we get
Solution 5
Rewrite the set after mod 3 as above
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 6
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 7
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
CASE 2- or
integers: There can be
or
integers that are
. We can choose these in
CASE 3- or
integers: There can be
or
integers that are
. We can choose these in
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 8 (Generating Functions)
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
(where
). 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
. (This is known as the third Roots of Unity Filter.) 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 9
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 10
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 11 (Quick guesswork for about 2 minutes remaining)
We conjecture that the difference from the probability will be as small as possible from (The value approached as
, where
is the number of terms in the largest subset).
We also see that there are subsets and know the denominator will be a power of
(since the numerator is an integer).
We essentially want to guess that the greatest integer satisfying
can be plugged in to get the solution of round
.
We see that this occurs at , and get round
round(
)=
.
Solution 12 (Very quick recursion)
The total number of subsets is simply Now we need to find the number of subsets that have a sum divisible by
Ignore the 6 numbers in the list that are divisible by 3. We look only at the number of subsets of then multiply by
at the end. This is because adding a multiple of
to the sum will not change whether it is divisible by
or not and for each of the
multiples, we have two options of whether to add it to the subset or not.
Now, let be the number of subsets of
that have a sum divisible by
. There are
numbers in the set. Let us look at the first
numbers: all subsets of the first
numbers will have a residue
or
mod
If it is
add both
and
to the subset. If it is
add just
to the set, and if it is
add just
We don't have to compute all three cases separately; since there is a 1 to 1 correspondence, we only need the sum of the three cases (which we know is
).
Now, this counts all the subsets except for those that include neither nor
However, this is just
Thus,
and the base case is
We have,
Multiplying this by we have,
The
cancels out with the denominator. However, the second term in the product is obviously odd and so does not cancel further with the denominator, which is just a power of
Thus, we want to find
which equals
Note: While the explanation may seem a bit complicated, the concept behind it is pretty simple. And once you get the solution, computing the answer doesn't take much time.
Solution 13
The total number of subsets is . If
, the sum of the elements divides 3. We can rewrite the set as 6 0s, 6 1s, and 6 2s. We can ignore the zeros for now, since they won't influence the sum so we focus on each configuration of the 6 1s and 6 2s such that the sum is divisible by 3 and then multiply by
at the end. We proceed with casework on the number of values that are equivalent to
as follows:
Case 1: There are zero elements:
Then, there are only configurations of the values congruent to 1 mod 3. There are ways to assign values in the set that are congruent to 1 mod 3 such that the sum of those values divides 3. Therefore there are
configurations for this case.
Case 2: There is one element:
There are ways to choose which element is included in the subset and
ways to assign values to the numbers congruent to 1 mod 3 in the set. Therefore there are
configurations for this case.
Case 3: There are two elements:
There are ways to choose the 2 elements in the set that are congruent to 2 mod 3 and
possible ways to assign values to the numbers congruent to 1 mod 3. Therefore there are
configurations for this case.
Case 4: There are three elements:
There are ways to choose three elements in the set that are congruent to 2 mod 3. There are
ways to assign values to the numbers congruent to 1 mod 3. Therefore, there are
configurations for this case.
Case 5, Case 6, and Case 7 are symmetric to Case 3, Case 2, and Case 1 respectively so we can multiply by 2 for those cases.
Putting all the cases together we obtain . Multiplying by
gives
. Since
,
. Therefore,
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.