Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2018 AIME I Problems/Problem 12"

(→‎Solution 1)
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 $T$ of $U = \{ 1,2,3,\ldots,18 \}$, let $s(T)$ be the sum of the elements of $T$, with $s(\emptyset)$ defined to be $0$. If $T$ is chosen at random among all subsets of $U$, the probability that $s(T)$ is divisible by $3$ is $\frac{m}{n}$, where $m$ and $n$ are relatively prime positive integers. Find $m$.

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 ${6 \choose 0}=1$ way to choose zero numbers ${6 \choose 1}=6$ ways to choose 1 and so on. There ends up being ${6 \choose 0}+{6 \choose 3}+{6 \choose 6}$ possible subsets congruent to 0mod 3. There are $2^6=64$ possible subsets of these numbers.

Solution 3

Notice that six numbers are $0\pmod3$, six are $1\pmod3$, and six are $2\pmod3$. Having numbers $0\pmod3$ will not change the remainder when $s(T)$ is divided by $3$, so we can choose any number of these in our subset. We ignore these for now. The number of numbers that are $1\pmod3$, minus the number of numbers that are $2\pmod3$, must be a multiple of $3$, possibly zero or negative. We can now split into cases based on how many numbers that are $1\pmod3$ are in the set.

Case 1- $0$, $3$, or $6$ integers: There can be $0$, $3$, or $6$ integers that are $2\pmod3$. We can choose these in $\left(\binom60+\binom63+\binom66\right)\cdot\left(\binom60+\binom63+\binom66\right)=(1+20+1)^2=484$ ways.

Case 2- $1$ or $4$ integers: There can be $2$ or $5$ integers that are $2\pmod3$. We can choose these in $\left(\binom61+\binom64\right)\cdot\left(\binom62+\binom65\right)=(6+15)^2=441$ ways.

Case 3- $2$ or $5$ integers: There can be $1$ or $4$ integers that are $2\pmod3$. We can choose these in $\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441$ ways.

Adding these up, we get that there are $1366$ 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 $3$ in our set, we have that there are $1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66+\right)=1366\cdot2^6$ subsets $T$ with a sum that is a multiple of $3$. Since there are $2^{18}$ total subsets, the probability is $\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}$, so the answer is $\boxed{683}$.

Solution 4

We use generating functions. Each element of $U$ has two choices that occur with equal probability--either it is in the set or out of the set. Therefore, given $n\in U$, the probability generating function is \[\frac{1}{2}+\frac{1}{2}x^n.\] Therefore, in the generating function \[\frac{1}{2^{18}}(1+x)(1+x^2)(1+x^3)\cdots (1+x^{18}),\] the coefficient of $x^k$ represents the probability of obtaining a sum of $k$. We wish to find the sum of the coefficients of all terms of the form $x^{3k}$. If $\omega=2^{2\pi i/3}$ is a cube root of unity, then it is well know that for a polynomial $P(x)$, \[\frac{P(1)+P(\omega)+P(\omega^2)}{3}\] will yield the sum of the coefficients of the terms of the form $x^{3k}$. Then we find \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*} To evaluate the last two products, we utilized the facts that $\omega^3=1$ and $1+\omega+\omega^2=0$. Therefore, the desired probability is \[\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.\] Thus the answer is $\boxed{683}$.

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2018_AIME_I_Problems/Problem_12&oldid=93103"