Maths Olympiad Prep

Library / /306 of 520

Number theory Difficulty 7.0 National olympiad, round 2 Prove it

Consider all points with integer coordinates in the carthesian plane. If one draws a circle with M(0,0) and a well-chose radius r, the circles goes through some of those points. (like circle with r=22r=2\sqrt2 goes through 4 points)

Prove that nN,r\forall n\in \mathbb{N}, \exists r so that the circle with midpoint 0,0 and radius rr goes through at least nn points.

Solution

1. Parametrization of the Unit Circle:
Consider the unit circle centered at the origin with radius 1. A rational parametrization of the unit circle is given by:
x=2t1+t2,y=1t21+t2 x = \frac{2t}{1 + t^2}, \quad y = \frac{1 - t^2}{1 + t^2}
where t t is a parameter. If t t is rational, then both x x and y y are rational.

2. Choosing Rational Points:
Choose n n distinct rational values for t t , say t1,t2,,tn t_1, t_2, \ldots, t_n . This gives us n n distinct rational points on the unit circle:
Mk=(2tk1+tk2,1tk21+tk2)fork=1,2,,n M_k = \left( \frac{2t_k}{1 + t_k^2}, \frac{1 - t_k^2}{1 + t_k^2} \right) \quad \text{for} \quad k = 1, 2, \ldots, n

3. Finding the Least Common Multiple (LCM):
Let m m be the least common multiple (LCM) of the denominators of the coordinates xk x_k and yk y_k for k=1,2,,n k = 1, 2, \ldots, n . This ensures that when we scale the coordinates by m m , we obtain integer coordinates.

4. Scaling the Points:
Apply a homothety (scaling transformation) with center O O (the origin) and ratio m m . The coordinates of the points Mk M_k after scaling by m m become:
Mk=(m2tk1+tk2,m1tk21+tk2) M_k' = \left( m \cdot \frac{2t_k}{1 + t_k^2}, m \cdot \frac{1 - t_k^2}{1 + t_k^2} \right)
Since m m is the LCM of the denominators, the coordinates of Mk M_k' are integers.

5. Conclusion:
The scaled points Mk M_k' are distinct integer points on a circle centered at the origin with radius r=m r = m . Therefore, we have found a radius r r such that the circle passes through at least n n distinct integer points.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.