A robot is placed at point $P$ on the $x$-axis but different from $(0,0)$ and $(1,0)$ and can only move along the axis either to the left or to the right. Two players play the following game. Player $A$ gives a distance and $B$ gives a direction and the robot will move the indicated distance along the indicated direction. Player $A$ aims to move the robot to either $(0,0)$ or $(1,0)$. Player $B$'s aim is to stop $A$ from achieving his aim. For which $P$ can $A$ win?
Problem
Source: SMO Open 2019 Q3
Tags: combinatorics, game, ilostthegame, Combinatorial games
NikoIsLife
06.07.2019 11:05
The answer is all points $P(x,0)$, where $x=\frac n{2^k}$ for some positive integers $n$ and $k$ where $n$ is odd and $0\le x\le1$.
Proof: Let $S$ be the set of all numbers $x$ for which there exists positive integers $n$ and $k$ such that $n$ is odd and $0\le x\le1$.
First, we show that it is impossible for $A$ to win if $x<0$ or $x>1$. If $x<0$, then for any distance that $A$ says, $B$ would always say left, so the robot would always remain to the left of $(0,0)$ no matter what. Similarly, if $x>1$, then for any distance that $B$ says, $B$ would always say right, and the robot would always remain to the right of $(1,0)$ no matter what.
Next, we show that if $x\not\in S$, then it's impossible for $A$ to win. It is easy to see that if $x\not\in S$, then $2x\not\in S$.
Suppose that the distance that $A$ says is $d$. Then this means, the robot could either go to the point $(x+d,0)$, or $(x-d,0)$. Observe that $(x+d)+(x-d)=2x\not\in S$. This means, at least one of $x+d$ or $x-d$ does not belong in $S$. Now, $B$ could simply say that direction which makes the position not belong in $S$.
Hence, for any distance that $A$ says, it's always possible for $B$ to do it in a way that avoids the robot from going to any position $(x,0)$ where $x\in S$. This means, the robot would never be able to go to $(0,0)$ ot $(1,0)$.
Finally, we should that if $x\in S$, then it's possible for $A$ to win. Let $x=\frac n{2^k}$ for some [psotove integers $n$ and $k$ where $n$ is odd. We will prove that it's always possible for $A$ to win no matter what $B$ chooses. We will prove this by induction on $k$.
The base case is when $k=1$. This means, $x=\frac12$. Now, $A$ can simply say $\frac12$, and no matter what $B$ chooses, the robot would always end up at either $(0,0)$ or $(1,0)$.
For the inductive step, suppose that $A$ has a winning strategy for any $x=\frac n{2^k}$ where $n=1,3,\ldots,2^k-1$. Then, if $x=\frac m{2^{k+1}}$ for some odd $m$, then $A$ could simply say $\frac1{2^{k+1}}$, and the denominator of $x+\frac1{2^{k+1}}$ or $x-\frac1{2^{k+1}}$ would be a divisor of $2^k$, and we already know that $A$ has a winning strategy for this.
fattypiggy123
06.07.2019 17:56
Another possible solution goes by setting $S_n$ to be the set of points that are winnable in at most $n$ moves, and noting that $S_n$ consists of the midpoints of $S_0,\ldots, S_{n-1}$, it is clear that $\cup_{n=0}^{\infty} S_n$ is exactly the solution set described above. However, one cannot conclude that this is every possible $P$ since it is not true in general that if $A$ can win from $P$ in finitely many turns, then there is an $n$ such that $A$ will definitely win in $n$ moves. To illustrate, consider a game where $B$ chooses a positive integer $n$, does nothing afterwards, and every turn $A$ gets to subtract $1$ off it and wins when the number is $0$. Then although $A$ is guaranteed to win from the starting position in finitely many turns, no upper bound for the number of turns exists. To fix this, consider a binary tree where the vertices are the current point the game is at, and the two descendants are the two possibilities given by the two possible directions $B$ can choose. Assuming $A$ is able to win from $P$ and plays optimally, every path then has finite depth. If there is no upper bound, then there are arbitrary large paths exists and so the graph is infinite. But by Kőnig's lemma there must exist an infinite path --- a contradiction. Hence every point $P$ will exists in $S_n$ for some $n$ and we are done.
DVDthe1st
26.07.2019 12:38
The following is essentially the above post restated, but it cleared up some confusion for me on why $\cup_{n=0}^{\infty} S_n$ isn't necessarily the set of winnable positions. Suppose now there's a slightly different game: modified game wrote: A robot is placed at point $P$ on [...]. Two players play the following game. Before the game starts, player $B$ gives a positive integer $N$. Player $A$ gives a distance and $B$ gives a direction and the robot will move the indicated distance along the indicated direction. Player $A$ aims to move the robot to either $(0,0)$ or $(1,0)$. Player $B$'s aim is to stop $A$ from achieving his aim, however, after $N$ turns player $B$ runs out of patience and forfeits the game. [...] It turns out each $S_i$ in the modified game is the same as in the original game. However, all positions are now winnable, so the winnable set is not $\cup_{n=0}^{\infty} S_n$. Essentially, what must be shown is that in the original game, none of $B$'s decisions (left/right) really have the "same impact" as picking $N$ in the modified game.