There are $4$ piles of stones with the following quantities: $1004$, $1005$, $2009$ and $2010$. A legitimate move is to remove a stone from each from $3$ different piles. Two players $A$ and $B$ play in turns. $A$ begins the game . The player who, on his turn, cannot make a legitimate move, loses. Determine which of the players has a winning strategy and give a strategy for that player.
Problem
Source:
Tags: combinatorics, game, winning strategy
Math_Is_Fun_101
17.09.2021 03:44
We claim player $A$ has a winning strategy. First, player $A$ removes a stone from the piles with $1005,2009,2010$ stones. This leaves $1004,1004,2008,2009$ stones in each pile. Now, we claim that if $B$ had a legitimate move, $A$ has one as well. Since the game must end (the number of stones strictly decreases), this implies that $A$ wins. Indeed, note that $B$ must make a move involving at least one of the $2$ piles with the least number of stones. Thus, the game will last at most $2008$ more moves, so the last two piles must have a stone every turn before the game ends. Now, whichever move $B$ makes $A$ copies. $A$ can always copy the move since if $B$ makes a move on the first two piles, it leaves that pile with an odd number of stones, so $A$ can make the same move and make the number of stones in the pile even again. Also, the moves on the last two piles are always possible by the aforementioned argument. Hence, $A$ can always move after $B$ and as a consequence, wins. $\blacksquare$