Competition problem — Combinatorics

Library / /436 of 520

Combinatorics Difficulty 3.9 AMC 10/12 Find the answer

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

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}$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.