Baranovv D.V.

Andrey and Boris are playing the following game. Initially, a robot stands at point $p$ on the number line. First, Andrey states the distance the robot should move. Then Boris chooses the direction in which the robot moves this distance, and so on. For which $p$ can Andrey ensure that the robot will reach one of the points 0 or 1 in a finite number of moves regardless of Boris's actions?
Note that if $p=1$, then Boris wins (he can always choose the direction away from 1, thereby increasing the distance from the robot to the segment).

We will prove that for $p \in [0,1]$, Andrey wins if and only if $p=\frac{m}{2^{n}}$, where $m$ and $n$ are non-negative integers, and the fraction is irreducible.

We will prove the "if" part. Suppose at some step the robot's coordinate has the form $\frac{k}{2^{t}}$ and lies between 0 and 1. Then

![](https://cdn.mathpix.com/cropped/2024_05_06_ed128c2d5b4d71db92ebg-04.jpg?height=83&width=2012&top_left_y=1828&top_left_x=0)
it will also be of the form $\frac{k}{2^{t}}$, but $l > 0$, so these points lie between 0 and 1. Since the denominator will eventually become 1, i.e., the robot will reach 0 or 1, Andrey will win.

We will prove the "only if" part. Suppose at some step the robot's coordinate $x$ cannot be represented in such a form. Then for any $d$, at least one of the numbers $x-d, x+d$ does not have such a form, because otherwise their average $x$ would also have such a form. Therefore, Boris can ensure that the new coordinate of the robot cannot be represented in such a form. Since 0 and 1 have such a form, Boris will win.

## Answer

$p=\frac{m}{2^{n}}$, where $m$ and $n$ are non-negative integers, the fraction is irreducible, and $m \leq 2^{n}$.

Send a comment