AoPS - Problem

Source: CentroAmerican 2013 Problem 2

Tags: combinatorics unsolved, combinatorics, Processes

fprosk

24.08.2013 22:59

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: 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. Prove that, repeating this procedure, there will necessarily be a point where one person has all of the coins.

Perhaps I'm missing something, but the problem looks absolutely trivial. It is clear that if we prove that at one point all the people have an even number of coins, we are done. If there are people with an odd number of coins, there must be an even number of them, since the total is $10000$. So, when a player has an odd number of coins, he will give his neighbour an odd number and leave an even number for himself. If his neighbour had an odd number of coins, then he'll have now an even number, just like the neighbour who passed him the coins, so it's allright. Otherwise, the process will continue until we find a player which had an odd number, whose existence is guaranteed by the parity of $10000$. So we're done