Maths Olympiad Prep

Library / /3 of 3

Combinatorics Difficulty 9.2 IMO level Prove it Romania

Let AA be a point in the Cartesian plane. Ann tells Bob a number 0<a10 < a \le 1 and he then moves AA rightward, leftward, upward or downward to a new position AA', aa distance apart from AA. Next, Ann tells Bob a number 0<a10 < a' \le 1 and he moves AA' rightward, leftward, upward or downward to a new position AA'', aa' distance apart from AA' 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 k100k \le 100. Clearly, if k=1k = 1, the case is settled, so let k2k \ge 2.

The first k1k-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(k1) and 12100k \frac{1}{2^{99}}, \frac{1}{2^{98}}, \dots, \frac{1}{2^{100-(k-1)}} \text{ and } \frac{1}{2^{100-k}}
The first k1k-1 moves decrease the xx-coordinate by at most
1299+1298++12100(k1)=12100k1299, \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/2100k1/2^{100-k}. Consequently, the overall variation of the xx-coordinate is at least
(12100k1299)+12100k=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,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.