Maths Olympiad Prep

Library / NMO Selection Tests for BMO and IMO /47 of 47

NMO Selection Tests for BMO and IMO

Combinatorics Difficulty 9.2 IMO level Prove it Romania

Let AA be a point in the Cartesian plane. Ann tells Bob a number 0<a≤10 < a \le 1 and he then moves AA rightward, leftward, upward or downward to a new position A′A', aa distance apart from AA. Next, Ann tells Bob a number 0<a′≤10 < a' \le 1 and he moves A′A' rightward, leftward, upward or downward to a new position A′′A'', a′a' distance apart from A′A' and so on and so forth, as long as Ann wishes. At each step, Bob is free to choose which way to move the point, on one condition: Amongst every 100 consecutive moves, each of his four possible choices should have been made at least once. Ann's goal is to force Bob eventually choose a point strictly more than 100 distance away from AA. Is it possible for Ann to achieve her goal?
Argentine, 2014

Solution

The answer is in the affirmative. It is sufficient to prove that there exists a positive number dd such that, by Ann providing Bob suitable numbers, she eventually forces the xx-coordinate of the point increase by at least dd. Then, using dd over and over again, she successively increases the xx-coordinate of the point by at least 2d,3d,…2d, 3d, \dots, thus making it as far away from AA as needed.

We now prove that d=1/299d = 1/2^{99} fits the bill. Ann first provides 1/2991/2^{99}, then 1/2981/2^{98}, 1/2971/2^{97} and so on and so forth until Bob is forced to make his first move rightward. This latter occurs at step 100 at latest, by the restriction condition on Bob's choices. Let Bob's first move rightward occur at step k≤100k \le 100. Clearly, if k=1k = 1, the case is settled, so let k≥2k \ge 2.

The first k−1k-1 moves are leftward, upward or downward. Any leftward move decreases the xx-coordinate of the point by the corresponding number Ann provided; upward and downward moves do not change it.

During the first kk steps, Ann successively provides the numbers
1299,1298,…,12100−(k−1) and 12100−k \frac{1}{2^{99}}, \frac{1}{2^{98}}, \dots, \frac{1}{2^{100-(k-1)}} \text{ and } \frac{1}{2^{100-k}}
The first k−1k-1 moves decrease the xx-coordinate by at most
1299+1298+⋯+12100−(k−1)=12100−k−1299, \frac{1}{2^{99}} + \frac{1}{2^{98}} + \dots + \frac{1}{2^{100-(k-1)}} = \frac{1}{2^{100-k}} - \frac{1}{2^{99}},
and the kk-th increases it by 1/2100−k1/2^{100-k}. Consequently, the overall variation of the xx-coordinate is at least
−(12100−k−1299)+12100−k=1299, - \left( \frac{1}{2^{100-k}} - \frac{1}{2^{99}} \right) + \frac{1}{2^{100-k}} = \frac{1}{2^{99}},
as needed. This ends the proof.

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.