55 Coins- / Young-Diagram Rearrangment-Riddle

Question

this has been a riddle to difficult for me to understand the solution some year ago. Even though the riddle seems really easy.

You have got 55 coins. Someone builds an arbitrary number m of stacks of arbitrary size out of them. Each step you take away one coin from each stack and out of these you build a new stack with m coins. Repeating this process you eventually get ten stacks with size 1, 2, 3, 4, 5, 6, 7, 8, 9 and 10 (adds up to 55). Now the procedure will reproduce this constellation.

Question: Why does this constellation always occur?

Equivalent to: Why is there no other constellation that reproduces itself alfter a certain amount of steps? For example suppose it had been 4 coins. then $ (1,3) \rightarrow (2,2) \rightarrow (1,1,2) \rightarrow (1,3) $ is such a multi-step loop. If, there would be any multistep loop with 55 coins, we wouldn't reach the position $ (1,2,3,4,5,6,7,8,9,10) $, hence there can not be a multi-step loop. On the other hand, if there is no, then after finitely many steps we reach the $ (1,2,...,10) $ position, in order to not repeat ourself in any other way, which would be contradicting the non-existence of multi-step-loops. (There is no other single-step-loop than the $ (1,2,3,4,5,6,7,8,9,19) $ one. The proof is straight forward.)

You can translate this problem into Young Diagrams. The solution I overheard some working mathematicians discuss did this, but I was not able to follow the arguments back than. They themself claimed the solution to be quite hard. This was the final riddle of some big mathematicians-riddle contest, they said. I hope this is not a duplicate, I have searched the side and the web, but I didn't find anything.

Answer 1

It's apparent that the number of stacks will tend towards a value dependent on the square root of the number of coins. With a large number of stacks, these will be small and within a few steps will be exhausted by the re-stacking process; with large stacks this will generate more stacks than are destroyed. The slowest case of course is when a big initial (or step-1) stack has to be gradually whittled down.

Then if we consider a stacking where the number of stacks is roughly equal to the number of coins in each stack, we build up a series of stacks of increasing height (delta=2 in height) as those stacks are diminished. Once the original stacks are gone, the varying-height stacks are also gradually depleted on alternate steps giving a more gradually varying height which relaxes to the triangular formation.

These are just initial impressions; I'm going to go build a model of the process and update this with any more concrete insights I can find.

Answer 2

Hmm. If the number of stacks is constant, as must be the case in a fixed point, then exactly one of the stacks contains exactly one coin, which will disappear in the next stage (to be replaced by a stack of $m$ coins). If there were multiple one-coin stacks, then all the one-coin stacks would disappear, and the total number of stacks would decrease.

A one-coin stack can only be newly created if the previous stage contained a single stack of $55$ coins, so in a fixed point, the one-coin stack must previously have been a two-coin stack. Therefore, there must also be a two-coin stack in the fixed point. There can only be one, because multiple two-coin stacks become multiple one-coin stacks in the next stage, and the fixed point contains only a single one-coin stack.

Similarly, the single two-coin stack must previously have been a single three-coin stack, which by virtue of the fixed point must also be in the current arrangement. It seems to me that one can continue this line of reasoning to obtain the fixed-point solution $(10, 9, 8, 7, 6, 5, 4, 3, 2, 1)$. Only triangular numbers would appear to have fixed-point solutions; other numbers have loops of length greater than $1$. For instance, $4$ generates the sequence $(3, 1) \to (2, 2) \to (2, 1, 1) \to (3, 1) \to \cdots$.