Difference between revisions of "1995 AIME Problems/Problem 3"
(solution) |
|||
| Line 1: | Line 1: | ||
== Problem == | == Problem == | ||
| − | Starting at <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 == | ||
| − | + | {{AIME box|year=1995|num-b=2|num-a=4}} | |
| − | + | ||
| − | + | [[Category:Intermediate Combinatorics Problems]] | |
Revision as of 13:48, 15 March 2008
Problem
Starting at 
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 
be the probability that the object reaches 
in six or fewer steps. Given that can be written in the form 
where 
and 
are relatively prime positive integers, find 
Solution
It takes an even number of steps for the object to reach , so the number of steps the object may have taken is either 
or 
.
If the object took steps, then it must have gone two steps N and two steps E, in some permutation. There are 
ways for these four steps of occuring, and the probability is 
.
If the object took 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 
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 
in four moves. There are 
ways to order those four steps and 
ways to determine the order of the remaining two steps, for a total of 
sequences that we have to exclude. This gives 
sequences of steps. There are the same number of sequences for the steps N,N,E,E,E,W, so the probability here is 
.
The total probability is 
, and 
.
See also
| 1995 AIME (Problems • Answer Key • Resources) | ||
| 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 | ||
