Track / Stage 3 / 250 of 260 #250 of 1964

Problem 250

AMC 10/12, early questions

Combinatorics Difficulty 3.9 Multiple choice

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?

Pick one

Official solution

Each path must go through either the second or the fourth quadrant.
Each path that goes through the second quadrant must pass through exactly one of the points $(-4,4)$ , $(-3,3)$ , and $(-2,2)$ .
There is $1$ path of the first kind, ${8\choose 1}^2=64$ paths of the second kind, and ${8\choose 2}^2=28^2=784$ paths of the third type.
Each path that goes through the fourth quadrant must pass through exactly one of the points $(4,-4)$ , $(3,-3)$ , and $(2,-2)$ .
Again, there is $1$ path of the first kind, ${8\choose 1}^2=64$ paths of the second kind, and ${8\choose 2}^2=28^2=784$ paths of the third type.
Hence the total number of paths is $2(1+64+784) = \boxed{1698}$ .

Source: NuminaMath-1.5, licensed Apache-2.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.