We have two piles with and coins respectively.
Ann and Bob take alternate turns making the following moves:
The player whose turn is to move picks a pile with at least two coins, removes from that pile coins for some , and adds to the other pile coin. The players can choose a different at each turn, and the player who cannot make a move loses.
If Ann plays \ffirst determine which player has a winning strategy.
Solution
To determine which player has a winning strategy, we begin by examining the rules of the game. Ann and Bob are alternating turns starting with Ann. They can move coins between two piles based on the rules specified, and the player unable to make a move loses.
Initially, the piles have 2000 and 2017 coins, respectively:
-
-
The key observation in this problem is to consider the total number of coins after each permitted move.
- A move consists of taking coins (where ) from one pile and adding 1 coin to the other pile.
- Therefore, the total number of coins decreases by for each move since we remove coins but only add 1 coin, leading to a decrease of 1, 2, or 3 coins depending on .
The total initial coins are:
The game proceeds until no valid moves can be made. A player cannot move if both piles have fewer than 2 coins.
We define positions in the game as winning or losing:
- A losing position is one where any move leaves the opponent in a winning position.
- A winning position is one where at least one move puts the opponent in a losing position.
To determine winning and losing positions, we need to focus on the total number of coins modulo the impact of :
- Since every move reduces the total number of coins by either 1, 2, or 3, observe that the difference in each move is modulo 3.
Determine the parity in terms of modulo 3:
- Initial total:
The player forced into positions when the total is congruent to 0 modulo 3 will face eventual defeat because every move leaves it in again.
Thus if we observe the strategy in Pam’s turn, her initial and subsequent turns face a zero modulo 3, implying she can't avoid leaving Bob a winning situation, confirming he eventually forces her into a decision twice or once with only valid exit options.
Therefore, Bob will have a winning strategy based on current parity strategies, ensuring he always has an option to return to .
Hence, the player with a winning strategy:
```