2008 USAMO 第 3 题

Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that

$$\left|x\right| + \left|y + \frac {1}{2}\right| < n$$

A path is a sequence of distinct points $(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots , \ell$, the distance between $(x_i , y_i )$ and $(x_{i - 1} , y_{i - 1} )$ is $1$ (in other words, the points $(x_i , y_i )$ and $(x_{i - 1} , y_{i - 1} )$ are neighbors in the lattice of points with integer coordinates). Prove that the points in $S_n$ cannot be partitioned into fewer than $n$ paths (a partition of $S_n$ into $m$ paths is a set $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$).

令 $n$ 为正整数。用 $S_n$ 表示具有整数坐标的点集 $(x, y)$，使得

$$

\左|x\右| + \left|y + \frac {1}{2}\right| <n

$$

路径是 $S_n$ 中一系列不同的点 $(x_1 , y_1 ), (x_2 , y_2 ), \ldots , (x_\ell, y_\ell)$ ，这样，对于 $i = 2, \ldots , \ell$ ，$(x_i , y_i )$ 和 $(x_{i - 1} , y_{i - ) 之间的距离1} )$ 是 $1$(换句话说，点 $(x_i , y_i )$ 和 $(x_{i - 1} , y_{i - 1} )$ 是具有整数坐标的点阵中的邻居)。证明 $S_n$ 中的点不能划分为少于 $n$ 路径(将 $S_n$ 划分为 $m$ 路径是 $m$ 个非空路径的 $\mathcal{P}$ 集合，使得 $S_n$ 中的每个点恰好出现在 $\mathcal{P}$ 中的 $m$ 路径之一中)。