1993 AIME Problem 9

Question

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?

Answer

Answer: 118

Concepts:Chinese Remainder Theorem modular arithmetic quadratic residue

Difficulty rating: 2550

Small hint:

Measure every label’s clockwise displacement from the point labeled

1

Big hint:

Reduce the resulting quadratic congruence separately modulo

32

and modulo

125

Solution:

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.