Library / Baltic Way Shortlisted Problems /8 of 13

Baltic Way Shortlisted Problems, 2015

Combinatorics Difficulty 7.8 National Olympiad, round 2 Prove it Baltic Way

Let $m$ and $n$ be positive integers and let the integer $X \ge \max(m, n)$ . Show that there exist integers $u$ and $v$ , not both equal to $0$ , such that
$\max(|u|, |v|) \le \sqrt{X} \quad \text{and} \quad 0 \le m u + n v \le 2\sqrt{X}.$

Solution

There are $[\sqrt{X} + 1]^2 \ge X + 1$ pairs $(a, b)$ such that $0 \le a, b \le \sqrt{X}$ , and for these
$0 \le m a + n b \le 2 X \sqrt{X}.$
Two linear combinations $m a + n b \ge m a' + n b'$ differ by at most $2\sqrt{X}$ , and so

$\max(|a$ - a'|, |b - b'|) $\le \sqrt{X} \quad \text{and} \quad 0 \le$ m(a - a') + n(b - b') $\le 2\sqrt{X}. \quad \square$

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

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