Maths Olympiad Prep

Track / Stage 7 / 277 of 300 #2317 of 2604

Problem 2317

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

For an irrational number xx, let x′x' be the integer nearest to xx. Define ⟨x⟩=∣x−x′∣\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 y−y′y - 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 1≤m≤20011 \le m \le 2001) belongs to I−1I_{-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
(m−n)y−[(my)′−(ny)′]=[my−(my)′]−[ny−(ny)′]<k+12002−k2002=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 (m−n)y(m-n)y, and we know that (m−n)y−[(m−n)y]′(m-n)y - [(m-n)y]' belongs to I−1I_{-1} or I0I_0. This is a contradiction. Therefore,

we can find some my−(my)′my - (my)' belonging to I−1I_{-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.