Yesterday, Manhattan GMAT posted a GMAT question on our blog. Today, they have followed up with the answer:
John has 4 options at each step, and he takes 4 successive steps, so there are 4×4×4×4 = 44 = 162 =256 possible outcomes. The harder calculation is to figure out how many of those outcomes bring him back to the origin. Since he must come back, any step he takes out must be undone at some point. For instance, if he takes a step Up, he must compensate later by taking a step Down before he’s done.
Perhaps the safest and ultimately quickest course is to start listing cases, then see whether you can generalize. Imagine that John takes his first step Up (U). Now, what happens on the second step is crucial.
(a) Second step is the same (another U). Then John has to get two Downs in a row.
There’s just 1 outcome: UUDD.
(b) Second step is the opposite of U (that is, a D). Then John can do anything on the third step, as long as he undoes that step on his fourth move.
There are 4 outcomes: UDUD, UDDU, UDLR, and UDRL.
(c) Second step is Left (L) or Right (R). Then John has to undo both the Up and the horizontal move, but he can undo them in either order.
There are 4 outcomes: ULDR, ULRD, URDL, and URLD.
So if John starts by walking Up, he has 9 outcomes that bring him back to the origin. Since the situation is symmetrical, the logic holds the same way for any of the other 3 starting directions. In all, there are 4×9 = 36 outcomes leading back to the origin.
Finally, the probability we’re looking for is 36/256 = 9/64.
The correct answer is B.
There’s not an obvious shortcut through this “case-listing” method. Notice that the case listing isn’t so bad, because we took advantage of symmetry. None of the four directions along the axes is fundamentally different from any other, so we can just pick Up as John’s first move, work out the 9 cases under that initial condition (staying organized as we go), then multiply by 4 to get the full 36 outcomes. There’s not a one-shot formula to get the answer, either.
By the way, John is taking a 2-dimensional “random walk.” Like last week’s problem, this week’s problem has echoes in the finance world, with various theorists arguing that securities prices take a “random walk” (or a modified version thereof) over time.