Problem:
Two thousand points are given on a circle. Label one of the points . From this point, count points in the clockwise direction and label this point . From the point labeled , count points in the clockwise direction and label this point . (See figure.) Continue this process until the labels 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
Solution:
Let be the point labeled . For any positive integer we can find the point labeled by by counting points around the circle in the clockwise direction, with the count starting at . It follows that two positive integers and will label the same point if and only if and have the same remainder when divided by . Thus, if is a positive integer that labels the same point as , then
must be a multiple of . It is clear that satisfies these conditions; we need to see if there is a positive integer that also satisfies these conditions and, if any exist, find the smallest such integer. Since and are of different parity and cannot both be multiples of , one of these integers must be a multiple of and one must be a multiple of . If , then , so exactly one of and is a multiple of and the other is a multiple of . We consider these two cases.
Case 1. and
Because and , it follows that and are divisible by and , respectively. In other words, and for non-negative integers and . It is now evident that and that arises from and .
Case 2. and
Because and , it follows that and are divisible by and respectively. Thus and for non-negative integers and . From this we obtain , so is a multiple of . Thus for some integer we have . It follows that any positive integer satisfying this case is greater than .
Hence is the smallest positive integer that labels the same point as .
The problems on this page are the property of the MAA's American Mathematics Competitions