Competition problem — Number theory

Library / /508 of 520

Number theory Difficulty 6.0 National olympiad Prove it

Example 1 Let $x$ be any real number. Prove: $x, 2 x, \cdots$ , $n x$ must contain a number, the absolute difference between which and some integer is no greater than $\frac{1}{n+1}$ .

Analysis: If we can prove that the sum of the absolute differences between each number in $x, 2 x, \cdots, n x$ and some integer is no greater than $\frac{n}{n+1}$ , then $x, 2 x, \cdots, n x$ must contain a number, the absolute difference between which and some integer is no greater than $\frac{1}{n+1}$ . However, since the integer is uncertain, it could either be $[i x]$ or $[i x]+1$ , and summing these absolute differences would involve too many cases to handle directly, making it difficult. Therefore, it might be better to consider a proof by contradiction.

Solution

Prove: If the absolute value of the difference between each $i x$ and some integer is greater than $\frac{1}{n+1}$ , then
$i x-[i x]>\frac{1}{n+1},[i x]+1-i x>\frac{1}{n+1},$

i.e., there are $n$ values of $i x-[i x]$ in the interval $\left(\frac{1}{n+1}, \frac{n}{n+1}\right)$ .
Consider the intervals
$\begin{array}{l} \left(\frac{1}{n+1}, \frac{2}{n+1}\right],\left(\frac{2}{n+1}, \frac{3}{n+1}\right], \cdots, \\ \left(\frac{n-1}{n+1}, \frac{n}{n+1}\right) . \end{array}$

By the pigeonhole principle, there exist $i, j (i>j)$ such that
$|(i x-[i x])-(j x-[j x])|<\frac{1}{n+1},$

i.e., there exists $1 \leqslant i-j \leqslant n$ and an integer $[i x]-[j x]$ , such that
$|(i-j) x-([i x]-[j x])|<\frac{1}{n+1} \text {. }$

Contradiction.

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.