Difference between revisions of "2003 AMC 12A Problems/Problem 22"
(→Solution) |
(→Solution 2 (Generating Functions)) |
||
(5 intermediate revisions by 5 users not shown) | |||
Line 11: | Line 11: | ||
</math> | </math> | ||
− | == Solution == | + | == Solution 1== |
− | If <math>A</math> and <math>B</math> meet, their paths connect <math>(0,0)</math> and <math>(5,7).</math> There are <math>\binom{12}{5}=792</math> such paths. Since the path is <math>12</math> units long, they must meet after each travels <math>6</math> units, so the probability is <math>\frac{792}{(2^{6} | + | If <math>A</math> and <math>B</math> meet, their paths connect <math>(0,0)</math> and <math>(5,7).</math> There are <math>\binom{12}{5}=792</math> such paths. Since the path is <math>12</math> units long, they must meet after each travels <math>6</math> units, so the probability is <math>\frac{792}{2^{6}\cdot 2^{6}} \approx 0.20 \Rightarrow \boxed{C}</math>. |
+ | |||
+ | Note: The number of paths, <math>\binom{12}{5}</math> 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 <math>\frac{12!}{5!7!}</math>, which is equivalent to <math>\binom{12}{5}</math>. | ||
+ | ~bearjere | ||
+ | |||
+ | == Solution 2 (Generating Functions) == | ||
+ | |||
+ | We know that the sum of the vertical steps must be equal to <math>7</math>. We also know that they must take <math>6</math> steps each. Since moving vertically or horizontally is equally likely, we can write all the possible paths as a generating function: | ||
+ | |||
+ | <cmath>P(x)=(x+1)^{12}</cmath> | ||
+ | |||
+ | Where we need to extract the <math>x^5</math> coefficient. By the binomial coefficient theorem, that term is <math>\binom{12}{5}=792</math> paths. Since there are also <math>2^{12}</math> paths, we have: | ||
+ | |||
+ | <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
Contents
[hide]Problem
Objects and
move simultaneously in the coordinate plane via a sequence of steps, each of length one. Object
starts at
and each of its steps is either right or up, both equally likely. Object
starts at
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?
Solution 1
If and
meet, their paths connect
and
There are
such paths. Since the path is
units long, they must meet after each travels
units, so the probability is
.
Note: The number of paths, 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
, which is equivalent to
.
~bearjere
Solution 2 (Generating Functions)
We know that the sum of the vertical steps must be equal to . We also know that they must take
steps each. Since moving vertically or horizontally is equally likely, we can write all the possible paths as a generating function:
Where we need to extract the coefficient. By the binomial coefficient theorem, that term is
paths. Since there are also
paths, we have:
Solution 3 (Alcumus)
Since there are twelve steps between and
,
and
can meet only after they have each moved six steps. The possible meeting places are
,
,
,
,
, and
. Let
and
denote the number of paths to
from
and
, respectively. Since
has to take
steps to the right and
has to take
steps down, the number of ways in which
and
can meet at
is
Since
and
can each take
paths in six steps, the probability that they meet is
walks that start at
, end at
, 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
-paths where
and
meet. In particular, given one of the
walks from
to
, the path followed by
consists of the first six steps of the walk, and the path followed by
is obtained by starting at
and reversing the last six steps of the walk. There are
paths that take 6 steps from
and
paths that take 6 steps from
, so there are
pairs of paths that
and
can take. The probability that they meet is
, so the answer is
.
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.