Maths Olympiad Prep

Track / Stage 7 / 277 of 300 #2157 of 2444

Problem 2157

National Olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.8 Prove it IMO Hk TST · Hong Kong

For an irrational number xx, let xx' be the integer nearest to xx. Define x=xx\langle x \rangle = |x - x'|. Show that for every irrational number yy, the minimum of the numbers y,2y,,2001y\langle y \rangle, \langle 2y \rangle, \dots, \langle 2001y \rangle is less than 12001\frac{1}{2001}.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

Consider the 2002 intervals Ik=(k2002,k+12002)I_k = (\frac{k}{2002}, \frac{k+1}{2002}) where k=1001,1000,,1000k = -1001, -1000, \dots, 1000. Since yy is irrational, the numbers yyy - y', 2y(2y)2y - (2y)', \dots, 2001y(2001y)2001y - (2001y)' are irrational numbers between 12-\frac{1}{2} and 12\frac{1}{2}. Thus, each of them belongs to one of the IkI_k's.

We claim that one of the numbers my(my)my - (my)' (with 1m20011 \le m \le 2001) belongs to I1I_{-1} or I0I_0. Suppose on the contrary that all these numbers belong to the other 2000 intervals. By the pigeonhole principle, two of them, say my(my)my - (my)' and ny(ny)ny - (ny)' with m>nm > n, belong to the same interval IkI_k. Then we have
(mn)y[(my)(ny)]=[my(my)][ny(ny)]<k+12002k2002=12002. (m-n)y - [(my)' - (ny)'] = [my - (my)'] - [ny - (ny)'] < \frac{k+1}{2002} - \frac{k}{2002} = \frac{1}{2002}.
Therefore, (my)(ny)(my)' - (ny)' is the closest integer to (mn)y(m-n)y, and we know that (mn)y[(mn)y](m-n)y - [(m-n)y]' belongs to I1I_{-1} or I0I_0. This is a contradiction. Therefore,

we can find some my(my)my - (my)' belonging to I1I_{-1} or I0I_0. For this mm, we have
my=my(my)<12002<12001. \langle my \rangle = |my - (my)'| < \frac{1}{2002} < \frac{1}{2001}.
This completes the proof.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty, ordering) added by this project.