AMC 8 2020 Problem 21
AMC8 2020 年第 21 题
递推★★★☆☆
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
- B.30
- C.32
- D.33
- E.35
正确答案 · Correct Answer
A
解析 · Solution
Solution 1
On any white square, we may choose to go left or right, as long as we do not cross over the border of the board. Call the moves and respectively. Every single legal path consists of 4 R's and 3 L's, so now all we have to find is the number of ways to order 4 R's and 3 L's in any way, which is . However, we originally promised that we will not go over the border, and now we have to subtract the paths that do go over the border. The paths that go over the border are any paths that start with RRR(1 path), RR(5 paths) and LRRR(1 path) so our final number of paths is 35-7=28.: Intuitive Approach We label the rows starting from the bottom. At row 1, there is 1 way: at P. We draw all the possible ways to get to Q. There are two ways to choose for row 2, and another two ways to choose for row 3. However, you can go to the "edge" or the farthest possible square westward of Q, so you can't multiply by 2 again. Notice how, at the first step, we figured that the answer was even, so choice D and E are eliminated, and after the second row, we realized it must be a multiple of 4, so choice B is eliminated. When we get to the fourth row, we do not multiply by 2 again, since we have limited possibilities rather than multiplying by 2 again. Choice C implies that there are two possibilities per row; however, we know that if you go to the farthest possible, you only have one possibility, so it is not so we know that the answer is choice.
继续练习