Japan Mathematical Olympiad

We will show that for any positive integer $k$ $A$ has strategies to win the game no matter how $B$ chooses his strategies. In the sequel, we restrict the possibilities for $A$ to mark only those lattice points in the set $J=\{(x,y):x+y=2^{k+1}k\}$. Also, we allow $A$ not to choose any lattice point to mark in his action. We will show that it is possible for $A$ to choose a correct strategy at each stage in such a way to prevent for $B$ to move the chess piece into the set $J$ no matter how $B$ chooses his strategies. Let us set $I_i=\{(x,y):ik\le x+y<(i+1)k\}$. If the chess piece lies in the region $I_i$, it stays in $I_i$ or moves into $I_{i+1}$ after the next action by $B$. This implies

that in order for the chess piece to reach the set $J$, it is necessary that for each $i$ ($i=1,2,\dots ,2^{k+1}$) $B$ must end his action at least once in the set $I_i$. Now, for each $s$ ($s=k+1,k,k-1,\dots ,2$) take note of the consecutive actions starting with the time of the first action by $B$ after the chess piece reached the set $I_{2^{k+1}-2^s}$ for the first time and ending with the action by $A$ taken immediately after the chess piece reached the set $I_{2^{k+1}-2^{s-1}}$, and call its listing the $s$-phase of the listing of consecutive actions taken during a game played. Let us investigate the situation in an $s$-phase more in detail. For $t$ ($t=1,2,\dots ,2^{s-1}$), suppose that the chess piece was moved to a point $(x^{\prime },y^{\prime })$ of the set $\{(x,y):x+y=(2^{k+1}-2^s+t)k\}$ during or at the end of an action by $B$, then define the set $X_{s,t}$ by $$X_{s,t}=\{(x,y):x+y=2^{k+1}k,(2^{s-1}-t)k+x^{\prime }\le x\le 2^{s-1}k+x^{\prime }\},$$ It is easy to check that the inclusion relations $X_{s,1}\subset X_{s,2}\subset \cdots \subset X_{s,2^{s-1}}$ hold. Let $h_s$ be an integer satisfying $0\le h_s<k$. Then there are exactly $t$ or $t+1$ elements $(x,y)$ of the set $X_{s,t}$ for which $x\equiv h_s(\mathrm{mod}k)$ holds. ($t+1$ such elements exist only when $2^{s-1}k+x^{\prime }\equiv h_s(\mathrm{mod}k)$). Now, consider the following strategy for the player $A$: If at the first time of the arrival of the chess piece in the set $I_{2^{k+1}-2^{s+t}}$ there is an element in $X_{s,t}$ which is unmarked and for which $x\equiv h_s(\mathrm{mod}k)$ is satisfied, then mark this element. If there are 2 or more such elements, then choose an element to be marked in such a way that one of the elements of the form $((2^{s-1}-t)k+x^{\prime },(2^{k+1}-2^{s-1})k+x^{\prime })$ or $(2^{s-1}k+x^{\prime },(2^{k+1}-2^{s-1})k+x^{\prime })$ remains unmarked. Do not mark any point if there are no such elements. By using the induction on $t$, the following facts can be established: Immediately after the action by $A$ using the strategy stated above, there are $t$ or more elements $(x,y)$ in the set $X_{s,t}$ which are marked and for which $x\equiv h_s(\mathrm{mod}k)$ hold. If there is an unmarked element of the set $X_{s,t}$ satisfying $x\equiv h_s(\mathrm{mod}k)$, then this element must be either $((2^{s-1}-t)k+x^{\prime },(2^{k+1}-2^{s-1})k-x^{\prime })$ or $(2^{s-1}k+x^{\prime },(2^{k+1}-2^{s-1})k-x^{\prime })$. By definition the set $X_{s,2^s-1}$ is precisely the set of points lying in the set $J$ that can be reached by the chess piece if $B$ can make moves ignoring $✓$'s after the time it reaches the set $\{(x,y):x+y=(2^{k+1}-2^s)k\}$ for the first time. Hence, we have the inclusion relations $X_{k+1,2^k}\supset X_{k,2^{k-1}}\supset \cdots \supset X_{2,2}$. Therefore, if $A$ chooses strategies in such a way that for each $s$ ($s=k+1,k,\dots ,2$) he picks distinct $h_s$ and performs the action for the $s$-phase using the strategy with the picked $h_s$ specified above, then $A$ can end up with the situation where $X_{2,2}$ has at most one element unmarked. At this stage the only points on the set $J$ that the chess piece can move into must belong to the set $X_{2,2}$. But since the chess piece at this stage lies in the set $I_{2^{k+1}-2}$, $B$ has to take at least 2 more actions in order to move the chess piece into the set $J$, which means that $A$ can take an action at least once before the chess piece can reach the set $J$, and therefore, $A$ can mark the unmarked point in $X_{2,2}$.

(if there is an unmarked point) to prevent $B$ to move the chess piece into the set $J$. Thus we have established the assertion that for any positive integer $k$ there are strategies that $A$ can follow to win the game regardless of how $B$ chooses his strategies.