Question

A particle moves in the Cartesian plane from one lattice point to another according to the following rules:

• From any lattice point $(a, b),$ the particle may move only to $(a+1, b),$ $(a, b+1),$ or $(a+1, b+1).$

• There are no right angle turns in the particle's path. That is, the sequence of points visited contains neither a subsequence of the form $(a, b),$ $(a+1, b),$ $(a+1, b+1)$ nor a subsequence of the form $(a, b),$ $(a, b+1),$ $(a+1, b+1).$

How many different paths can the particle take from $(0, 0)$ to $(5, 5)?$

Answer

Answer: 83

Concepts:lattice paths recursive counting

Difficulty rating: 3060

Solution:

The forbidden right-angle turns say exactly that a rightward step may never immediately follow an upward step, and vice versa; a diagonal step may follow or precede anything. So at each lattice point $(x, y)$ track three counts $D(x,y),$ $R(x,y),$ $U(x,y):$ the numbers of legal paths from $(0,0)$ arriving there by a diagonal, rightward, or upward step. The rules give $\begin{aligned} &D(x,y) = D + R \\ &\quad {}+ U \text{ at } (x-1, y-1), \\ &R(x,y) = D(x-1,y) \\ &\quad {}+ R(x-1,y), \\ &U(x,y) = D(x,y-1) \\ &\quad {}+ U(x,y-1). \end{aligned}$

Starting from the single empty path at $(0,0)$ (which may begin with any step), fill in the grid up to $(5,5).$ Along the axes only all-rightward or all-upward paths survive, and the interior builds up quickly; at $(5, 5)$ the three counts come out to $27,$ $28,$ and $28.$

The total number of paths is $27 + 28 + 28 = 83.$

2005 AIME I Problem 13

Answer: 83

Difficulty rating: 3060

Solution:

Problem 13 in Other Years