AIME 1995 · 第 3 题

AIME 1995 — Problem 3

专题: Contest Math
难度: L4
来源: AIME

题目详情

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