Competition problem — Combinatorics

Library / /34 of 43

Combinatorics Difficulty 6.3 National Olympiad Prove it JBMO

Problem:

There are two piles of coins, each containing $2010$ pieces. Two players $A$ and $B$ play a game taking turns ( $A$ plays first). At each turn, the player on play has to take one or more coins from one pile or exactly one coin from each pile. Whoever takes the last coin is the winner. Which player will win if they both play in the best possible way?

Solution

Solution:

$B$ wins.

In fact, we will show that $A$ will lose if the total number of coins is a multiple of $3$ and the two piles differ by not more than one coin (call this a balanced position). To this end, firstly notice that it is not possible to move from one balanced position to another. The winning strategy for $B$ consists in returning $A$ to a balanced position (notice that the initial position is a balanced position).

There are two types of balanced positions; for each of them consider the moves of $A$ and the replies of $B$ .

If the number in each pile is a multiple of $3$ and there is at least one coin:
- if $A$ takes $3n$ coins from one pile, then $B$ takes $3n$ coins from the other one.
- if $A$ takes $3n+1$ coins from one pile, then $B$ takes $3n+2$ coins from the other one.
- if $A$ takes $3n+2$ coins from one pile, then $B$ takes $3n+1$ coins from the other one.
- if $A$ takes a coin from each pile, then $B$ takes one coin from one pile.

If the numbers are not multiples of $3$ , then we have $3m+1$ coins in one pile and $3m+2$ in the other one. Hence:
- if $A$ takes $3n$ coins from one pile, then $B$ takes $3n$ coins from the other one.
- if $A$ takes $3n+1$ coins from the first pile ( $n \leq m$ ), then $B$ takes $3n+2$ coins from the second one.
- if $A$ takes $3n+2$ coins from the second pile ( $n \leq m$ ), then $B$ takes $3n+1$ coins from the first one.
- if $A$ takes $3n+2$ coins from the first pile ( $n \leq m-1$ ), then $B$ takes $3n+4$ coins from the second one.
- if $A$ takes $3n+1$ coins from the second pile ( $n \leq m$ ), then $B$ takes $3n-1$ coins from the first one. This is impossible if $A$ has taken only one coin from the second pile; in this case $B$ takes one coin from each pile.
- if $A$ takes a coin from each pile, then $B$ takes one coin from the second pile.

In all these cases, the position after $B$ 's move is again a balanced position. Since the number of coins decreases and $(0, 0)$ is a balanced position, after a finite number of moves, there will be no coins left after $B$ 's move. Thus, $B$ wins.

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: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.