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:
Since the net movement must be two steps right () and two steps up (), there must be at least four steps. The point can be reached in exactly four steps if the sequence is some permutation of . These four steps can be permuted in
ways. Each of these sequences has probability of occurring. Thus the probability of reaching in exactly steps is .
In moving to , the total number of steps must be even, since an odd number of steps would reach a lattice point with one even coordinate and one odd coordinate. Next consider the possibility of reaching in six steps. A six-step sequence must include the steps in some order, as well as a pair consisting of (left) or (down), in some order. The steps can be permuted in
ways, but for of these sequences - namely those that start with some permutation of the object actually reaches in four steps. A similar analysis holds for the steps . Thus there are six-step sequences that reach , but that do not do so until the sixth step. Each of these sequences occurs with probability .
Considering the four- and six-step possibilities, we find that the probability of reaching in six or fewer steps is
Thus .
The problems on this page are the property of the MAA's American Mathematics Competitions