Maths Olympiad Prep

Library / China Hong Kong Mathematical Olympiad /22 of 89

China Hong Kong Mathematical Olympiad

Algebra Difficulty 5.3 AIME, harder Prove it Hong Kong

Determine if there exists a positive integer pair (m,n)(m, n), such that
(i) the greatest common divisor of mm and nn is 11, and m≤2007m \le 2007,
(ii) for any k=1,2,…,2007k = 1, 2, \dots, 2007, ⌊nkm⌋=⌈2k⌉\lfloor \frac{nk}{m} \rfloor = \lceil \sqrt{2k} \rceil.

(Here ⌊x⌋\lfloor x \rfloor stands for the greatest integer less than or equal to xx.)

Solution

Yes, it exists.
There are finitely many fractions ab\frac{a}{b} of lowest term such that a≥1a \ge 1, 1≤b≤20071 \le b \le 2007 and ab<2\frac{a}{b} < \sqrt{2}. Let nm\frac{n}{m} be the largest such fraction. If ⌊nkm⌋≠⌊2k⌋\lfloor \frac{nk}{m} \rfloor \ne \lfloor \sqrt{2}k \rfloor for some k=1,2,…,2007k = 1, 2, \dots, 2007, then t=⌊2k⌋t = \lfloor \sqrt{2}k \rfloor is an integer satisfying nkm<t<2k\frac{nk}{m} < t < \sqrt{2}k since nm<2\frac{n}{m} < \sqrt{2} and 2k∉Z\sqrt{2}k \notin \mathbb{Z}. It follows that nm<tk<2\frac{n}{m} < \frac{t}{k} < \sqrt{2}, which contradicts the choice of nm\frac{n}{m}. Therefore, we must have ⌊nkm⌋=⌊2k⌋\lfloor \frac{nk}{m} \rfloor = \lfloor \sqrt{2}k \rfloor for 1≤k≤20071 \le k \le 2007.

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.