There are three stacks of tokens on the table: the first contains $a,$ the second contains $b,$ and the third contains $c$ where $a \ge b \ge c.$ Players $A$ and $B$ take turns playing a game of swapping tokens. $A$ starts first. On each turn, the player who gets his turn chooses two stacks, then takes at least one token from the stack with the lowest number of tokens and places them on the stack with the highest number of tokens. If the number of tokens in the two piles he/she chooses is equal, then he/she takes at least one token from any of them and puts it in the other. If only one pile remains after a player's move, that player is considered a winner. At what values of $a, b, c$ who has the winning strategy ($A$ or $B$)?
Problem
Source: 2016 Azerbaijan JBMO TST, D1 P4
Tags: combinatorics, games, winning strategy
expsaggaf
12.10.2024 17:53
Claim: The position $(x, y, y)$, where $x \ge y$ is losing (the player in that position will eventually lose the game)
Proof: The player in this position will either play $(x + k, y, y - k)$ or $(x, y + k, y - k)$, where $k \in \mathbb{N}$. Notice that in both cases, either all three piles are pairwise unequal, or two are equal and the third is smaller. We will prove that in both cases, the other player can keep two piles equal, and the third pile is bigger or equal.
Case 1: $(x, y, y) \to (x + k, y, y - k)$
Then the next player responds with $(x + k, y, y - k) \to (x + 2k, y - k, y - k)$ (since $x + k > y$) and keeps two piles equal, and the third bigger or equal.
Case 2: $(x, y, y) \to (x, y + k, y - k)$
Let $x = y + a$. If $y + k \ge x$, then the other player responds with $(y + a, y + k, y - k) \to (y + a - (a + k), y + k + (a + k), y - k) = (y - k, y + 2k + a, y - k)$ and keeps two piles equal, and the third bigger or equal.
And if $y + k < x$, then the other player responds with $(x, y + k, y - k) \to (x + 2k, y - k, y - k)$, keeping two piles equal, and the third bigger or equal.
Notice that the piles with equal values always decrease in value ($(y, y) \to (y - k, y - k)$) which means that the other player will eventually turn the piles into $(x, 0, 0)$, while the initial player can't as stated above. So the player who initially started with $(x, y, y)$ will have lost.
Now if $b = c$, then Player $A$ is in the same position as described above, so Player $B$ will win.
If $b \neq c$, let $b = c + n$ $(n \in \mathbb{N})$. Player $A$ can then make the move $(a, c + n, c) \to (a + n, c, c)$ since $a \ge b$, putting Player $B$ in a losing position, so Player $A$ will win.
Conclusion: Player $B$ wins if and only if $b = c$.