Question

一个粒子在笛卡尔平面内从一个格点移动到另一个格点，规则如下：

• 从任意格点 $(a, b)$ ，粒子只能移动到 $(a+1, b)$ ， $(a, b+1)$ ，或 $(a+1, b+1)$ 。

• 粒子的路径中没有直角转弯。也就是说，访问过的点列中既不包含形如 $(a, b)$ ， $(a+1, b)$ ， $(a+1, b+1)$ 的子序列，也不包含形如 $(a, b)$ ， $(a, b+1)$ ， $(a+1, b+1)$ 的子序列。

粒子从 $(0, 0)$ 到 $(5, 5)$ 可以走多少条不同路径？

A particle moves in the Cartesian plane from one lattice point to another according to the following rules:

• From any lattice point $(a, b),$ the particle may move only to $(a+1, b),$ $(a, b+1),$ or $(a+1, b+1).$

• There are no right angle turns in the particle's path. That is, the sequence of points visited contains neither a subsequence of the form $(a, b),$ $(a+1, b),$ $(a+1, b+1)$ nor a subsequence of the form $(a, b),$ $(a, b+1),$ $(a+1, b+1).$

How many different paths can the particle take from $(0, 0)$ to $(5, 5)?$

答案

答案：83

知识点：格路递推计数

难度评级：3060

解答：

禁止直角转弯恰好表示：向右的一步绝不能紧接在向上的一步之后，反过来也一样；对角步可以跟在任何步之后或之前。因此在每个格点 $(x, y)$ 记录三个计数 $D(x,y)$ ， $R(x,y)$ ， $U(x,y)$ ：从 $(0,0)$ 出发、以对角、向右或向上的一步到达该点的合法路径数。规则给出 $\begin{aligned} &D(x,y) = D + R \\ &\quad {}+ U \text{ at } (x-1, y-1), \\ &R(x,y) = D(x-1,y) \\ &\quad {}+ R(x-1,y), \\ &U(x,y) = D(x,y-1) \\ &\quad {}+ U(x,y-1). \end{aligned}$

从 $(0,0)$ 处唯一的空路径开始（它可以从任意一步开始），填表直到 $(5,5)$ 。在坐标轴上，只有全向右或全向上的路径保留下来；内部的计数会快速累积。在 $(5, 5)$ 处，三个计数分别为 $27$ ， $28$ ，和 $28$ 。

路径总数为 $27 + 28 + 28 = 83$ 。

The forbidden right-angle turns say exactly that a rightward step may never immediately follow an upward step, and vice versa; a diagonal step may follow or precede anything. So at each lattice point $(x, y)$ track three counts $D(x,y),$ $R(x,y),$ $U(x,y):$ the numbers of legal paths from $(0,0)$ arriving there by a diagonal, rightward, or upward step. The rules give $\begin{aligned} &D(x,y) = D + R \\ &\quad {}+ U \text{ at } (x-1, y-1), \\ &R(x,y) = D(x-1,y) \\ &\quad {}+ R(x-1,y), \\ &U(x,y) = D(x,y-1) \\ &\quad {}+ U(x,y-1). \end{aligned}$

Starting from the single empty path at $(0,0)$ (which may begin with any step), fill in the grid up to $(5,5).$ Along the axes only all-rightward or all-upward paths survive, and the interior builds up quickly; at $(5, 5)$ the three counts come out to $27,$ $28,$ and $28.$

The total number of paths is $27 + 28 + 28 = 83.$

2005 AIME I 第 13 题

答案：83

难度评级：3060

解答：

其他年份的第 13 题