Difference between revisions of "2018 AIME I Problems/Problem 12"
(→Solution 2) |
(→Solution 2) |
||
Line 86: | Line 86: | ||
==Solution 2== | ==Solution 2== | ||
− | Consider the numbers {1,4,7,10,13,16}. Each of those are congruent to 1mod3. There is <math>{6 \choose 0}=1</math> way to choose zero numbers <math>{6 \choose 1}=6</math> ways to choose 1 and so on. There ends up being <math>{6 \choose 0}+{6 \choose 3}+{6 \choose 6}</math> = 22 possible subsets congruent to 0mod 3. There are <math>2^6=64</math> possible subsets of these numbers. By symmetry there are 21 subsets each for | + | Consider the numbers {1,4,7,10,13,16}. Each of those are congruent to 1mod3. There is <math>{6 \choose 0}=1</math> way to choose zero numbers <math>{6 \choose 1}=6</math> ways to choose 1 and so on. There ends up being <math>{6 \choose 0}+{6 \choose 3}+{6 \choose 6}</math> = 22 possible subsets congruent to 0mod 3. There are <math>2^6=64</math> possible subsets of these numbers. By symmetry there are 21 subsets each for 1mod3 and 2mod3. |
+ | |||
We get the same numbers for the subsets of {2,5,8,11,14,17}. | We get the same numbers for the subsets of {2,5,8,11,14,17}. | ||
− | For {3,6,9,12,15,18}, all | + | |
+ | For {3,6,9,12,15,18}, all <math>2^6</math> subsets are 0mod3. | ||
+ | |||
+ | So the probability is: <math>\frac{(22\cdot22+2\cdot\21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math> | ||
==Solution 3== | ==Solution 3== |
Revision as of 12:06, 16 March 2018
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
Rewrite the set after mod3
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 1
Case 2 222 20
Case 3 222222 1
Case 4 12 6*6=36
Case 5 12222 6*15=90
Case 6 1122 15*15=225
Case 7 1122222 15*6=90
Case 8 111 20
Case 9 111222 20*20=400
Case 10 111222222 20
Case 11 11112 15*6=90
Case 12 11112222 15*15=225
Case 13 1111122 6*15=90
Case 14 1111122222 6*6=36
Case 15 111111 1
Case 16 111111222 20
Case 17 111111222222 1
Total 1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366
P=1362/2^12=683/2^11
ANS=683
By S.B.
Solution 2
Consider the numbers {1,4,7,10,13,16}. Each of those are congruent to 1mod3. There is way to choose zero numbers
ways to choose 1 and so on. There ends up being
= 22 possible subsets congruent to 0mod 3. There are
possible subsets of these numbers. By symmetry there are 21 subsets each for 1mod3 and 2mod3.
We get the same numbers for the subsets of {2,5,8,11,14,17}.
For {3,6,9,12,15,18}, all subsets are 0mod3.
So the probability is: $\frac{(22\cdot22+2\cdot\21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}$ (Error compiling LaTeX. Unknown error_msg)
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
.
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.