Difference between revisions of "2018 AIME I Problems/Problem 12"
(→Solution 1) |
Mathgeek2006 (talk | contribs) |
||
Line 96: | Line 96: | ||
Adding these up, we get that there are <math>1366</math> 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 <math>3</math> in our set, we have that there are <math>1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66+\right)=1366\cdot2^6</math> subsets <math>T</math> with a sum that is a multiple of <math>3</math>. Since there are <math>2^{18}</math> total subsets, the probability is <math>\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math>, so the answer is <math>\boxed{683}</math>. | Adding these up, we get that there are <math>1366</math> 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 <math>3</math> in our set, we have that there are <math>1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66+\right)=1366\cdot2^6</math> subsets <math>T</math> with a sum that is a multiple of <math>3</math>. Since there are <math>2^{18}</math> total subsets, the probability is <math>\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math>, so the answer is <math>\boxed{683}</math>. | ||
+ | |||
+ | ==Solution 4== | ||
+ | We use generating functions. Each element of <math>U</math> has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given <math>n\in U</math>, the probability generating function is | ||
+ | <cmath>\frac{1}{2}+\frac{1}{2}x^n.</cmath> | ||
+ | Therefore, in the generating function | ||
+ | <cmath>\frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18}),</cmath> | ||
+ | the coefficient of <math>x^k</math> represents the probability of obtaining a sum of <math>k</math>. We wish to find the sum of the coefficients of all terms of the form <math>x^{3k}</math>. If <math>\omega=2^{2\pi i/3}</math> is a cube root of unity, then it is well know that for a polynomial <math>P(x)</math>, | ||
+ | <cmath>\frac{P(1)+P(\omega)+P(\omega^2)}{3}</cmath> | ||
+ | will yield the sum of the coefficients of the terms of the form <math>x^{3k}</math>. Then we find | ||
+ | <cmath> | ||
+ | \begin{align*} | ||
+ | \frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18})&=1\\frac{1}{2^{18}}(1+\omega)(1+\omega^2)(1+\omega^3)\cdots (1+\omega^{18})&=\frac{1}{2^{12}}\\frac{1}{2^{18}}(1+\omega^2)(1+\omega^4)(1+\omega^6)\cdots (1+\omega^{36})&=\frac{1}{2^{12}}. | ||
+ | \end{align*}</cmath> | ||
+ | To evaluate the last two products, we utilized the facts that <math>\omega^3=1</math> and <math>1+\omega+\omega^2=0</math>. Therefore, the desired probability is | ||
+ | <cmath>\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.</cmath> | ||
+ | Thus the answer is <math>\boxed{683}</math>. | ||
==See Also== | ==See Also== | ||
{{AIME box|year=2018|n=I|num-b=11|num-a=13}} | {{AIME box|year=2018|n=I|num-b=11|num-a=13}} | ||
{{MAA Notice}} | {{MAA Notice}} |
Revision as of 21:26, 9 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
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 .
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.