2018 AIME I Problems/Problem 12

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=\frac{1362}{2^{12}}=\frac{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 $1 \pmod 3$ . 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} = 22$ possible subsets congruent to $0\pmod 3$ . There are $2^6=64$ possible subsets of these numbers. By symmetry there are $21$ subsets each for $1 \pmod 3$ and $2 \pmod3$ .

We get the same numbers for the subsets of $\{2,5,8,11,14,17\}$ .

For $\{3,6,9,12,15,18\}$ , all $2^6$ subsets are $0 \pmod3$ .

So the probability is: $\frac{(22\cdot22+2\cdot21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}$

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=e^{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+1)(1+1^2)(1+1^3)\cdots (1+1^{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}$ .

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

Page

Toolbox

Search