Ten dwarfs are seated around a table. At the beginning, one of them has ten gold coins. Every minute,

combinatorics

Ten dwarves are seated around a table. At the beginning, one of them has ten gold coins. Every minute, the dwarves check to see if one of them has more than one piece. If yes then exactly one of these gives one coin to each of its two neighbours. Is it possible to arrive at the situation where each dwarf has exactly one piece?

I think one thing is conserved and that is the fact that at each step there's at least one dwarf that has an even number of coins , and so the situation is impossible, I still don't know how to prove it

Best Answer

Consider the number of coins held by dwarves sitting in even-numbered seats (seats starting at the "rich" dwarf and counting every other seat going around the circle). What happens when a dwarf is chosen to give away coins?

If the dwarf is in an even seat, then the number of coins owned by the even seats goes down by 2.

If the dwarf is in an odd seat, then his two neighbors (both even seats) gain one each, so the total goes up by two.

Since these are the only ways by which coins can move, the end result is that the number held by even-numbered seats can only go up or down by 2's.

Now, we start with all 10 coins in even-numbered seats. (The "rich" dwarf is at an even seat.) If we consider the case where everybody has 1 coin, that means there's 5 coins in even seats. But this is impossible, since we cannot get to 5 by adding/subtracting 2's from 10.

Thus it is not possible to evenly distribute the coins using the method described.