This was proposed by Cyprus (Demetres Christofides again a beautiful problem)

reposting the original pic, that I uploaded yesterday in the start, until I wrote down the wording, in order to remove it from the 1st post and the related post collection to look better

Attachments:

Since there are no solutions posted yet I will give a sketch of my solution. Anna does not have a winning strategy. Even though it's "easy" to come up with a strategy for Bob that works or "almost" works I believe it is "quite hard" to actually write it down correctly and prove that it works. Part of the reason is that everything is so close that just a small variation of the rules can make it a win for Anna. For example if Anna is allowed to start by making only two steps instead of three and then continuing with three steps each turn, then she has a winning strategy. (It might seem unintuitive but there is no mistake in the last line.) Any proof should take account of this. Bob's strategy on the line $y=2019$ is as follows: 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 step, Bob deletes the next available point to the left and the next available point to the right. (This annoying exception is really needed here. Without it the strategy does not work.) We may assume for contradiction that Anna wins by placing her token at $(k,2019)$ for some $k > 0$. (Needs some not too difficult explanation why we may assume $k > 0$.) The crucial seminvariant in my proof is $\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. It can be checked that after a turn by Anna and then a turn by Bob, $\Delta$ does not decrease. Furthermore, it can be checked that in the final move of Anna (note: Bob does not play yet) we have $\Delta \leqslant -4$. So Anna must have decreased $\Delta$ in her last turn by at least $4$ and this can only happen if she makes a move of type $(1,2)$ or $(2,1)$. (The first one decreases $\Delta$ by $4$ and the second one by $5$.) 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 \bmod 3$. However in that case it can be checked that we must have already had $\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 turns with the change of $y$ being $+1$ or $-2$ or at least one turn with the change of $y$ being $+2$ or $-1$. In both cases, it can be checked that we get an increase of at least $2$ in $\Delta$, a contradiction.

Demetres, congrats, good problem. According to official results this problem has been completely solved only by two Serbian contestants. I've also spotted a Cypriot student receiving 7 points, and another Serbian with 4 points. It turns out to be undoubtedly the hardest problem of this year's Balkan.

Our student who got 7 looked at the quantities $m_i-x_i$ where $x_i$ is the change of the $x$-coordinate in Anna's i-th turn and $m_i$ is the additional number of points deleted by Bob to the right of $(0,2019)$ afterwards. (Actually, he worked on the line $x = 2019$, rather than the line $y=2019$.) I wonder what were the invariants/semivariants used by the two Serbians. Anybody knows?

The two Serbian students have completely different solutions from each other, as well as from the official solution. I will sketch the easier one (which is, IMHO, also easier and nicer than the official solution). We describe Bob's strategy for the bottom edge (the rest is symmetric). During the first $672\frac12$ moves, Bob deletes all the points that are $\equiv 0\pmod 3$ (whatever Anna is doing), and as an additional point in his $673$rd move, he deletes the nondeleted point that is closest to Anna (if there are two such points, then any of them). In all the further moves he always deletes the two points that are closest to Anna. It can be quite easily proved that, by this strategy, he always keeps Anna at a distance of at least $4$ from any boundary point, which is enough to complete the proof. The solution from the second Serbian student is extremely complicated and actually nonconstructive (he shows that Bob wins but never gives an explicit description of his strategy; the proof is by contradiction after supposing that Anna could win)! I promised to some people that I would write a detailed account of his solution in English and send it to them, and when I do that (say in a week or so), I could also post it here. Btw., I also liked the problem very much. The only thing that bothers me about it is the fact that the opportunity is missed to make a) and b) part, where a) would be the same as it is now, and b) would be the same question but when Anna is allowed to make at most three steps, and has to make strictly less than three steps on at least one move. Then the intuition about the problem would suggest exactly the opposite of what in fact would be a correct answer! Demetres, did you think about this version, and what is your opinion? (I agree that the problem would then probably be a little bit too hard for BMO, but perhaps it could be considered for IMO or something else.)

Bojan Basic wrote: The two Serbian students have completely different solutions from each other, as well as from the official solution. I will sketch the easier one (which is, IMHO, also easier and nicer than the official solution). We describe Bob's strategy for the bottom edge (the rest is symmetric). During the first $672\frac12$ moves, Bob deletes all the points that are $\equiv 0\pmod 3$ (whatever Anna is doing), and as an additional point in his $673$rd move, he deletes the nondeleted point that is closest to Anna (if there are two such points, then any of them). In all the further moves he always deletes the two points that are closest to Anna. It can be quite easily proved that, by this strategy, he always keeps Anna at a distance of at least $4$ from any boundary point, which is enough to complete the proof. What a lovely proof! to him Bojan Basic wrote: The solution from the second Serbian student is extremely complicated and actually nonconstructive (he shows that Bob wins but never gives an explicit description of his strategy; the proof is by contradiction after supposing that Anna could win)! I promised to some people that I would write a detailed account of his solution in English and send it to them, and when I do that (say in a week or so), I could also post it here. Would also be interested to see it. Bojan Basic wrote: Btw., I also liked the problem very much. The only thing that bothers me about it is the fact that the opportunity is missed to make a) and b) part, where a) would be the same as it is now, and b) would be the same question but when Anna is allowed to make at most three steps, and has to make strictly less than three steps on at least one move. Then the intuition about the problem would suggest exactly the opposite of what in fact would be a correct answer! Demetres, did you think about this version, and what is your opinion? (I agree that the problem would then probably be a little bit too hard for BMO, but perhaps it could be considered for IMO or something else.) I've sent the problem to last years' IMO but it didn't get selected for the shortlist. (In fact, the combinatorics problems of the last 3 BMOs which are all mine were first send for IMO but were not selected for the shortlist. ) The version that I've sent there, was for general $N$. It turns out that Anna wins unless $N=1$ or $N \equiv 0 \bmod 3$. Anna's strategy is not difficult but I had to add another two paragraphs for each of $N \equiv 1 \bmod 3$ and $N \equiv 2 \bmod 3$ in the proof. Together with the statement, this almost spanned 2 pages. For BMO I felt that this was too much and the problem would be immediately rejected as way too hard. So trying to minimize as much as possible the length of the statement and the proof, I kept just the hard part of the question. If I only had your student's proof... I am sure what you suggest would cause lots of headaches for the students. However, once you overcome this and realise that the answer is the opposite of what you expect it might actually help a student to know what to avoid in the proof. (This is where our student went wrong.) To find a proof though is still another matter. So yes, I would like this as a version to the problem. In any case, I added as side notes without proofs the facts of what happens if Anna is allowed to make fewer moves or if we replace $2019$ by $N$. So in a sense it was also up to the jury to decide if they wanted to modify the statement and how. Unfortunately, I could not come this year to BMO. If I was the Cyprus leader I would suggest to the jury a couple of different alternatives.

Here is the other solution that I mentioned. (The solution from the previous message is by SRB5, Jovan Toromanović; the solution from this post is by SRB3, Aleksa Milojević, who has thus achieved his fourth perfect score in a row at BMOs!) We prove that Anna cannot win. We define the following modification, call it $I'$, of the game from the statement: the game is played on the same board, but Bob is allowed to delete only points from the bottom edge (instead of from any edge), and Anna wins if she reaches the bottom edge (instead of any edge); if Anna reaches any other edge, the game simply continues (Anna still makes three steps in each her move, but she is not allowed to go beyond the boundary lines). Lemma 1. If Anna has a winning strategy in the original game, then she also has a winning strategy in the game $I'$. Proof. Suppose the contrary: Bob has a strategy to stop Anna from reaching the bottom edge in the game $I'$. Then Bob can also defeat Anna in the original game, by applying analogous strategies on each of the remaining three edges. $\square$ Therefore, it is enough to prove that Bob can defeat Anna in the game $I'$. For the rest of the solution, we consider only the game $I'$ (the original game will never be mentioned anymore). Lemma 2. Suppose that, at a given point in time, Anna can choose between making the step to a point $P$ and making the step to a point $Q$, where $Q$ is one unit below and one unit either left or right of $P$. If Anna can force a win by making the step to the point $P$, then she also can force a win by making the step to the point $Q$. Proof. Since this is the part of the solution that is the hardest to comprehend, I will write it in a very formal manner. (An informal account is given at the end of the proof, if you prefer that way.) Anna's strategy can be formally described as a function $f$ defined on triples $(X,{\mathcal D},i)$, where: • $X$ is a point on the playing grid (Anna's current position); • $\mathcal D$ is a set of deleted points on the bottom edge; • $i\in\{1,2,3\}$, which denotes whether Anna is about to make the first, the second, or the third step within a move; $f$ maps such a triple to a point at the distance $1$ from the point $X$ (that is, $f$ determines which point Anna should move the token to). Note that $f$ does not have to be defined at any such triple, but it must be defined at any triple reachable from a triple that is known as winning for Anna (here we mean reachable under Anna's optimal play and Bob's any play---since Anna, in order to win, must have a response to any possible Bob's move); in other words, if $f(X,\mathcal D,i)$ is defined, then, if $i=1,2$, we have that $f(f(X,\mathcal D,i),\mathcal D,i+1)$ also has to be defined, while if $i=3$, $f(f(X,\mathcal D,i),\mathcal D',1)$ has to be defined for any $\mathcal D'$ such that $|\mathcal D'|=|\mathcal D|+2$. By the conditions of the lemma, the point $Q$ is either $P-(1,1)$ or $P+(1,-1)$. Assume, w.l.o.g., the former case. By the assumption that Anna can force a win by making the step to the point $P$, we have that $f(P,\mathcal D,i)$ is defined for the corresponding $i$ and any set of deleted points $\mathcal D$ that can appear after Anna's step (if Bob is on the move after Anna's step; if not, then $\mathcal D$ equals the set of deleted points before Anna's step). Assume that Anna steps to the point $Q$ instead of the point $P$. We shall now describe how Anna can win from this position. Assume that after Bob's move (if any) the set of deleted points is $\mathcal B$. We know that $f(P,\mathcal B,i)$ is defined; if it represents a point that is one unit down or left from the point $P$ (call this “Case One”), then this point is also reachable from the point $Q$, and by moving her token there, Anna obtains a winning position (since $f(P,\mathcal B,i)$ is a winning position for Anna by the definition of $f$). Assume now that $f(P,\mathcal B,i)$ is up or right from the point $P$ (call this “Case Two”). Then Anna should also step up, respectively right, from the point $Q$. Now Anna's token is at the position $f(P,\mathcal B,i)-(1,1)$, and we can now repeat the reasoning above (with the point $f(P,\mathcal B,i)$ playing the role of $P$). Since the board is finite, sooner or later Case One will happen, after which Anna will be able to move her token to a winning position, as we have already seen. (Here is a shorter, though informal, description of the main idea of the presented proof. Standing at the point $Q$, Anna imagines a shadow standing at the point $P$. Anna and Bob then play a game “in reality,” and the shadow moves according to its winning strategy, responding to the moves Bob makes in the “real game”---note that, since we have assumed that there would be a winning strategy for Anna if she were at the point $P$, this means that the shadow will have a winning response to any Bob's move. Anna's aim is to merge with the shadow; that is, if the shadow steps to a point that Anna can also step to, Anna goes there and achieves the aim, while if the shadow moves away from Anna, Anna continues to chase it and waits for the opportunity to merge with it, which must happen sooner or later.) $\square$ Lemma 3. Suppose that Anna can win. Then she can win by first going straight down until she reaches the line $y=-2018$, and only then making steps to the left and to the right. Proof. If Anna can win, then she can win by never making a step up: indeed, by the previous lemma, if Anna could win by making a step up, then she could also win by making a step to the left or to the right instead. Also by the previous lemma, if Anna could win by making a horizontal step (on some line above $y=-2018$), then she could also win by making the step down instead. $\square$ Therefore, in order to reach a contradiction with the assumption that Anna can win, it is enough to show that Anna cannot win by first going straight down until she reaches the line $y=-2018$, and only then making steps to the left and to the right. We give a strategy for Bob to defeat this Anna's strategy. During the first $673$ moves, Bob deletes all the points whose $x$-coordinate is from the interval $[-672,673]$. Before her $673^{\text{rd}}$ move, Anna is at the point $(0,-2016)$, and she now has to make two steps down and then one step left or right. If she goes left, Bob deletes the next two points on the left, and if she goes right, Bob deletes one point on the left and one point on the right. In every following move, Bob deletes the next two points in Anna's direction. It is a straightforward calculation to see that, by continuing to play this way, Bob will have (just) enough time to prevent Anna from reaching the bottom edge.