Difference between revisions of "2018 AIME I Problems/Problem 12"
m (→Solution 1) |
m (→Solution 1) |
||
Line 11: | Line 11: | ||
Case 1 | Case 1 | ||
No 1 No 2 | No 1 No 2 | ||
− | 1 | + | <math>1</math> |
Case 2 | Case 2 | ||
− | 222 | + | <math>222</math> |
− | 20 | + | <math>20</math> |
Case 3 | Case 3 | ||
− | 222222 | + | <math>222222</math> |
− | 1 | + | <math>1</math> |
Case 4 | Case 4 | ||
− | 12 | + | <math>12</math> |
− | 6*6=36 | + | <math>6*6=36</math> |
Case 5 | Case 5 | ||
− | 12222 | + | <math>12222</math> |
− | 6*15=90 | + | <math>6*15=90</math> |
Case 6 | Case 6 | ||
− | 1122 | + | <math>1122</math> |
− | 15*15=225 | + | <math>15*15=225</math> |
Case 7 | Case 7 | ||
− | 1122222 | + | <math>1122222</math> |
− | 15*6=90 | + | <math>15*6=90</math> |
Case 8 | Case 8 | ||
− | 111 | + | <math>111</math> |
− | 20 | + | <math>20</math> |
Case 9 | Case 9 | ||
− | 111222 | + | <math>111222</math> |
<math>20*20=400</math> | <math>20*20=400</math> | ||
Case 10 | Case 10 | ||
− | 111222222 | + | <math>111222222</math> |
− | 20 | + | <math>20</math> |
Case 11 | Case 11 | ||
− | 11112 | + | <math>11112</math> |
<math>15*6=90</math> | <math>15*6=90</math> | ||
Case 12 | Case 12 | ||
− | 11112222 | + | <math>11112222</math> |
<math>15*15=225</math> | <math>15*15=225</math> | ||
Case 13 | Case 13 | ||
− | 1111122 | + | <math>1111122</math> |
<math>6*15=90</math> | <math>6*15=90</math> | ||
Case 14 | Case 14 | ||
− | 1111122222 | + | <math>1111122222</math> |
<math>6*6=36</math> | <math>6*6=36</math> | ||
Case 15 | Case 15 | ||
− | 111111 | + | <math>111111</math> |
− | 1 | + | <math>1</math> |
Case 16 | Case 16 | ||
− | 111111222 | + | <math>111111222</math> |
− | 20 | + | <math>20</math> |
Case 17 | Case 17 | ||
− | 111111222222 | + | <math>111111222222</math> |
− | 1 | + | <math>1</math> |
Total <math>1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366</math> | Total <math>1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366</math> | ||
Line 81: | Line 81: | ||
<math>P=1362/2^12=683/2^11</math> | <math>P=1362/2^12=683/2^11</math> | ||
− | ANS=683 | + | ANS=<math>683</math> |
By S.B. | By S.B. |
Revision as of 02:46, 29 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
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 S.B.
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
.
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.