1993 AIME Problems/Problem 9

Problem

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\dots,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$ ?

Solution

The label $1993$ will occur on the $\frac12(1993)(1994) \pmod{2000}$ th point around the circle. (Starting from 1) A number $n$ will only occupy the same point on the circle if $\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}$ .

Simplifying this expression, we see that $(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{2000}$ . Therefore, one of $1993 - n$ or $1994 + n$ is odd, and each of them must be a multiple of $125$ or $16$ .

For $1993 - n$ to be a multiple of $125$ and $1994 + n$ to be a multiple of $16$ , $n \equiv 118 \pmod {125}$ and $n\equiv 6 \pmod {16}$ . The smallest $n$ for this case is $118$ .

In order for $1993 - n$ to be a multiple of $16$ and $1994 + n$ to be a multiple of $125$ , $n\equiv 9\pmod{16}$ and $n\equiv 6\pmod{125}$ . The smallest $n$ for this case is larger than $118$ , so $\boxed{118}$ is our answer.

Note: One can just substitute $1993\equiv-7\pmod{2000}$ and $1994\equiv-6\pmod{2000}$ to simplify calculations.

== solution 2 ==

Two labels $a$ and $b$ occur on the same point if $\ a(a+1)/2\equiv \ b(b+1)/2\ pmod{2000}$ . If we assume the final answer be $n$ , then we have $\frac12(n)(n + 1)\equiv \frac12(1993)(1994) \pmod{2000}$ .

Multiply $2$ on both side we have $(1993)(1994) - (n)(n + 1) = (1993 - n)(1994 + n)\equiv 0\pmod{4000}$ . As they have different parities, the even one must be divisible by $32$ .As $(1993 - n)+(1994 + n)\equiv 2\pmod{5}$ , one of them is divisible by $5$ , which indicates it's divisible by $125$ .

Which leads to four different cases: $1993-n\equiv 0\pmod{4000}$ ; $1994+n\equiv 0\pmod{4000}$ ; $1993-n\equiv 0\pmod{32}$ and $1994+n\equiv 0\pmod{125}$ ; $1993-n\equiv 0\pmod{125}$ and $1994+n\equiv 0\pmod{32}$ . Which leads to $n\equiv 1993,2006,3881 and 118\pmod{4000}$ respectively, and only $n=118$ satisfied.Therefore answer is $\boxed{118}$ .

1993 AIME (Problems • Answer Key • Resources)
Preceded by Problem 8	Followed by Problem 10
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15
All AIME Problems and Solutions

Page

Toolbox

Search

1993 AIME Problems/Problem 9

Problem

Solution

See also