2024 APMO 第 2 题

Consider a $100 \times 100$ table, and identify the cell in row $a$ and column $b, 1 \leq a, b \leq 100$, with the ordered pair $(a, b)$. Let $k$ be an integer such that $51 \leq k \leq 99$. A $k$-knight is a piece that moves one cell vertically or horizontally and $k$ cells to the other direction; that is, it moves from $(a, b)$ to $(c, d)$ such that $(|a-c|,|b-d|)$ is either $(1, k)$ or $(k, 1)$. The $k$-knight starts at cell $(1,1)$, and performs several moves. A sequence of moves is a sequence of cells $\left(x_{0}, y_{0}\right)=(1,1)$, $\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{n}, y_{n}\right)$ such that, for all $i=1,2, \ldots, n, 1 \leq x_{i}, y_{i} \leq 100$ and the $k$-knight can move from $\left(x_{i-1}, y_{i-1}\right)$ to $\left(x_{i}, y_{i}\right)$. In this case, each cell $\left(x_{i}, y_{i}\right)$ is said to be reachable. For each $k$, find $L(k)$, the number of reachable cells.

Answer: $L(k)=\left\{\begin{array}{ll}100^{2}-(2 k-100)^{2} & \text { if } k \text { is even } \\ \frac{100^{2}-(2 k-100)^{2}}{2} & \text { if } k \text { is odd }\end{array}\right.$.

考虑 $100 \times 100$ 表，并使用有序对 $(a, b)$ 标识行 $a$ 和列 $b 中的单元格，1 \leq a, b \leq 100$。令 $k$ 为整数，使得 $51 \leq k \leq 99$。 $k$-骑士是一个可以垂直或水平移动一个单元格并将 $k$ 个单元格移动到另一个方向的棋子；也就是说，它从 $(a, b)$ 移动到 $(c, d)$，使得 $(|a-c|,|b-d|)$ 要么是 $(1, k)$ 要么是 $(k, 1)$。 $k$-knight 从单元格 $(1,1)$ 开始，并执行多个动作。移动序列是单元格序列 $\left(x_{0}, y_{0}\right)=(1,1)$, $\left(x_{1}, y_{1}\right),\left(x_{2}, y_{2}\right), \ldots,\left(x_{n}, y_{n}\right)$ 使得对于所有 $i=1,2, \ldots， n, 1 \leq x_{i}, y_{i} \leq 100$ 并且 $k$-knight 可以从 $\left(x_{i-1}, y_{i-1}\right)$ 移动到 $\left(x_{i}, y_{i}\right)$。在这种情况下，每个单元格 $\left(x_{i}, y_{i}\right)$ 被认为是可达的。对于每个 $k$，找到 $L(k)$，即可达单元格的数量。

答案：$L(k)=\left\{\begin{array}{ll}100^{2}-(2 k-100)^{2} & \text { 如果 } k \text { 是偶数 } \\ \frac{100^{2}-(2 k-100)^{2}}{2} & \text { 如果 } k \text { 是奇数 }\end{array}\right.$。