AMC8 2020

AMC8 2020 · Q21

AMC8 2020 · Q21. It mainly tests Recursion & DP style counting (basic), Coordinate geometry.

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.)

一个游戏棋盘由 $64$ 个方格组成，方格颜色在黑白之间交替。下面的图显示了底排的方格 $P$ 和顶排的方格 $Q$。标记放置在 $P$ 上。一歩操作是将标记移动到上方一行相邻的白方格之一。从 $P$ 到 $Q$ 有多少条 $7$ 步路径？（图中显示了一条示例路径。）

(A) 28 28

(B) 30 30

(D) 33 33

(E) 35 35

Answer

Correct choice: (A)

正确答案：（A）

Solution

Notice that, from one of the $1$ or $2$ white squares immediately beneath it (since the marker can only move on white squares). This means that the number of ways to move from $P$ to that square is the sum of the number of ways to move from $P$ to each of the white squares immediately beneath it (also called the Waterfall Method). 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 $P$ to that square, as already stated). The answer is therefore $\boxed{\textbf{(A) }28}$. Note: This is a classic example of a problem involving Pascal's triangle.

注意，每个白方格只能从其正下方的 $1$ 或 $2$ 个白方格到达（因为标记只能移动到白方格）。这意味着从 $P$ 到该方格的路径数是从 $P$ 到其正下方每个白方格路径数的总和（也称为瀑布方法）。为了解决问题，我们可以据此构建以下图表，其中每个方格中的数字是其正下方白方格数字的总和（从而表示从 $P$ 到该方格的路径数）。因此答案是 $\boxed{\textbf{(A) }28}$。注意：这是帕斯卡三角形问题的经典示例。

Topics