2020 AMC 8 Problems/Problem 21
Problem
A game board consists of 
squares that alternate in color between black and white. The figure below shows square 
in the bottom row and square 
in the top row. A marker is placed at 
A step consists of moving the marker onto one of the adjoining white squares in the row above. How many 
-step paths are there from to 
(The figure shows a sample path.)
![[asy]//diagram by SirCalcsALot size(200); int[] x = {6, 5, 4, 5, 6, 5, 6}; int[] y = {1, 2, 3, 4, 5, 6, 7}; int N = 7; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } for (int i = 0; i < N; ++i) { draw(circle((x[i],y[i])+(0.5,0.5),0.35)); } label("$P$", (5.5, 0.5)); label("$Q$", (6.5, 7.5)); [/asy]](http://latex.artofproblemsolving.com/2/1/0/210b98fc88e4c297773b0400a31787193c0d4338.png)
Solution 1
Notice that, in order to step onto any particular white square, the marker must have come from one of the 
or 
white squares immediately beneath it (since the marker can only move on white squares). This means that the number of ways to move from to that square is the sum of the numbers of ways to move from to each of the white squares immediately beneath it. To solve the problem, we can accordingly construct the following diagram, where each number in a square is calculated as the sum of the numbers on the white squares immediately beneath that square (and thus will represent the number of ways to remove from to that square, as already stated).
![[asy] int N = 7; for (int i = 0; i < 8; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } label("$1$", (5.5, .5)); label("$1$", (4.5, 1.5)); label("$1$", (6.5, 1.5)); label("$1$", (3.5, 2.5)); label("$1$", (7.5, 2.5)); label("$2$", (5.5, 2.5)); label("$1$", (2.5, 3.5)); label("$3$", (6.5, 3.5)); label("$3$", (4.5, 3.5)); label("$4$", (3.5, 4.5)); label("$3$", (7.5, 4.5)); label("$6$", (5.5, 4.5)); label("$10$", (4.5, 5.5)); label("$9$", (6.5, 5.5)); label("$19$", (5.5, 6.5)); label("$9$", (7.5, 6.5)); label("$28$", (6.5, 7.5)); [/asy]](http://latex.artofproblemsolving.com/3/8/d/38df398e31d5f4a69999da41b16ceb51aef50425.png)
The answer is therefore 
.
Solution 2
Suppose we "extend" the chessboard infinitely with additional columns to the right, as shown below. The red line shows the right-hand edge of the original board.
![[asy] int N = 7; for (int i = 0; i < 10; ++i) { for (int j = 0; j < 8; ++j) { draw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)); if ((i+j) % 2 == 0) { filldraw((i,j)--(i+1,j)--(i+1,j+1)--(i,j+1)--(i,j)--cycle,black); } } } draw((8,0) -- (8,8),red); label("$P$", (5.5,.5)); label("$Q$", (6.5,7.5)); label("$X$", (8.5,3.5)); label("$Y$", (8.5,5.5)); [/asy]](http://latex.artofproblemsolving.com/2/1/1/211bd95d19c4750245aab388d7d737af5fcdffbe.png)
The total number of paths from to , including invalid paths which cross over the red line, is then the number of paths which make 
steps up-and-right and 
steps up-and-left, which is 
. We need to subtract the number of invalid paths, i.e. the number of paths that pass through 
or 
. To get to , the marker has to make up-and-right steps, after which it can proceed to with steps up-and-left and step up-and-right. Thus, the number of paths from to that pass through is 
. Similarly, the number of paths that pass through is 
. However, we have now double-counted the invalid paths which pass through both and ; from the diagram, it is clear that there are only of these (as the marker can get from to by a step up-and-left and a step-up-and-right in either order). Hence the number of invalid paths is 
, and the number of valid paths from to is 
.
Video Solutions
See also
| 2020 AMC 8 (Problems • Answer Key • Resources) | ||
| Preceded by Problem 20 |
Followed by Problem 22 | |
| 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 | ||
| All AJHSME/AMC 8 Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
