Maths Olympiad Prep

Library / /68 of 136

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it 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}.

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.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.