Maths Olympiad Prep

Library / /22 of 94

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 m2007m \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 a1a \ge 1, 1b20071 \le b \le 2007 and ab<2\frac{a}{b} < \sqrt{2}. Let nm\frac{n}{m} be the largest such fraction. If nkm2k\lfloor \frac{nk}{m} \rfloor \ne \lfloor \sqrt{2}k \rfloor for some k=1,2,,2007k = 1, 2, \dots, 2007, then t=2kt = \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 2kZ\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 1k20071 \le k \le 2007.

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.