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 3: better formating)
Line 2: Line 2:
 
For every subset <math>T</math> of <math>U = \{ 1,2,3,\ldots,18 \}</math>, let <math>s(T)</math> be the sum of the elements of <math>T</math>, with <math>s(\emptyset)</math> defined to be <math>0</math>. If <math>T</math> is chosen at random among all subsets of <math>U</math>, the probability that <math>s(T)</math> is divisible by <math>3</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>.
 
For every subset <math>T</math> of <math>U = \{ 1,2,3,\ldots,18 \}</math>, let <math>s(T)</math> be the sum of the elements of <math>T</math>, with <math>s(\emptyset)</math> defined to be <math>0</math>. If <math>T</math> is chosen at random among all subsets of <math>U</math>, the probability that <math>s(T)</math> is divisible by <math>3</math> is <math>\frac{m}{n}</math>, where <math>m</math> and <math>n</math> are relatively prime positive integers. Find <math>m</math>.
  
−
==Solution==
+
==Solution 1==
  
 
Consider the elements of <math>U</math> modulo <math>3.</math>
 
Consider the elements of <math>U</math> modulo <math>3.</math>
Line 28: Line 28:
 
By [[Combinatorial identity | Vandermonde's Identity]] on the second case, this is <math>2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}</math>
 
By [[Combinatorial identity | Vandermonde's Identity]] on the second case, this is <math>2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}</math>
  
−
==Solution 1==
+
==Solution 2 (Simple Casework)==
−
Rewrite the set after mod 3
+
 
 +
The question asks us for the probability that a randomly chosen subset of the set of the fist 18 positive integers has the property that the sum of its elements is divisible by 3. To simplify the problem, let’s convert the set to mod 3:
 +
 
 +
==Solution 3==
 +
Rewrite the set after mod 3 as above
  
 
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
Line 111: Line 115:
 
By SpecialBeing2017
 
By SpecialBeing2017
  
−
==Solution 2==
+
==Solution 4==
 
Consider the numbers <math>\{1,4,7,10,13,16\}</math>. Each of those are congruent to <math>1 \pmod 3</math>. There is <math>{6 \choose 0}=1</math> way to choose zero numbers <math>{6 \choose 1}=6</math> ways to choose <math>1</math> and so on. There ends up being  <math>{6 \choose 0}+{6 \choose 3}+{6 \choose 6} = 22</math> possible subsets congruent to <math>0\pmod 3</math>.  There are <math>2^6=64</math> possible subsets of these numbers. By symmetry there are <math>21</math> subsets each for <math>1 \pmod 3</math> and <math>2 \pmod3</math>.
 
Consider the numbers <math>\{1,4,7,10,13,16\}</math>. Each of those are congruent to <math>1 \pmod 3</math>. There is <math>{6 \choose 0}=1</math> way to choose zero numbers <math>{6 \choose 1}=6</math> ways to choose <math>1</math> and so on. There ends up being  <math>{6 \choose 0}+{6 \choose 3}+{6 \choose 6} = 22</math> possible subsets congruent to <math>0\pmod 3</math>.  There are <math>2^6=64</math> possible subsets of these numbers. By symmetry there are <math>21</math> subsets each for <math>1 \pmod 3</math> and <math>2 \pmod3</math>.
  
Line 120: Line 124:
 
So the probability is: <math>\frac{(22\cdot22+21\cdot21+21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math>
 
So the probability is: <math>\frac{(22\cdot22+21\cdot21+21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</math>
  
−
==Solution 3==
+
==Solution 5==
 
Notice that six numbers are <math>0\pmod3</math>, six are <math>1\pmod3</math>, and six are <math>2\pmod3</math>.  Having numbers <math>0\pmod3</math> will not change the remainder when <math>s(T)</math> is divided by <math>3</math>, so we can choose any number of these in our subset.  We ignore these for now.  The number of numbers that are <math>1\pmod3</math>, minus the number of numbers that are <math>2\pmod3</math>, must be a multiple of <math>3</math>, possibly zero or negative.  We can now split into cases based on how many numbers that are <math>1\pmod3</math> are in the set.
 
Notice that six numbers are <math>0\pmod3</math>, six are <math>1\pmod3</math>, and six are <math>2\pmod3</math>.  Having numbers <math>0\pmod3</math> will not change the remainder when <math>s(T)</math> is divided by <math>3</math>, so we can choose any number of these in our subset.  We ignore these for now.  The number of numbers that are <math>1\pmod3</math>, minus the number of numbers that are <math>2\pmod3</math>, must be a multiple of <math>3</math>, possibly zero or negative.  We can now split into cases based on how many numbers that are <math>1\pmod3</math> are in the set.
  
Line 131: Line 135:
 
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 <cmath>1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66\right)=1366\cdot2^6</cmath> 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 <cmath>\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</cmath>, 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 <cmath>1366\cdot\left(\binom60+\binom61+\binom62+\binom63+\binom64+\binom65+\binom66\right)=1366\cdot2^6</cmath> 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 <cmath>\frac{1366\cdot2^6}{2^{18}}=\frac{683}{2^{11}}</cmath>, so the answer is <math>\boxed{683}</math>.
  
−
==Solution 4==
+
==Solution 6==
 
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
 
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>
 
<cmath>\frac{1}{2}+\frac{1}{2}x^n.</cmath>
Line 147: Line 151:
 
Thus the answer is <math>\boxed{683}</math>.
 
Thus the answer is <math>\boxed{683}</math>.
  
−
==Solution 5==
+
==Solution 7==
 
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
 
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>
 
<cmath>\{1,2,0,1,2,0,1,2,0,1,2,0,1,2,0,1,2,0\}.</cmath>
Line 167: Line 171:
 
so the answer is <math>\boxed{683}.</math>
 
so the answer is <math>\boxed{683}.</math>
  
−
==Solution 6==
+
==Solution 8==
 
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.  
 
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.  
  
Line 178: Line 182:
 
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>.
 
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)==
+
==Solution 9 (Quick guesswork for about 2 minutes remaining)==
  
  

Revision as of 01:21, 5 December 2021

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

Consider the elements of $U$ modulo $3.$

Ignore the $0$'s because we're gonna multiply $\binom{6}{0}+..+\binom{6}{6}=2^6$ at the end. Let $a$ be the $1's$ and $b$ be the $2's$. The key here is that $2 \equiv -1 \pmod{3}$ so the difference between the number of $a$ and $b$ is a multiple of $3$.

1. Counted twice because $a$ and $b$ can be switched:

$6a$

$6a,3b$

$5a,2b$

$4a,b$

$3a$

2. Counted once:

$6a,6b$ ... $0a,0b$

By Vandermonde's Identity on the second case, this is $2^6 \left( 2\left(1+20+90+90+20\right) + \binom{12}{6} \right)\implies \boxed{683}$

Solution 2 (Simple Casework)

The question asks us for the probability that a randomly chosen subset of the set of the fist 18 positive integers has the property that the sum of its elements is divisible by 3. To simplify the problem, let’s convert the set to mod 3:

Solution 3

Rewrite the set after mod 3 as above

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 4

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+21\cdot21+21\cdot21)\cdot2^6}{2^{18}}=\frac{683}{2^{11}}$

Solution 5

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\]

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\]

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\]

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 6

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 7

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 8

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 9 (Quick guesswork for about 2 minutes remaining)

We conjecture that the difference from the probability will be as small as possible from $\frac{1}{3}$ (The value approached as $n \rightarrow \infty$ , 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 $\left(\frac{2^n}{3}\right)-1 <1000$ can be plugged in to get the solution of round $\left( \frac{2^n}{3} \right)$.


We see that this occurs at $n=11$, and get round $\left( \frac{2^{11}}{3} \right)=$round($682.66...$)= $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=167340"