1993 AIME 第 9 题

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 题