A game board consists of 64 squares that alternate in color between black and white. The figure below shows square $P$ in the bottom row and square $Q$ in the top row. A marker is placed at $P$. A step consists of moving the marker onto one of the adjoining white squares in the row above. How many 7-step paths are there from $P$ to $Q$? (The figure shows a sample path.)

A. 28

B. 30

C. 32

D. 33

E. 35

1. 2020 AMC 8 官方解析

Beginning with the row above $P$ and flling in one row at a time, the number of paths that lead from $P$ to each square can be counted, as shown in the figure below. (Squares that cannot be reached or do not lead to $Q$ in 7 moves are left blank.) Note that the number of paths leading to a square equals the sum of the counts in the adjoining squares below it. (For example, to reach the square with 10 paths, it is necessary to pass through one of the adjoining squares below; they have 4 and 6 paths leading to them, respectively.) Applying this counting method to each row, moving up from the bottom, results in a total of 28 seven-step paths from $P$ to $Q$.

从$P$上方的行开始，一次填充一行，可以计算出从$P$到每个正方形的路径数，如下图所示.（无法到达或无法使其在7步之内移动到$Q$的小正方形留空白.）可以看出，通向一个正方形的路径数等于其下方相邻正方形中计数的总和.（例如，要到达具有10个路径数的正方形，必须穿过与其正下方的正方形相邻的一个正方形；它们部分的路径数分别为4和6.）将此计数方法应用于每一行，从底部开始移动，可以得出从$P$到$Q$总共有28个七步路径.

Each step moves the marker either one column to the left ($L$) or one column to the right ($R$). Because $Q$ is one column to the right of $P$, each path must consist of 4 moves to the right and 3 moves to the left. Ignoring the possibility that a path may extend past the right edge of the board, the number of paths from $P$ to $Q$ is equivalent to the number of distinguishable permutations of $RRRRLLL$, which equals the number of combinations of 7 objects taken 4 at atime: $C_7^4 = \binom{7}{4} = \frac{7!}{4!3!} = 35$. This total, however, includes paths that move the marker off the right edge of the board. One such path is shown below. A path leaves the board when the number of $R$ moves exceeds the number of L moves by 3. There are 7 paths that extend beyond the board: $LRRRRLL$, $RLRRRLL$, $RRLRRLL$, and the 4 paths that begin with $RRR$. Removing these 7 paths leaves $35 - 7 = 28$ seven-step paths from $P$ to $Q$.