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

m (Solution 1: Typo)
(Solution 7 (Quick guesswork for about 2 minutes remaining))
(11 intermediate revisions by 6 users not shown)
Line 81: Line 81:
 
<math>P=\frac{1366}{2^{12}}=\frac{683}{2^{11}}</math>
 
<math>P=\frac{1366}{2^{12}}=\frac{683}{2^{11}}</math>
  
ANS=<math>683</math>
+
ANS=<math>\boxed{683}</math>
  
By S.B.
+
By SpecialBeing2017
  
 
==Solution 2==
 
==Solution 2==
Line 103: Line 103:
 
Case 3- <math>2</math> or <math>5</math> integers:  There can be <math>1</math> or <math>4</math> integers that are <math>2\pmod3</math>.  We can choose these in <math>\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441</math> ways.
 
Case 3- <math>2</math> or <math>5</math> integers:  There can be <math>1</math> or <math>4</math> integers that are <math>2\pmod3</math>.  We can choose these in <math>\left(\binom62+\binom65\right)\cdot\left(\binom61+\binom64\right)=(15+6)^2=441</math> ways.
  
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==
 
==Solution 4==
Line 120: Line 120:
 
<cmath>\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.</cmath>
 
<cmath>\frac{1+1/2^{12}+1/2^{12}}{3}=\frac{683}{2^{11}}.</cmath>
 
Thus the answer is <math>\boxed{683}</math>.
 
Thus the answer is <math>\boxed{683}</math>.
 +
 +
==Solution 5==
 +
Define a set that "works" to be a set for which the sum of the terms is <math>0</math> mod <math>3</math>. The given set mod <math>3</math> is
 +
<cmath>\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.</cmath>
 +
Let <math>w(N)</math> be the number of subsets of the first <math>N</math> terms of this set that "work."
 +
Consider just the first <math>3</math> terms:
 +
<cmath>\{1,2,0\}.</cmath>
 +
There are <math>2^3=8</math> total subsets, and <math>w(3)=4</math> (the subsets are <math>\emptyset, \{0\}, \{1,2\},</math> and <math>\{1,2,0\}</math>). Now consider the first <math>6</math> terms:
 +
<cmath>\{1,2,0,1,2,0\}.</cmath>
 +
To find <math>w(6)</math>, we set aside the last <math>3</math> terms as a "reserve" that we can pair with subsets of the first <math>3</math> terms (which we looked at earlier).
 +
 +
First, all <math>2^3</math> subsets of the first <math>3</math> terms can either be paired with a <math>1</math> or a <math>2</math> (or nothing) from the "reserve" terms so that they "work," creating <math>2^3</math> subsets that "work" already. But for each of these, we have the option to add a <math>0</math> from the reserve, so we now have <math>2\cdot2^3</math> subsets that "work." For each of the <math>w(3)=4</math> subsets of the first <math>3</math> terms that "work", we can also add on a <math>\{1,2\}</math> or a <math>\{1,2,0\}</math> from the reserves, creating <math>2w(3)</math> new subsets that "work." And that covers all of them. With all of this information, we can write <math>w(6)</math> as
 +
<cmath>w(6)=2\cdot2^3+2w(3)=2(2^3+w(3)).</cmath>
 +
The same process can be used to calculate <math>w(9)</math> then <math>w(12)</math> etc. so we can generalize it to
 +
<cmath>w(N)=2(2^{N-3}+w(N-3)).</cmath>
 +
Thus, we calculate <math>w(18)</math> with this formula:
 +
<cmath>w(18)=2( 2^{15} + 2( 2^{12} + 2( 2^9 + 2( 2^6 + 2( 2^3 + 4 ) ) ) ) )=87424.</cmath>
 +
Because there are <math>2^{18}</math> total possible subsets, the desired probability is
 +
<cmath>\frac{w(3)}{2^{18}}=\frac{87424}{2^{18}}=\frac{683}{2048},</cmath>
 +
so the answer is <math>\boxed{683}.</math>
 +
 +
==Solution 6==
 +
Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if <math>U</math> is of a small size.
 +
 +
If <math>U = \{ 1,2,0\} \pmod 3</math>, then <math>4</math> out of <math>8</math> subsets work, for a probability of <math>\frac12</math>.
 +
 +
If <math>U = \{ 1,2,0,1,2,0\} \pmod 3</math>, then <math>24</math> out of <math>64</math> subsets work, for a probability of <math>\frac38</math>.
 +
 +
If <math>U = \{ 1,2,0,1,2,0,1,2,0\} \pmod 3</math>, then <math>176</math> out of <math>512</math> subsets work, for a probability of <math>\frac{11}{32}</math>.
 +
 +
Let <math>a_n</math> be the numerator of the desired probability if <math>U</math> is of size <math>3n</math>. Then <math>a_1 = 1, a_2 = 3,</math> and <math>a_3 = 11</math>. Noticing that the denominators are multiplied by <math>4</math> each time, we can conclude that the pattern of the numerators is <math>a_n = 4a_{n-1} - 1</math>, so <math>a_6 = \boxed{683}</math>.
 +
 +
==Solution 7 (Quick guesswork for about 2 minutes remaining)==
 +
 +
 +
We conjecture that the difference from the probability will be as small as possible from 1/3
 +
 +
(The value approached as n-->infinity, where n is the number of terms in the largest subset.)
 +
 +
 +
We also see that there are 2^18 subsets and know the denominator will be a power of 2
 +
(since the numerator is an integer).
 +
 +
We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 <1000 can be plugged in to get the solution of round(2^n/3)
 +
 +
 +
We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.
  
 
==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 16:40, 7 May 2019

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{1366}{2^{12}}=\frac{683}{2^{11}}$

ANS=$\boxed{683}$

By SpecialBeing2017

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}$.

Solution 5

Define a set that "works" to be a set for which the sum of the terms is $0$ mod $3$. The given set mod $3$ is \[\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.\] Let $w(N)$ be the number of subsets of the first $N$ terms of this set that "work." Consider just the first $3$ terms: \[\{1,2,0\}.\] There are $2^3=8$ total subsets, and $w(3)=4$ (the subsets are $\emptyset, \{0\}, \{1,2\},$ and $\{1,2,0\}$). Now consider the first $6$ terms: \[\{1,2,0,1,2,0\}.\] To find $w(6)$, we set aside the last $3$ terms as a "reserve" that we can pair with subsets of the first $3$ terms (which we looked at earlier).

First, all $2^3$ subsets of the first $3$ terms can either be paired with a $1$ or a $2$ (or nothing) from the "reserve" terms so that they "work," creating $2^3$ subsets that "work" already. But for each of these, we have the option to add a $0$ from the reserve, so we now have $2\cdot2^3$ subsets that "work." For each of the $w(3)=4$ subsets of the first $3$ terms that "work", we can also add on a $\{1,2\}$ or a $\{1,2,0\}$ from the reserves, creating $2w(3)$ new subsets that "work." And that covers all of them. With all of this information, we can write $w(6)$ as \[w(6)=2\cdot2^3+2w(3)=2(2^3+w(3)).\] The same process can be used to calculate $w(9)$ then $w(12)$ etc. so we can generalize it to \[w(N)=2(2^{N-3}+w(N-3)).\] Thus, we calculate $w(18)$ with this formula: \[w(18)=2( 2^{15} + 2( 2^{12} + 2( 2^9 + 2( 2^6 + 2( 2^3 + 4 ) ) ) ) )=87424.\] Because there are $2^{18}$ total possible subsets, the desired probability is \[\frac{w(3)}{2^{18}}=\frac{87424}{2^{18}}=\frac{683}{2048},\] so the answer is $\boxed{683}.$

Solution 6

Try smaller cases and find a pattern. Using similar casework as in Solution 1, we can easily find the desired probability if $U$ is of a small size.

If $U = \{ 1,2,0\} \pmod 3$, then $4$ out of $8$ subsets work, for a probability of $\frac12$.

If $U = \{ 1,2,0,1,2,0\} \pmod 3$, then $24$ out of $64$ subsets work, for a probability of $\frac38$.

If $U = \{ 1,2,0,1,2,0,1,2,0\} \pmod 3$, then $176$ out of $512$ subsets work, for a probability of $\frac{11}{32}$.

Let $a_n$ be the numerator of the desired probability if $U$ is of size $3n$. Then $a_1 = 1, a_2 = 3,$ and $a_3 = 11$. Noticing that the denominators are multiplied by $4$ each time, we can conclude that the pattern of the numerators is $a_n = 4a_{n-1} - 1$, so $a_6 = \boxed{683}$.

Solution 7 (Quick guesswork for about 2 minutes remaining)

We conjecture that the difference from the probability will be as small as possible from 1/3

(The value approached as n-->infinity, where n is the number of terms in the largest subset.)


We also see that there are 2^18 subsets and know the denominator will be a power of 2 (since the numerator is an integer).

We essentially want to guess that the greatest integer n satisfying (2^n/3)-1 <1000 can be plugged in to get the solution of round(2^n/3)


We see that this occurs at n=11, and get round(2^11/3)=round(682.66...)= 683.

See Also

2018 AIME I (ProblemsAnswer KeyResources)
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