Track / Stage 7 / 22 of 300 #1422 of 1964

Problem 1422

National olympiad second round; IMO P1/P4

Combinatorics Difficulty 7.0 Prove it

Around a round table the people $P_1, P_2,..., P_{2013}$ are seated in a clockwise order. Each person starts with a certain amount of coins (possibly none); there are a total of $10000$ coins. Starting with $P_1$ and proceeding in clockwise order, each person does the following on their turn:

[list][*]If they have an even number of coins, they give all of their coins to their neighbor to the left.

[*]If they have an odd number of coins, they give their neighbor to the left an odd number of coins (at least $1$ and at most all of their coins) and keep the rest.[/list]

Prove that, repeating this procedure, there will necessarily be a point where one person has all of the coins.

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official solution

1. Initial Setup and Parity Argument:
- We start with 2013 people, each with a certain number of coins, and the total number of coins is 10000.
- Note that 10000 is an even number. This implies that the sum of the coins held by all people is even.
- If we consider the parity (odd or even nature) of the number of coins each person has, the sum of the parities must also be even. This means there must be an even number of people with an odd number of coins.

2. Behavior of Coin Distribution:
- Each person follows a specific rule based on whether they have an even or odd number of coins:
- If a person has an even number of coins, they give all their coins to their neighbor to the left.
- If a person has an odd number of coins, they give an odd number of coins (at least 1 and at most all) to their neighbor to the left and keep the rest.
- When a person with an odd number of coins gives an odd number of coins to their neighbor, they are left with an even number of coins.

3. Propagation of Parity Changes:
- Consider a person $P_i$ with an odd number of coins. When $P_i$ gives an odd number of coins to $P_{i-1}$ :
- $P_i$ will have an even number of coins after the transaction.
- $P_{i-1}$ will change its parity (if $P_{i-1}$ had an even number of coins, it will now have an odd number, and vice versa).
- This process continues, and the parity of the number of coins held by each person changes as coins are passed around.

4. Eventual Convergence to Even Parity:
- Since the total number of coins is even, and the parity of the total number of coins remains unchanged, the system will eventually reach a state where all people have an even number of coins.
- When all people have an even number of coins, each person will give all their coins to their neighbor to the left in their turn.

5. Final State:
- Once all people have an even number of coins, the process will continue until one person ends up with all the coins.
- This is because, in each round, the coins are being consolidated towards one person as each person gives all their coins to their neighbor.

Therefore, the process will necessarily reach a point where one person has all the coins.

$\blacksquare$

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