2005 AIME I 第 13 题

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

小提示：

按每条部分路径的最后一步分类；向右的一步不能紧接在向上的一步之后，反之亦然

Classify each partial path by its last step; a rightward step may not immediately follow an upward one, and vice versa

大提示：

在每个格点记录三个计数：由对角、向右或向上的一步到达的路径数，然后从

(0,0)

开始填满

6 \times 6

网格

At each lattice point keep three counts — paths arriving by a diagonal, rightward, or upward step — and fill in the

6 \times 6

grid from

(0,0)

解答：

禁止直角转弯恰好表示：向右的一步绝不能紧接在向上的一步之后，反过来也一样；对角步可以出现在任何一步前后。因此在每个格点

(x, y)

记录三个计数

D(x,y)

，

R(x,y)

，

U(x,y)

：从

(0,0)

出发、以对角、向右或向上的一步到达该点的合法路径数。规则给出

\begin{aligned} D(x,y) &= D(x-1,y-1) \\ &\quad {}+ R(x-1,y-1) \\ &\quad {}+ U(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}\text{。}

从

(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(x-1,y-1) \\ &\quad {}+ R(x-1,y-1) \\ &\quad {}+ U(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 题