A game with coins

129 Views Asked by At

You have 15 coins which are split to number of piles, in each step you must collect 1 coin from each pile and form a new pile and so on.

Prove that no matter how the arrangement was in the beginning you will end up in the stable case in which you have 5 piles of coins (1 with 1 coin, one with 2 coins .. till 1 with 5 coins).

It can be generalized to a number of coins N which equals N=m(m+1) where m is natural

2

There are 2 best solutions below

3
On

generale case :

First you can show that because the number of pile is constant, exactly one pile should have one coin at each step.

Then by induction you can show that for each $i$ less or equal to the number of pile. There is exactly one pile with $i$ coins.

0
On

As Levgeni shows above, a single fixed state (as opposed to a cycle which loops through multiple states) must have the form $(1,2,3,\dots,n)$.

I can also show that any state that differs from a $(1,2,3,\dots,n)$ state by $1$ in one or more places will be part of cycle of length $n+1$. So for $16$ coins, for example, there is a cycle

$(1,2,3,4,6) \rightarrow (1,2,3,5,5) \rightarrow (1,2,4,4,5) \rightarrow (1,3,3,4,5) \rightarrow (2,2,3,4,5) \rightarrow (1,1,2,3,4,5) \rightarrow (1,2,3,4,6)$

and for $17$ coins there are two distinct $6$-cycles:

$(1,2,3,5,6) \rightarrow (1,2,4,5,5) \rightarrow (1,3,4,4,5) \rightarrow (2,3,3,4,5) \rightarrow (1,2,2,3,4,5) \rightarrow (1,1,2,3,4,6) \rightarrow (1,2,3,5,6)$

and

$(1,2,4,4,6) \rightarrow (1,3,3,5,5) \rightarrow (2,2,4,4,5) \rightarrow (1,1,3,3,4,5) \rightarrow (2,2,3,4,6) \rightarrow (1,1,2,3,5,5) \rightarrow (1,2,4,4,6)$

I cannot yet prove that these are the only possible cycles.