Maths Olympiad Prep

Library / /16 of 19

Combinatorics Difficulty 6.8 National olympiad Find the answer

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.

A number or a short expression. Spacing and $ signs are ignored.

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 1,9,17,25, 1, 9, 17, 25, \ldots .

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 2004=250×8+42004 = 250 \times 8 + 4).

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.

Player A can win for sure \boxed{\text{Player A can win for sure}}

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.