Browse · MathNet
Print74th NMO Selection Tests for BMO and IMO
Romania counting and probability
Problem
Let be a point in the Cartesian plane. Ann tells Bob a number and he then moves rightward, leftward, upward or downward to a new position , distance apart from . Next, Ann tells Bob a number and he moves rightward, leftward, upward or downward to a new position , distance apart from 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 . 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 such that, by Ann providing Bob suitable numbers, she eventually forces the -coordinate of the point increase by at least . Then, using over and over again, she successively increases the -coordinate of the point by at least , thus making it as far away from as needed.
We now prove that fits the bill. Ann first provides , then , 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 . Clearly, if , the case is settled, so let .
The first moves are leftward, upward or downward. Any leftward move decreases the -coordinate of the point by the corresponding number Ann provided; upward and downward moves do not change it.
During the first steps, Ann successively provides the numbers The first moves decrease the -coordinate by at most and the -th increases it by . Consequently, the overall variation of the -coordinate is at least as needed. This ends the proof.
We now prove that fits the bill. Ann first provides , then , 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 . Clearly, if , the case is settled, so let .
The first moves are leftward, upward or downward. Any leftward move decreases the -coordinate of the point by the corresponding number Ann provided; upward and downward moves do not change it.
During the first steps, Ann successively provides the numbers The first moves decrease the -coordinate by at most and the -th increases it by . Consequently, the overall variation of the -coordinate is at least as needed. This ends the proof.
Final answer
Yes
Techniques
Games / greedy algorithmsSums and productsCartesian coordinates