Problem:
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≤x≤2,−2≤y≤2 at each step?
Answer Choices:
A. 92
B. 144
C. 1568
D. 1698
E. 12,800
Solution:
Each such path intersects the line y=−x at exactly one of the points (±4,∓4),(±3,∓3), or (±2,∓2). For j=0,1, and 2, the number of paths from (−4,4) to either of (±(4−j),∓(4−j)) is (j8), and the number of paths to (4,4) from either of (±(4−j),∓(4−j)) is the same. Therefore the number of paths that meet the requirement is 2((08)2+(18)2+(28)2)=2(12+82+282)= 1698.
The problems on this page are the property of the MAA's American Mathematics Competitions