36th Balkan Mathematical Olympiad

Anna does not have a winning strategy. We will provide a winning strategy for Bob. It is enough to describe his strategy for the deletions on the line $y=2019$.

Bob starts by deleting $(0,2019)$ and $(-1,2019)$. Once Anna completes her turn, he deletes the next two available points on the left if Anna decreased her $x$-coordinate, the next two available points on the right if Anna increased her $x$-coordinate, and the next available point to the left and the next available point to the right if Anna did not change her $x$-coordinate. The only exception to the above rule is on the very first time Anna decreases $x$ by exactly 1. In that turn, Bob deletes the next available point to the left and the next available point to the right.

Bob's strategy guarantees the following: If Anna makes a sequence of steps reaching $(-x,y)$ with $x>0$ and the exact opposite sequence of steps in the horizontal direction reaching $(x,y)$, then Bob deletes at least as many points to the left of $(0,2019)$ in the first sequence than points to the right of $(0,2019)$ in the second sequence.

So we may assume for contradiction that Anna wins by placing her token at $(k,2019)$ for some $k>0$.

Define $\Delta =3m-(2x+y)$, where $m$ is the total number of points deleted by Bob to the right of $(0,2019)$, and $(x,y)$ is the position of Anna's token.

For each sequence of steps performed first by Anna and then by Bob, $\Delta$ does not decrease. This can be seen by looking at the following table exhibiting the changes in $3m$ and $2x+y$. We have excluded the cases where $2x+y<0$.

Turn	(0,3)	(1,2)	(-1,2)	(2,1)	(0,1)	(3,0)	(1,0)	(2,-1)	(1,-2)
m	1	2	0 (or 1)	2	1	2	2	2	2
3m	3	6	0 (or 3)	6	3	6	6	6	6
2x + y	3	4	0	5	1	6	2	3	0

The table also shows that, if in this sequence of turns Anna changes $y$ by +1 or -2, then $\Delta$ is increased by 1. Also, if Anna changes $y$ by +2 or -1, then the first time this happens $\Delta$ is increased by 2. (This also holds if her turn is (0, -1) or (-2, -1), which are not shown in the table.)

Since Anna wins by placing her token at $(k,2019)$ we must have $m\le k-1$ and $k\le 2018$. So at that exact moment we have: $$\Delta =3m-(2k+2019)=k-2022\le -4.$$ So in her last turn she must have decreased $\Delta$ by at least 4. So her last turn must have been (1, 2) or (2, 1), which give a decrease of 4 and 5 respectively. (It could not be (3, 0) because then she must have already won. Also she could not have done just one or two steps in her last turn since this is not enough for the required decrease in $\Delta$.)

If her last turn was (1, 2), then just before doing it we had $y=2017$ and $\Delta =0$. This means that in one of her turns the total change in $y$ was not $0\mathrm{mod}3$. However, in that case we have seen that $\Delta >0$, a contradiction.

If her last turn was (2, 1), then just before doing it we had $y=2018$ and $\Delta =0$ or $\Delta =1$. So she must have made at least two turns with the change of $y$ being +1 or -2 or at least one step with the change of $y$ being +2 or -1. In both cases, consulting the table, we get an increase of at least 2 in $\Delta$, a contradiction.

Note 1: If Anna is allowed to make at most three steps at each turn, then she actually has a winning strategy.

Note 2: If 2019 is replaced by $N>1$, then Bob has a winning strategy if and only if $3\mid N$. □