2010 AMC 12A Problems/Problem 18

Problem 18

A 16-step path is to go from $(-4,-4)$ to $(4,4)$ with each step increasing either the $x$ -coordinate or the $y$ -coordinate by 1. How many such paths stay outside or on the boundary of the square $-2 \le x \le 2$ , $-2 \le y \le 2$ at each step?

$\textbf{(A)}\ 92 \qquad \textbf{(B)}\ 144 \qquad \textbf{(C)}\ 1568 \qquad \textbf{(D)}\ 1698 \qquad \textbf{(E)}\ 12,800$

Brute Force Solution

The number of ways to reach any point $(x,y)$ on the grid is equal to the number of ways to reach $(x-1,y)$ plus the number of ways to reach $(x,y-1)$ . Using this recursion, we can draw the diagram and label each point with the number of ways to reach it and go up until we reach the end. Luckily, the figure is not so big that this is too time-consuming or difficult to do.