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"
m (→‎Solution 2)
 
(6 intermediate revisions by 6 users not shown)
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 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>.
 +
 
 +
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>(2,2)</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>.
 +
 
 +
== Solution 2 ==
 +
 
 +
Let's let the object wander for 6 steps so we get a constant denominator of <math>4^{6}</math>
 +
 
 +
In the first case, 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 different paths for the object to end at (2,2):
 +
 
 +
1.To go a permutation of R,R,R,U,U,L or
 +
 
 +
2.To go 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). In these 120 ways the object could reach (2,2) first and then come back to (2,2). This will be a factor in our second case.
 +
 
 +
In the second case, the object can get to (2,2) first in 4 moves, then move away from (2,2) with the remaing 2 moves. 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 4 ways were already counted in the first case, so we should only count 12 of the 16 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 ==
−
* [[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]]
 +
{{MAA Notice}}

Latest revision as of 22:15, 16 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}$

In the first case, 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 different paths for the object to end at (2,2):

1.To go a permutation of R,R,R,U,U,L or

2.To go 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). In these 120 ways the object could reach (2,2) first and then come back to (2,2). This will be a factor in our second case.

In the second case, the object can get to (2,2) first in 4 moves, then move away from (2,2) with the remaing 2 moves. 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 4 ways were already counted in the first case, so we should only count 12 of the 16 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=106465"