Problem 2. For two positive integers $a$ and $b$, Ivica and Marica play the following game: Given two piles of $a$ and $b$ cookies, on each turn a player takes $2 n$ cookies from one of the piles, of which he eats $n$ and puts $n$ of them on the other pile. Number $n$ is arbitrary in every move. Players take turns alternatively, with Ivica going first. The player who cannot make a move, loses. Assuming both players play perfectly, determine all pairs of numbers $(a, b)$ for which Marica has a winning strategy.

(Petar Orlić)
Solution. Marica wins the game if $|a-b| \leqslant 1$, otherwise Ivica wins.

We will say that a player is in a losing position if it is his turn and $|a-b| \leqslant 1$, while calling all other positions winning positions. It is easy to see that the only positions in which one cannot make a move are $(0,0),(0,1),(1,0),(1,1)$ and that they are all losing positions.

Claim 1. If a player is in a losing position, then regardless of his move he must leave a winning position for the other player.

Proof. If the piles are of sizes $x$ and $x+1$, then after a move they will have sizes $x-2 k \mathrm{i} x+k+1$ (their difference is $3 k+1$ ) or $x+k$ i $x-2 k+1$ (their difference is $3 k-1$ ). In both cases, the difference is at least 2 . If the piles have $x$ and $x$ cookies each, then after a move they will have $x-2 k$ and $x+k$ cookies (there difference is $3 k$, which is at least 3). Since the difference of the number of cookies is always bigger than 1 , we have proven that this is a winning position.

Claim 2. A player who is in a winning position can always leave a losing position after his turn.

Proof. If the piles are of sizes $x$ and $x+3 a$ (where $a \geqslant 0$ ), one can take $2 a$ cookies from the second pile and and leave two piles containing $x+a$ and $x+a$ cookies. If the piles are of sizes $x$ and $x+3 a+1$ (where $a \geqslant 0$ ), one can take $2 a$ cookies from the second pile and leave two piles containing $x+a$ and $x+a+1$ cookies.

If the piles are of sizes $x$ and $x+3 a-1$ (where $a \geqslant 0$ ), one can take $2 a$ cookies from the second pile and and leave two piles containing $x+a$ and $x+a-1$ cookies. Since the difference in each case is less than 2, thus a player can always leave a loosing position if he is in a winning position.

We have now proven that if Ivica is in a loosing position in the begging, Marica can always ensure that he is in a winning position and win. Similarly, if Ivica is in a winning position in the begging, he can always ensure that he is in a winning position and win. So, Marica wins only when Ivica is in a losing position in his first turn. This is true only when $|a-b| \leqslant 1$.