BMO 2019 Shortlist

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 step, 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 step, 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 moves 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$.

Step	(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 steps 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 move 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 step 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 moves in her last turn since this is not enough for the required decrease in $\Delta$.)

If her last step was $(1,2)$ then just before doing it we had $y=2017$ and $\Delta =0$. This means that in one of her steps 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 step 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 steps 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.