Difference between revisions of "2018 AIME I Problems/Problem 12"
Math101010 (talk | contribs) m |
(→Solution 1) |
||
Line 4: | Line 4: | ||
==Solution 1== | ==Solution 1== | ||
Rewrite the set after mod3 | Rewrite the set after mod3 | ||
+ | |||
1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 | 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 | ||
+ | |||
All 0s can be omitted | All 0s can be omitted | ||
+ | |||
Case 1 | Case 1 | ||
No 1 No 2 | No 1 No 2 | ||
1 | 1 | ||
+ | |||
Case 2 | Case 2 | ||
222 | 222 | ||
20 | 20 | ||
+ | |||
Case 3 | Case 3 | ||
222222 | 222222 | ||
1 | 1 | ||
+ | |||
Case 4 | Case 4 | ||
12 | 12 | ||
6*6=36 | 6*6=36 | ||
+ | |||
Case 5 | Case 5 | ||
12222 | 12222 | ||
6*15=90 | 6*15=90 | ||
+ | |||
Case 6 | Case 6 | ||
1122 | 1122 | ||
15*15=225 | 15*15=225 | ||
+ | |||
Case 7 | Case 7 | ||
1122222 | 1122222 | ||
15*6=90 | 15*6=90 | ||
+ | |||
Case 8 | Case 8 | ||
111 | 111 | ||
20 | 20 | ||
+ | |||
Case 9 | Case 9 | ||
111222 | 111222 | ||
20*20=400 | 20*20=400 | ||
+ | |||
Case 10 | Case 10 | ||
111222222 | 111222222 | ||
20 | 20 | ||
+ | |||
Case 11 | Case 11 | ||
11112 | 11112 | ||
15*6=90 | 15*6=90 | ||
+ | |||
Case 12 | Case 12 | ||
11112222 | 11112222 | ||
15*15=225 | 15*15=225 | ||
+ | |||
Case 13 | Case 13 | ||
1111122 | 1111122 | ||
6*15=90 | 6*15=90 | ||
+ | |||
Case 14 | Case 14 | ||
1111122222 | 1111122222 | ||
6*6=36 | 6*6=36 | ||
+ | |||
Case 15 | Case 15 | ||
111111 | 111111 | ||
1 | 1 | ||
+ | |||
Case 16 | Case 16 | ||
111111222 | 111111222 | ||
20 | 20 | ||
+ | |||
Case 17 | Case 17 | ||
111111222222 | 111111222222 | ||
1 | 1 | ||
+ | |||
Total 1+20+1+36+90+225+90+20+400+20+90+225+90+36+1+20+1=484+360+450+72=1366 | 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 | P=1362/2^12=683/2^11 | ||
+ | |||
ANS=683 | ANS=683 | ||
− | |||
==Solution 2== | ==Solution 2== |
Revision as of 21:01, 9 March 2018
Contents
[hide]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
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 possible subsets congruent to 0mod 3. There are possible subsets of these numbers.
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 .
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.