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 "2021 AMC 12B Problems/Problem 23"

(Created page with "==Problem 23== Three balls are randomly and independantly tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bi...")
 
(→‎Video Solution Using Infinite Geometric Series)
 
(40 intermediate revisions by 10 users not shown)
Line 1: Line 1:
−
==Problem 23==
+
==Problem==
 
Three balls are randomly and independantly tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>i</math> is <math>2^{-i}</math> for <math>i=1,2,3,....</math> More than one ball is allowed in each bin. The probability that the balls end up evenly spaced in distinct bins is <math>\frac pq,</math> where <math>p</math> and <math>q</math> are relatively prime positive integers. (For example, the balls are evenly spaced if they are tossed into bins <math>3,17,</math> and <math>10.</math>) What is <math>p+q?</math>
 
Three balls are randomly and independantly tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin <math>i</math> is <math>2^{-i}</math> for <math>i=1,2,3,....</math> More than one ball is allowed in each bin. The probability that the balls end up evenly spaced in distinct bins is <math>\frac pq,</math> where <math>p</math> and <math>q</math> are relatively prime positive integers. (For example, the balls are evenly spaced if they are tossed into bins <math>3,17,</math> and <math>10.</math>) What is <math>p+q?</math>
  
 
<math>\textbf{(A) }55 \qquad \textbf{(B) }56 \qquad \textbf{(C) }57\qquad \textbf{(D) }58 \qquad \textbf{(E) }59</math>
 
<math>\textbf{(A) }55 \qquad \textbf{(B) }56 \qquad \textbf{(C) }57\qquad \textbf{(D) }58 \qquad \textbf{(E) }59</math>
  
−
==Solution==
+
==Solution 1==
 
"Evenly spaced" just means the bins form an arithmetic sequence.
 
"Evenly spaced" just means the bins form an arithmetic sequence.
  
Line 10: Line 10:
 
<cmath>\begin{align*}
 
<cmath>\begin{align*}
 
6\sum_{x=2}^{\infty}\frac{x-1}{8^x} &= \frac{6}{8}\left[\frac{1}{8} + \frac{2}{8^2} + \frac{3}{8^3}\cdots\right]\\
 
6\sum_{x=2}^{\infty}\frac{x-1}{8^x} &= \frac{6}{8}\left[\frac{1}{8} + \frac{2}{8^2} + \frac{3}{8^3}\cdots\right]\\
−
&= \frac34\left[\left(\frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3}\right) + \left(\frac{1}{8^2} + \frac{1}{8^3} + \frac{1}{8^4}\right) + \cdots\right]\\
+
&= \frac34\left[\left(\frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3}+\cdots \right) + \left(\frac{1}{8^2} + \frac{1}{8^3} + \frac{1}{8^4} + \cdots \right) + \cdots\right]\\
−
&= \frac34\left[\frac17\cdot \left(1 + \frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3}\right)\right]\\
+
&= \frac34\left[\frac17\cdot \left(1 + \frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3} + \cdots \right)\right]\\
 
&= \frac34\cdot \frac{8}{49}\\
 
&= \frac34\cdot \frac{8}{49}\\
 
&= \frac{6}{49}
 
&= \frac{6}{49}
 
\end{align*}</cmath>
 
\end{align*}</cmath>
 
The answer is <math>6+49=\boxed{\textbf{(A) }55}.</math>
 
The answer is <math>6+49=\boxed{\textbf{(A) }55}.</math>
 +
 +
==Solution 2==
 +
As in solution 1, note that "evenly spaced" means the bins are in arithmetic sequence. We let the first bin be <math>a</math> and the common difference be <math>d</math>. Further note that each <math>(a, d)</math> pair uniquely determines a set of <math>3</math> bins.
 +
 +
We have <math>a\geq1</math> because the leftmost bin in the sequence can be any bin, and <math>d\geq1</math>, because the bins must be distinct.
 +
 +
This gives us the following sum for the probability:
 +
<cmath>\begin{align*} 6 \sum_{a=1}^{\infty} \sum_{d=1}^{\infty} 2^{-3a-3d}
 +
&= 6 \sum_{a=1}^{\infty} \sum_{d=1}^{\infty} 2^{-3a} \cdot 2^{-3d} \\
 +
&= 6 \left( \sum_{a=1}^{\infty} 2^{-3a} \right) \left( \sum_{d=1}^{\infty} 2^{-3d} \right) \\
 +
&= 6 \left( \sum_{a=1}^{\infty} 8^{-a} \right) \left( \sum_{d=1}^{\infty} 8^{-d} \right) \\
 +
&= 6 \left( \frac{1}{7} \right) \left( \frac{1}{7} \right) \\
 +
&= \frac{6}{49} .\end{align*}</cmath>
 +
Therefore the answer is <math>6 + 49 = \boxed{\textbf{(A) }55}</math>.
 +
 +
-Darren Yao
 +
 +
==Solution 3==
 +
This is a slightly messier variant of solution 2. If the first ball is in bin <math>i</math> and the second ball is in bin <math>j>i</math>, then the third ball is in bin <math>2j-i</math>. Thus the probability is
 +
<cmath>\begin{align*}
 +
6\sum_{i=1}^{\infty}\sum_{j=i+1}^\infty2^{-i}2^{-j}2^{-2j+i}&=6\sum_{i=1}^{\infty}\sum_{j=i+1}^\infty2^{-3j}\\
 +
&=6\sum_{i=1}^{\infty}\left(\frac{2^{-3(i+1)}}{1-\tfrac{1}{8}}\right)\\
 +
&=6\sum_{i=1}^\infty\frac{8}{7}\cdot2^{-3}\cdot2^{-3i}\\
 +
&=\frac{6}{7}\sum_{i=1}^\infty2^{-3i}\\
 +
&=\frac{6}{7}\cdot\frac{2^{-3}}{1-\tfrac18}\\
 +
&=\frac{6}{49}.
 +
\end{align*}</cmath>
 +
Therefore the answer is <math>6 + 49 = \boxed{\textbf{(A) }55}</math>.
 +
 +
==Solution 4 (Table)==
 +
Based on the value of <math>n,</math> we construct the following table:
 +
<cmath>\begin{array}{c|c|c|c}
 +
& & & \\ [-1.5ex]
 +
\textbf{Exactly }\boldsymbol{n}\textbf{ Spaces Apart} & \textbf{Bin \#s} & \textbf{Expression} & \textbf{Prob. of One Such Perm.} \\ [1ex]
 +
\hline\hline 
 +
& & & \\ [-1.5ex]
 +
n=1 & 1,2,3 & 2^{-1}\cdot2^{-2}\cdot2^{-3} & 2^{-6} \\ [1ex]
 +
& 2,3,4 & 2^{-2}\cdot2^{-3}\cdot2^{-4} & 2^{-9} \\ [1ex]
 +
& 3,4,5 & 2^{-3}\cdot2^{-4}\cdot2^{-5} & 2^{-12} \\ [1ex]
 +
& 4,5,6 & 2^{-4}\cdot2^{-5}\cdot2^{-6} & 2^{-15} \\ [1ex]
 +
& \cdots & \cdots & \cdots \\ [1ex]
 +
\hline
 +
& & & \\ [-1.5ex]
 +
n=2 & 1,3,5 & 2^{-1}\cdot2^{-3}\cdot2^{-5} & 2^{-9} \\ [1ex]
 +
& 2,4,6 & 2^{-2}\cdot2^{-4}\cdot2^{-6} & 2^{-12} \\ [1ex]
 +
& 3,5,7 & 2^{-3}\cdot2^{-5}\cdot2^{-7} & 2^{-15} \\ [1ex]
 +
& 4,6,8 & 2^{-4}\cdot2^{-6}\cdot2^{-8} & 2^{-18} \\ [1ex]
 +
& \cdots & \cdots & \cdots \\ [1ex]
 +
\hline
 +
& & & \\ [-1.5ex]
 +
n=3 & 1,4,7 & 2^{-1}\cdot2^{-4}\cdot2^{-7} & 2^{-12} \\ [1ex]
 +
& 2,5,8 & 2^{-2}\cdot2^{-5}\cdot2^{-8} & 2^{-15} \\ [1ex]
 +
& 3,6,9 & 2^{-3}\cdot2^{-6}\cdot2^{-9} & 2^{-18} \\ [1ex]
 +
& 4,7,10 & 2^{-4}\cdot2^{-7}\cdot2^{-10} & 2^{-21} \\ [1ex]
 +
& \cdots & \cdots & \cdots \\ [1ex]
 +
\hline
 +
& & & \\ [-1.5ex] 
 +
\cdots & \cdots & \cdots & \cdots \\ [1ex]
 +
\end{array}</cmath>
 +
Since three balls have <math>3!=6</math> permutations, the requested probability is
 +
<cmath>\begin{align*}
 +
6\left(\sum_{k=0}^{\infty}2^{-6-3k}+\sum_{k=0}^{\infty}2^{-9-3k}+\sum_{k=0}^{\infty}2^{-12-3k}+\cdots\right)&=6\left(2^{-6}\sum_{k=0}^{\infty}2^{-3k}+2^{-9}\sum_{k=0}^{\infty}2^{-3k}+2^{-12}\sum_{k=0}^{\infty}2^{-3k}+\cdots\right) \\
 +
&=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(2^{-6}+2^{-9}+2^{-12}+\cdots\right) \\
 +
&=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(\sum_{k=0}^{\infty}2^{-6-3k}\right) \\
 +
&=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(2^{-6}\sum_{k=0}^{\infty}2^{-3k}\right) \\
 +
&=\frac{6}{1-2^{-3}}\cdot\frac{2^{-6}}{1-2^{-3}} \\
 +
&=\frac{6}{49}
 +
\end{align*}</cmath>
 +
by infinite geometric series, from which the answer is <math>6+49=\boxed{\textbf{(A) }55}.</math>
 +
 +
~MRENTHUSIASM
 +
 +
== Video Solution==
 +
https://youtu.be/x16YUmd0OqY
 +
 +
~MathProblemSolvingSkills.com
 +
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/_IvLCWSSDFs
 +
 +
~ pi_is_3.14
 +
 +
== Video Solution Using Infinite Geometric Series ==
 +
https://youtu.be/3B-3_nOTIu4
 +
 +
~hippopotamus1
 +
 +
==See Also==
 +
{{AMC12 box|year=2021|ab=B|num-b=22|num-a=24}}
 +
{{MAA Notice}}

Latest revision as of 02:25, 28 January 2023

Problem

Three balls are randomly and independantly tossed into bins numbered with the positive integers so that for each ball, the probability that it is tossed into bin $i$ is $2^{-i}$ for $i=1,2,3,....$ More than one ball is allowed in each bin. The probability that the balls end up evenly spaced in distinct bins is $\frac pq,$ where $p$ and $q$ are relatively prime positive integers. (For example, the balls are evenly spaced if they are tossed into bins $3,17,$ and $10.$) What is $p+q?$

$\textbf{(A) }55 \qquad \textbf{(B) }56 \qquad \textbf{(C) }57\qquad \textbf{(D) }58 \qquad \textbf{(E) }59$

Solution 1

"Evenly spaced" just means the bins form an arithmetic sequence.

Suppose the middle bin in the sequence is $x$. There are $x-1$ different possibilities for the first bin, and these two bins uniquely determine the final bin. Now, the probability that these $3$ bins are chosen is $6\cdot 2^{-3x} = 6\cdot \frac{1}{8^x}$, so the probability $x$ is the middle bin is $6\cdot\frac{x-1}{8^x}$. Then, we want the sum \begin{align*} 6\sum_{x=2}^{\infty}\frac{x-1}{8^x} &= \frac{6}{8}\left[\frac{1}{8} + \frac{2}{8^2} + \frac{3}{8^3}\cdots\right]\\ &= \frac34\left[\left(\frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3}+\cdots \right) + \left(\frac{1}{8^2} + \frac{1}{8^3} + \frac{1}{8^4} + \cdots \right) + \cdots\right]\\ &= \frac34\left[\frac17\cdot \left(1 + \frac{1}{8} + \frac{1}{8^2} + \frac{1}{8^3} + \cdots \right)\right]\\ &= \frac34\cdot \frac{8}{49}\\ &= \frac{6}{49} \end{align*} The answer is $6+49=\boxed{\textbf{(A) }55}.$

Solution 2

As in solution 1, note that "evenly spaced" means the bins are in arithmetic sequence. We let the first bin be $a$ and the common difference be $d$. Further note that each $(a, d)$ pair uniquely determines a set of $3$ bins.

We have $a\geq1$ because the leftmost bin in the sequence can be any bin, and $d\geq1$, because the bins must be distinct.

This gives us the following sum for the probability: \begin{align*} 6 \sum_{a=1}^{\infty} \sum_{d=1}^{\infty} 2^{-3a-3d} &= 6 \sum_{a=1}^{\infty} \sum_{d=1}^{\infty} 2^{-3a} \cdot 2^{-3d} \\ &= 6 \left( \sum_{a=1}^{\infty} 2^{-3a} \right) \left( \sum_{d=1}^{\infty} 2^{-3d} \right) \\ &= 6 \left( \sum_{a=1}^{\infty} 8^{-a} \right) \left( \sum_{d=1}^{\infty} 8^{-d} \right) \\ &= 6 \left( \frac{1}{7} \right) \left( \frac{1}{7} \right) \\ &= \frac{6}{49} .\end{align*} Therefore the answer is $6 + 49 = \boxed{\textbf{(A) }55}$.

-Darren Yao

Solution 3

This is a slightly messier variant of solution 2. If the first ball is in bin $i$ and the second ball is in bin $j>i$, then the third ball is in bin $2j-i$. Thus the probability is \begin{align*} 6\sum_{i=1}^{\infty}\sum_{j=i+1}^\infty2^{-i}2^{-j}2^{-2j+i}&=6\sum_{i=1}^{\infty}\sum_{j=i+1}^\infty2^{-3j}\\ &=6\sum_{i=1}^{\infty}\left(\frac{2^{-3(i+1)}}{1-\tfrac{1}{8}}\right)\\ &=6\sum_{i=1}^\infty\frac{8}{7}\cdot2^{-3}\cdot2^{-3i}\\ &=\frac{6}{7}\sum_{i=1}^\infty2^{-3i}\\ &=\frac{6}{7}\cdot\frac{2^{-3}}{1-\tfrac18}\\ &=\frac{6}{49}. \end{align*} Therefore the answer is $6 + 49 = \boxed{\textbf{(A) }55}$.

Solution 4 (Table)

Based on the value of $n,$ we construct the following table: \[\begin{array}{c|c|c|c} & & & \\ [-1.5ex] \textbf{Exactly }\boldsymbol{n}\textbf{ Spaces Apart} & \textbf{Bin \#s} & \textbf{Expression} & \textbf{Prob. of One Such Perm.} \\ [1ex] \hline\hline & & & \\ [-1.5ex] n=1 & 1,2,3 & 2^{-1}\cdot2^{-2}\cdot2^{-3} & 2^{-6} \\ [1ex] & 2,3,4 & 2^{-2}\cdot2^{-3}\cdot2^{-4} & 2^{-9} \\ [1ex] & 3,4,5 & 2^{-3}\cdot2^{-4}\cdot2^{-5} & 2^{-12} \\ [1ex] & 4,5,6 & 2^{-4}\cdot2^{-5}\cdot2^{-6} & 2^{-15} \\ [1ex] & \cdots & \cdots & \cdots \\ [1ex] \hline & & & \\ [-1.5ex] n=2 & 1,3,5 & 2^{-1}\cdot2^{-3}\cdot2^{-5} & 2^{-9} \\ [1ex] & 2,4,6 & 2^{-2}\cdot2^{-4}\cdot2^{-6} & 2^{-12} \\ [1ex] & 3,5,7 & 2^{-3}\cdot2^{-5}\cdot2^{-7} & 2^{-15} \\ [1ex] & 4,6,8 & 2^{-4}\cdot2^{-6}\cdot2^{-8} & 2^{-18} \\ [1ex] & \cdots & \cdots & \cdots \\ [1ex] \hline & & & \\ [-1.5ex] n=3 & 1,4,7 & 2^{-1}\cdot2^{-4}\cdot2^{-7} & 2^{-12} \\ [1ex] & 2,5,8 & 2^{-2}\cdot2^{-5}\cdot2^{-8} & 2^{-15} \\ [1ex] & 3,6,9 & 2^{-3}\cdot2^{-6}\cdot2^{-9} & 2^{-18} \\ [1ex] & 4,7,10 & 2^{-4}\cdot2^{-7}\cdot2^{-10} & 2^{-21} \\ [1ex] & \cdots & \cdots & \cdots \\ [1ex] \hline & & & \\ [-1.5ex] \cdots & \cdots & \cdots & \cdots \\ [1ex] \end{array}\] Since three balls have $3!=6$ permutations, the requested probability is \begin{align*} 6\left(\sum_{k=0}^{\infty}2^{-6-3k}+\sum_{k=0}^{\infty}2^{-9-3k}+\sum_{k=0}^{\infty}2^{-12-3k}+\cdots\right)&=6\left(2^{-6}\sum_{k=0}^{\infty}2^{-3k}+2^{-9}\sum_{k=0}^{\infty}2^{-3k}+2^{-12}\sum_{k=0}^{\infty}2^{-3k}+\cdots\right) \\ &=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(2^{-6}+2^{-9}+2^{-12}+\cdots\right) \\ &=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(\sum_{k=0}^{\infty}2^{-6-3k}\right) \\ &=\left(6\sum_{k=0}^{\infty}2^{-3k}\right)\cdot\left(2^{-6}\sum_{k=0}^{\infty}2^{-3k}\right) \\ &=\frac{6}{1-2^{-3}}\cdot\frac{2^{-6}}{1-2^{-3}} \\ &=\frac{6}{49} \end{align*} by infinite geometric series, from which the answer is $6+49=\boxed{\textbf{(A) }55}.$

~MRENTHUSIASM

Video Solution

https://youtu.be/x16YUmd0OqY

~MathProblemSolvingSkills.com

Video Solution by OmegaLearn

https://youtu.be/_IvLCWSSDFs

~ pi_is_3.14

Video Solution Using Infinite Geometric Series

https://youtu.be/3B-3_nOTIu4

~hippopotamus1

See Also

2021 AMC 12B (Problems • Answer Key • Resources)
Preceded by
Problem 22 		Followed by
Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 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=2021_AMC_12B_Problems/Problem_23&oldid=188246"