Question

圆上有两千个点。任选一点标上 $1$ 。从该点起，沿顺时针方向数 $2$ 个点，并将到达的点标上 $2$ 。再从标有 $2$ 的点起，沿顺时针方向数 $3$ 个点，并将到达的点标上 $3$ 。（见图。）继续这一过程，直到 $1$ 、 $2$ 、 $3$ 、 $\ldots$ 、 $1993$ 这些标号全部用过。圆上有些点会有多个标号，有些点则没有标号。与 $1993$ 标在同一点上的最小整数是多少？

Two thousand points are given on a circle. Label one of the points $1.$ From this point, count $2$ points in the clockwise direction and label this point $2.$ From the point labeled $2,$ count $3$ points in the clockwise direction and label this point $3.$ (See figure.) Continue this process until the labels $1,$ $2,$ $3,$ $\ldots,$ $1993$ are all used. Some of the points on the circle will have more than one label and some points will not have a label. What is the smallest integer that labels the same point as $1993?$

答案

答案：118

知识点：中国剩余定理模运算二次剩余

难度评级：2550

小提示：

计算每个标号相对于标有 $1$ 的点的顺时针位移

Measure every label’s clockwise displacement from the point labeled $1$

大提示：

将所得二次同余式分别模 $32$ 和模 $125$ 求解

Reduce the resulting quadratic congruence separately modulo $32$ and modulo $125$

解答：

标号 $j$ 相对于标号 $1$ 沿顺时针方向移动了 $2+3+\cdots+j=\frac{j(j+1)}2-1$ 个点。因此，它与标号 $1993$ 位于同一点，当且仅当 $j(j+1)\equiv1993\cdot1994$ 模 $4000$ ，等价地，当 $j(j+1)\equiv2042\pmod {4000}$ 。模 $125$ 时，解为 $j\equiv6$ 和 $j\equiv118$ ；模 $32$ 时，解为 $j\equiv9$ 和 $j\equiv22$ 。用中国剩余定理合并，得到 $\begin{aligned}j\equiv{}&118,1993,\\&2006,3881\pmod {4000}\end{aligned}\text{。}$ 最小的正整数解为 $118$ 。

Label $j$ is displaced $2+3+\cdots+j=\frac{j(j+1)}2-1$ points clockwise from label $1.$ Thus it shares the point of label $1993$ exactly when $j(j+1)\equiv1993\cdot1994$ modulo $4000,$ or equivalently when $j(j+1)\equiv2042\pmod {4000}.$ Modulo $125,$ the solutions are $j\equiv6$ and $j\equiv118,$ and modulo $32,$ they are $j\equiv9$ and $j\equiv22.$ Combining these by the Chinese Remainder Theorem gives $\begin{aligned}j\equiv{}&118,1993,\\&2006,3881\pmod {4000}.\end{aligned}$ The smallest positive possibility is $118.$

1993 AIME 第 9 题

答案：118

难度评级：2550

小提示：

大提示：

解答：

其他年份的第 9 题