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.$

1993 AIME Problem 9

Answer: 118

Difficulty rating: 2550

Small Hint:

Big Hint:

Solution:

Problem 9 in Other Years