62nd Ukrainian National Mathematical Olympiad, Third Round, First Tour

Answer: if $m$ and $n$ have the same parity, Vasyl wins, else Petrik wins.

Wlog the number of rows doesn't exceed the number of columns, so $m\le n$. Enumerate the rows from bottom to top as 1, 2, ..., $m$, and columns from left to right as 1, 2, ..., $n$, then each cell has two coordinates – numbers of the row and the column. Let's denote the chip that is initially in the left-upper cell with coordinates $(m,1)$ by A, and the other chip – in the cell $(1,n)$ – by B.

Let's show that if $m$ and $n$ have the same parity, then Vasyl has a winning strategy.

Vasyl can act as follows: first, he moves $\frac{1}{2}(n-m)$ times to the right with a chip A twice in a row. After that, the white chips will be in the opposite corners of the square $m\times m$. After this each time he will make 1 move with chip A to the right, and with chip B – 1 one move up. Let's show that in this case white chips will end up in the same cell with coordinates $(m,n)$, so black chip wouldn't be able to prevent this. For this, we will show that the black chip won't ever be able to get to any cell of the top row and to any cell of the right column. We will show this by contradiction. Suppose it's not true.

Case 1. Black chip got to the top row. Chip A at this point has made $x$ double and $y$ unary moves. Then black chip made $(x+y+1)$ moves, each of which is moving a chip twice. So the sum of its coordinates could change by at most $2(x+y+1)$. As it ended up in the top row, the first coordinate of its cell is $m$, so it is in the column with number at most $2+2(x+y+1)-m$. A, however, also is in the top row in a column with number $1+2x+y$. By assumption the chip A has to stand to the left of the black chip, as otherwise black chip wouldn't be able to get to that cell. So, the following inequality has to hold: $$1+2x+y<2+2(x+y+1)-m\Rightarrow y+3>m\Rightarrow m-2\le y$$ But this inequality means that the white chip A is at least in the cell $(m,n-1)$, and the white cell B is at least in the cell $(m-1,n)$, so the black chip has to be in a cell $(m,n)$. But then at least on one of the cells $(m,n-1)$ and $(m-1,n)$ were both black and white chips, contradiction, which completes the first case.

Case 2. The black chip got to the rightmost column. Suppose that it made $k$ double moves. Then the sum of coordinates of the black chip is at most $2+2k$, and as it is in the rightmost column, its first coordinate equals $n$. So the number of its row doesn't exceed $2+2k-n$. Let's count the number of row of B. For the first $\frac{1}{2}(n-m)$ moves it hasn't moved, and for the rest $2k-\frac{1}{2}(n-m)$ moves it was moving by one cell up at a time. So, its row number is $1+2k-\frac{1}{2}(n-m)$. By assumption, chip B has to be in a row with a smaller number than the black chip. So, the following inequality has to hold: $$2+2k-n>1+2k-\frac{1}{2}(n-m)\Rightarrow 1>\frac{1}{2}(n+m),$$ which is impossible.

So, under any conditions, the white chips will meet at the corner and Vasyl wins.

Now let's show that if $m$ and $n$ have different parity, then Petrik has a winning strategy. With a first move, he will move the first chip one cell to the right and one cell up. Next, he will act by the following algorithm, while possible: if Vasyl moves chip A(B) twice, Petrik will move his chip to the right(up) twice, and if he moves both chips, Petrik will move his chip one cell up and one cell to the right.

Fig. 7

Lemma. The algorithm of moves of Petrik has the following properties: If Petrik can perform the corresponding move, then after this move the black chip is always to the right of the cell A by columns and always higher to the cell B by rows, and the white cells haven't yet been to that part of the board (to the right and up from the black chip); Petrik can't make a move only if the black chip has reached the edge of the board, or white chips are in the adjacent cells above and to the right of it.

Fig. 8

Proof. We will do this by induction. After the first move, the statement is trivial. Suppose that Petrik did $k$ double moves. If Vasyl makes a double move with one chip (fig. 7), then Petrik can make the analogous move, without intersecting the trajectory of any white cell. For example, B moved up two cells, then Petrik also moves up two cells in other column, where white cells weren't before. If both white chips move by one cell, Petrik will also be able to go according to the algorithm (fig. 8). It's easy to see that after the $(k+1)$-st move the invariant is saved, so the lemma is proved.

In the case, when white chips surround the black chip in such a way, the black chip has coordinates $(k,l)$, and white have coordinates $(k,l+1)$ and $(k+1,l)$, and the value of the invariant is: $$((k+1+l)+(k+l+1)-(k+l))\equiv 0(\mathrm{mod}2).$$ We see the contradiction, which shows that this situation isn't possible for such values of $(m,n)$, which completes the proof.

From this lemma, if Petrik achieved the border, he separated white cells with his trajectory, so they won't be able to meet. Let's show that the situation, when both white cells are adjacent to the black chip is impossible. The parity of the sum of coordinates of white chips minus the coordinates of the black chip is an invariant, as after each move two coordinates change by 1, or one coordinate changes by 2. At the beginning of the game we have the following value of this invariant: $$((1+n)+(1+m)-(1+1))=(m+n)\equiv 1(\mathrm{mod}2).$$