Two players, A and B, play the following game: they retire coins of a pile which contains initially 2006 coins. The players play removing alternatingly, in each move, from 1 to 7 coins, each player keeps the coins that retires. If a player wishes he can pass(he doesn't retire any coin), but to do that he must pay 7 coins from the ones he retired from the pile in past moves. These 7 coins are taken to a separated box and don't interfere in the game any more. The winner is the one who retires the last coin, and A starts the game. Determine which player can win for sure, it doesn't matter how the other one plays. Show the winning strategy and explain why it works.
Solution
To solve this problem, we need to analyze the structure of the game to determine a winning strategy for player A. We start with 2006 coins, and players alternate turns, removing between 1 and 7 coins on each move. Additionally, a player may pass their turn by paying 7 coins from their own collected coins into a separate box. The objective is to take the last coin.
Step 1: Basic Analysis
First, let's consider the state of the game at crucial checkpoints. The player who is forced to move when exactly 1 coin remains will lose because they have no choice but to take the last coin, thus handing victory to the opponent.
Step 2: Losing and Winning Positions
- Losing Position: A position is losing if every possible move leaves the opponent in a winning position.
- Winning Position: A position is winning if there exists a move that places the opponent in a losing position.
Step 3: Calculate Losing Positions
By examining different positions via backward induction, we reason that:
- Positions with 1 coin are losing—since the player must take the last coin and lose.
- Positions with 9 coins are also losing, because whatever move (from 1 to 7 coins) the player makes will always leave 2 coins or more (i.e., 2 to 8 coins) for the opponent, who can then remove the remaining coins efficiently to force the competitor back into a critical losing scenario such as 1 coin.
Thus, crucial losing positions will repeat every 8 coins, starting from 1, which is .
Step 4: Initial Position Analysis
If the initial number of coins (2006) is not part of the series of losing positions calculated above, then player A can force a win. To ensure this, player A should always leave player B with a losing position derived from the sequence 1, 9, 17, 25, \ldots (namely, a multiple of 8 plus 1).
2006 coins is not one of these losing positions (since 2006 mod 8 = 2), meaning player A automatically starts in a winning configuration where they can always control the game to converge towards a losing position for player B.
Conclusion: Strategy for Player A
- On every turn, player A should aim to adjust the number of coins so that player B is left in one of these losing configurations.
- If player A starts with 2006 coins, they remove 2 coins during their first turn, reducing the pile to 2004 coins, which is a losing position for B (since ).
Thus, through strategic manipulation and optimal play, player A can control the game flow and ensure victory.
In summary, the winning strategy for player A is adjusting moves to continuously leave player B in a series of calculated losing positions derived from the sequence structure, ensuring player A ultimately claims the last coin.