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 "2003 AMC 12A Problems/Problem 22"

(Note on extra step that might not be obvious)
(→‎Solution 2 (Generating Functions))
 
Line 27: Line 27:
  
 
<math>\frac{792}{2^{12}}=\frac{792}{4096}\approx\frac{800}{4000}\approx\boxed{\text{(C) } 0.20}</math>
 
<math>\frac{792}{2^{12}}=\frac{792}{4096}\approx\frac{800}{4000}\approx\boxed{\text{(C) } 0.20}</math>
 +
 +
== Solution 3 (Alcumus) ==
 +
Since there are twelve steps between <math>(0,0)</math> and <math>(5,7)</math>, <math>A</math> and <math>B</math> can meet only after they have each moved six steps. The possible meeting places are <math>P_{0} = (0,6)</math>, <math>P_{1} = (1,5)</math>, <math>P_{2} = (2,4)</math>, <math>P_{3}=(3,3)</math>, <math>P_{4} = (4,2)</math>, and <math>P_{5} =
 +
(5,1)</math>. Let <math>a_{i}</math> and <math>b_{i}</math> denote the number of paths to <math>P_{i}</math> from <math>(0,0)</math> and <math>(5,7)</math>, respectively. Since <math>A</math> has to take <math>i</math> steps to the right and <math>B</math> has to take <math>i+1</math> steps down, the number of ways in which <math>A</math> and <math>B</math> can meet at <math>P_{i}</math> is<cmath>a_{i}\cdot b_{i} = \binom{6}{i} \binom{6}{i+1}. </cmath>Since <math>A</math> and <math>B</math> can each take <math>2^{6}</math> paths in six steps, the probability that they meet is\begin{align*}
 +
&\sum_{i = 0}^{5}\displaystyle\left ( \frac{a_{i}}{2^{6}}\displaystyle\right)\displaystyle\left( \frac{b_{i}}{2^{6}} \displaystyle\right) \\
 +
& \qquad = \frac{\binom{6}{0}\binom{6}{1} + \binom{6}{1}\binom{6}{2} + \binom{6}{2}\binom{6}{3}
 +
+ \binom{6}{3}\binom{6}{4}+ \binom{6}{4}\binom{6}{5} + \binom{6}{5}\binom{6}{6}}{2^{12}}\\
 +
& \qquad = \frac{99}{512} \\
 +
& \qquad \approx \boxed{0.20}.
 +
\end{align*}
 +
Solution 2:
 +
Consider the <math>\binom{12}{5}</math> walks that start at <math>(0,0)</math>, end at <math>(5,7)</math>, and consist of 12 steps, each one either up or to the right. There is a one-to-one correspondence between these walks and the set of <math>(A,B)</math>-paths where <math>A</math> and <math>B</math> meet. In particular, given one of the <math>\binom{12}{5}</math> walks from <math>(0,0)</math> to <math>(5,7)</math>, the path followed by <math>A</math> consists of the first six steps of the walk, and the path followed by <math>B</math> is obtained by starting at <math>(5,7)</math> and reversing the last six steps of the walk. There are <math>2^{6}</math> paths that take 6 steps from <math>(0,0)</math> and <math>2^{6}</math> paths that take 6 steps from <math>(5,7)</math>, so there are <math>2^{12}</math> pairs of paths that <math>A</math> and <math>B</math> can take. The probability that they meet is\begin{align*}
 +
P&=\frac{1}{2^{12}}\binom{12}{5}\\
 +
&=\frac{1}{2^{12}}\frac{12\cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\
 +
&=\frac{99}{2^9}.\\
 +
\end{align*}This is approximately <math>0.20</math>, so the answer is <math>\boxed{C}</math>.
  
 
== See Also ==
 
== See Also ==

Latest revision as of 00:46, 30 November 2024

Problem

Objects $A$ and $B$ move simultaneously in the coordinate plane via a sequence of steps, each of length one. Object $A$ starts at $(0,0)$ and each of its steps is either right or up, both equally likely. Object $B$ starts at $(5,7)$ and each of its steps is either to the left or down, both equally likely. Which of the following is closest to the probability that the objects meet?

$\mathrm{(A)} \ 0.10 \qquad \mathrm{(B)} \ 0.15 \qquad \mathrm{(C)} \ 0.20 \qquad \mathrm{(D)} \ 0.25 \qquad \mathrm{(E)} \ 0.30 \qquad$

Solution 1

If $A$ and $B$ meet, their paths connect $(0,0)$ and $(5,7).$ There are $\binom{12}{5}=792$ such paths. Since the path is $12$ units long, they must meet after each travels $6$ units, so the probability is $\frac{792}{2^{6}\cdot 2^{6}} \approx 0.20 \Rightarrow \boxed{C}$.

Note: The number of paths, $\binom{12}{5}$ comes from the fact that there must be 5 ups/downs and 7 lefts/rights in one path. WLOG, for Object A, the number of paths would be the amount of combinations of the sequence of letters with 5 "U"s 7 "R"s (i.e. UUUUURRRRRRR). This is $\frac{12!}{5!7!}$, which is equivalent to $\binom{12}{5}$. ~bearjere

Solution 2 (Generating Functions)

We know that the sum of the vertical steps must be equal to $7$. We also know that they must take $6$ steps each. Since moving vertically or horizontally is equally likely, we can write all the possible paths as a generating function:

\[P(x)=(x+1)^{12}\]

Where we need to extract the $x^5$ coefficient. By the binomial coefficient theorem, that term is $\binom{12}{5}=792$ paths. Since there are also $2^{12}$ paths, we have:

$\frac{792}{2^{12}}=\frac{792}{4096}\approx\frac{800}{4000}\approx\boxed{\text{(C) } 0.20}$

Solution 3 (Alcumus)

Since there are twelve steps between $(0,0)$ and $(5,7)$, $A$ and $B$ can meet only after they have each moved six steps. The possible meeting places are $P_{0} = (0,6)$, $P_{1} = (1,5)$, $P_{2} = (2,4)$, $P_{3}=(3,3)$, $P_{4} = (4,2)$, and $P_{5} = (5,1)$. Let $a_{i}$ and $b_{i}$ denote the number of paths to $P_{i}$ from $(0,0)$ and $(5,7)$, respectively. Since $A$ has to take $i$ steps to the right and $B$ has to take $i+1$ steps down, the number of ways in which $A$ and $B$ can meet at $P_{i}$ is\[a_{i}\cdot b_{i} = \binom{6}{i} \binom{6}{i+1}.\]Since $A$ and $B$ can each take $2^{6}$ paths in six steps, the probability that they meet is\begin{align*} &\sum_{i = 0}^{5}\displaystyle\left ( \frac{a_{i}}{2^{6}}\displaystyle\right)\displaystyle\left( \frac{b_{i}}{2^{6}} \displaystyle\right) \\ & \qquad = \frac{\binom{6}{0}\binom{6}{1} + \binom{6}{1}\binom{6}{2} + \binom{6}{2}\binom{6}{3} + \binom{6}{3}\binom{6}{4}+ \binom{6}{4}\binom{6}{5} + \binom{6}{5}\binom{6}{6}}{2^{12}}\\ & \qquad = \frac{99}{512} \\ & \qquad \approx \boxed{0.20}. \end{align*} Solution 2: Consider the $\binom{12}{5}$ walks that start at $(0,0)$, end at $(5,7)$, and consist of 12 steps, each one either up or to the right. There is a one-to-one correspondence between these walks and the set of $(A,B)$-paths where $A$ and $B$ meet. In particular, given one of the $\binom{12}{5}$ walks from $(0,0)$ to $(5,7)$, the path followed by $A$ consists of the first six steps of the walk, and the path followed by $B$ is obtained by starting at $(5,7)$ and reversing the last six steps of the walk. There are $2^{6}$ paths that take 6 steps from $(0,0)$ and $2^{6}$ paths that take 6 steps from $(5,7)$, so there are $2^{12}$ pairs of paths that $A$ and $B$ can take. The probability that they meet is\begin{align*} P&=\frac{1}{2^{12}}\binom{12}{5}\\ &=\frac{1}{2^{12}}\frac{12\cdot 11 \cdot 10 \cdot 9 \cdot 8}{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}\\ &=\frac{99}{2^9}.\\ \end{align*}This is approximately $0.20$, so the answer is $\boxed{C}$.

See Also

2003 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 21 		Followed by
Problem 23
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=2003_AMC_12A_Problems/Problem_22&oldid=235869"