Competition problem — Combinatorics

Library / /23 of 32

Combinatorics Difficulty 6.5 National olympiad Prove it Netherlands

Around a round table $n \ge 3$ players are sitting. The game leader divides $n$ coins among the players, in such a way that not everyone gets exactly one coin. Any player can see the number of coins of each other player. Every 10 seconds, the game leader rings a bell. At that moment, each player looks how many coins their two neighbours have. Then they all do the following at the same time:
* If a player has more coins than at least one of their neighbours, the player gives away exactly one coin. They give this coin to the neighbour with the smallest number of coins. If both of their neighbours have the same number of coins, they give the coin to the neighbour on the left.
* If a player does not have more coins than at least one of their neighbours, the player does nothing and waits for the next round.
The game ends if everyone has exactly one coin.

a) For each $n \ge 3$ , find a distribution of the coins at the start such that the game will never stop (and prove that the game does not stop for your starting distribution).

b) For each $n \ge 4$ , find a distribution of the coins at the start of the game such that the game will stop (and prove that the game stops for your starting distribution).

Solution

(a) Consider the situation where the first player has 2 coins, the second player has 0 coins and all other players have 1 coin. This situation looks as follows:
$\underbrace{2011\cdots11}_{n-2 \text{ ones}}$
For example, for $n=3$ the starting distribution is 201. We see that the first and the third player both give a coin to the second player. This gives the distribution 120. This is exactly the distribution 201 if you shift all players by one place. We see that the game never stops. In this case the first player has to give a coin to the second player, the third player has to give a coin to the left and all other players keep their coin. We end with the following situation.
$\underbrace{12011\cdots11}_{n-3 \text{ ones}}$
This is exactly the same distribution as the starting distribution, except now it is player 2 that has 2 coins and player 3 that has 0 coins. If we continue playing, there will always be a player with 2 coins and thus the game never stops. □

(b) For $n \ge 4$ we can consider the following starting distribution.
$2002\underbrace{11\cdots11}_{n-4 \text{ ones}}$
For example, for $n = 4$ the starting distribution is 2002. In this case there is no player with exactly one coin. The first and the last player give a coin to the second and third player, respectively. Then the game stops.
The first player has to give a coin to the right and the fourth player has to give a coin to the left. All other players keep their coin. This gives a situation where all players have 1 coin, thus the game stops. ☐

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 and solution reproduced as published; topic and difficulty added by this site.