Difference between revisions of "1995 AIME Problems/Problem 3"

(solution)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
Starting at <math>\displaystyle (0,0),</math> an object moves in the coordinate plane via a sequence of steps, each of length one.  Each step is left, right, up, or down, all four equally likely.  Let <math>\displaystyle p</math> be the probability that the object reaches <math>\displaystyle (2,2)</math> in six or fewer steps.  Given that <math>\displaystyle p</math> can be written in the form <math>\displaystyle m/n,</math> where <math>\displaystyle m</math> and <math>\displaystyle n</math> are relatively prime positive integers, find <math>\displaystyle m+n.</math>
+
Starting at <math>(0,0),</math> an object moves in the [[coordinate plane]] via a sequence of steps, each of length one.  Each step is left, right, up, or down, all four equally likely.  Let <math>p</math> be the probability that the object reaches <math>(2,2)</math> in six or fewer steps.  Given that <math>p</math> can be written in the form <math>m/n,</math> where <math>m</math> and <math>n</math> are relatively prime positive integers, find <math>m+n.</math>
  
 
== Solution ==
 
== Solution ==
 +
It takes an even number of steps for the object to reach <math>(2,2)</math>, so the number of steps the object may have taken is either <math>4</math> or <math>6</math>.
 +
 +
If the object took <math>4</math> steps, then it must have gone two steps <tt>N</tt> and two steps <tt>E</tt>, in some permutation. There are <math>\frac{4!}{2!2!} = 6</math> ways for these four steps of occuring, and the probability is <math>\frac{6}{4^{4}}</math>.
 +
 +
If the object took <math>6</math> steps, then it must have gone two steps <tt>N</tt> and two steps <tt>E</tt>, and an additional pair of moves that would cancel out, either <tt>N/S</tt> or <tt>W/E</tt>. The sequences <tt>N,N,N,E,E,S</tt> can be permuted in <math>\frac{6!}{3!2!1!} = 60</math> ways. However, if the first four steps of the sequence are <tt>N,N,E,E</tt> in some permutation, it would have already reached the point <math>(0,0)</math> in four moves. There are <math>\frac{4!}{2!2!}</math> ways to order those four steps and <math>2!</math> ways to determine the order of the remaining two steps, for a total of <math>12</math> sequences that we have to exclude. This gives <math>60-12=48</math> sequences of steps. There are the same number of sequences for the steps <tt>N,N,E,E,E,W</tt>, so the probability here is <math>\frac{2 \times 48}{4^6}</math>.
 +
 +
The total probability is <math>\frac{6}{4^4} + \frac{96}{4^6} = \frac{3}{64}</math>, and <math>m+n= \boxed{067}</math>.
  
 
== See also ==
 
== See also ==
* [[1995_AIME_Problems/Problem_2|Previous Problem]]
+
{{AIME box|year=1995|num-b=2|num-a=4}}
* [[1995_AIME_Problems/Problem_4|Next Problem]]
+
 
* [[1995 AIME Problems]]
+
[[Category:Intermediate Combinatorics Problems]]

Revision as of 14:48, 15 March 2008

Problem

Starting at $(0,0),$ an object moves in the coordinate plane via a sequence of steps, each of length one. Each step is left, right, up, or down, all four equally likely. Let $p$ be the probability that the object reaches $(2,2)$ in six or fewer steps. Given that $p$ can be written in the form $m/n,$ where $m$ and $n$ are relatively prime positive integers, find $m+n.$

Solution

It takes an even number of steps for the object to reach $(2,2)$, so the number of steps the object may have taken is either $4$ or $6$.

If the object took $4$ steps, then it must have gone two steps N and two steps E, in some permutation. There are $\frac{4!}{2!2!} = 6$ ways for these four steps of occuring, and the probability is $\frac{6}{4^{4}}$.

If the object took $6$ steps, then it must have gone two steps N and two steps E, and an additional pair of moves that would cancel out, either N/S or W/E. The sequences N,N,N,E,E,S can be permuted in $\frac{6!}{3!2!1!} = 60$ ways. However, if the first four steps of the sequence are N,N,E,E in some permutation, it would have already reached the point $(0,0)$ in four moves. There are $\frac{4!}{2!2!}$ ways to order those four steps and $2!$ ways to determine the order of the remaining two steps, for a total of $12$ sequences that we have to exclude. This gives $60-12=48$ sequences of steps. There are the same number of sequences for the steps N,N,E,E,E,W, so the probability here is $\frac{2 \times 48}{4^6}$.

The total probability is $\frac{6}{4^4} + \frac{96}{4^6} = \frac{3}{64}$, and $m+n= \boxed{067}$.

See also

1995 AIME (ProblemsAnswer KeyResources)
Preceded by
Problem 2
Followed by
Problem 4
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions