Maths Olympiad Prep

Library / /26 of 30

Combinatorics Difficulty 6.4 National olympiad Find the answer

We have two piles with 20002000 and 20172017 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 tt coins for some 2t42\le t \le 4, and adds to the other pile 11 coin. The players can choose a different tt at each turn, and the player who cannot make a move loses.
If Ann plays \ffirst determine which player has a winning strategy.

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

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:
- P1=2000 P_1 = 2000
- P2=2017 P_2 = 2017

The key observation in this problem is to consider the total number of coins after each permitted move.
- A move consists of taking t t coins (where 2t4 2 \leq t \leq 4 ) from one pile and adding 1 coin to the other pile.
- Therefore, the total number of coins decreases by t1 t - 1 for each move since we remove t t coins but only add 1 coin, leading to a decrease of 1, 2, or 3 coins depending on t t .

The total initial coins are:
T=2000+2017=4017 T = 2000 + 2017 = 4017
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 t t :
- 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: T40170 (mod 3) T \equiv 4017 \equiv 0 \ (\text{mod} \ 3)

The player forced into positions when the total is congruent to 0 modulo 3 will face eventual defeat because every move leaves it in (3k0)0(mod3) (3k - 0) \equiv 0 \pmod{3} 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 T0 (mod 3) T \equiv 0 \ (\text{mod} \ 3) .

Hence, the player with a winning strategy:
Bob has a winning strategy. \text{Bob has a winning strategy.}

Bob has a winning strategy.\boxed{\text{Bob has a winning strategy.}}
```

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.