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 "1995 AIME Problems/Problem 3"
(→‎Solution)
Line 2: Line 2:
 
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>
 
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 1 ==
 
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>.
 
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>.
  
Line 10: Line 10:
  
 
The total probability is <math>\frac{6}{4^4} + \frac{96}{4^6} = \frac{3}{64}</math>, and <math>m+n= \boxed{067}</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>.
 +
 +
== Solution 2 ==
 +
 +
Let's let the object wander for 6 steps so we get a constant denominator of <math>4^{6}</math>
 +
 +
First we count how many ways the object can end at 2,2, at the end of 6 steps. We will also count it even if we go to 2,2, and go back to 2,2. So, there are 2 ways for the object to end at 2,2. To go a permutation of R,R,R,U,U,L or a permutation of R,R,U,U,U,D. There are 60 ways to permute for each case, giving a total of 120 ways for the object to succeed and end at 2,2.
 +
 +
But, the object can also get to 2,2, then move away. That is also a possible way the object can move. So, there are 6 ways to get to 2,2 in 4 moves, then there are 16 ways the object can "move around", but 4 of the ways will return the object back to 2,2. Those ways were already counted in the first case, so we should only count 12 ways to prevent over-counting. Thus, there are <math>12*6 = </math> 72 ways in the second case.
 +
 +
So, in all, there are 120+72 ways for the object to achieve it's goal of moving to 2,2. Put that over our denominator, we get <math>\frac{192}{4^{6}} = \frac{3}{4^{3}} = \frac{3}{64}</math>, in which adding the numerator and denominator get us an answer of <math>\boxed{067}</math>
 +
 +
 +
- AlexLikeMath
  
 
== See also ==
 
== See also ==

Revision as of 22:46, 15 June 2019

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 1

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 $(2,2)$ 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}$.

Solution 2

Let's let the object wander for 6 steps so we get a constant denominator of $4^{6}$

First we count how many ways the object can end at 2,2, at the end of 6 steps. We will also count it even if we go to 2,2, and go back to 2,2. So, there are 2 ways for the object to end at 2,2. To go a permutation of R,R,R,U,U,L or a permutation of R,R,U,U,U,D. There are 60 ways to permute for each case, giving a total of 120 ways for the object to succeed and end at 2,2.

But, the object can also get to 2,2, then move away. That is also a possible way the object can move. So, there are 6 ways to get to 2,2 in 4 moves, then there are 16 ways the object can "move around", but 4 of the ways will return the object back to 2,2. Those ways were already counted in the first case, so we should only count 12 ways to prevent over-counting. Thus, there are $12*6 =$ 72 ways in the second case.

So, in all, there are 120+72 ways for the object to achieve it's goal of moving to 2,2. Put that over our denominator, we get $\frac{192}{4^{6}} = \frac{3}{4^{3}} = \frac{3}{64}$, in which adding the numerator and denominator get us an answer of $\boxed{067}$


- AlexLikeMath

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

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=1995_AIME_Problems/Problem_3&oldid=106391"