Let $n$ be a natural number.
You are given $\frac{n(n+1)}{2}$ coins which are arranged in towers. Every turn you pick up the top coin of each tower and gather all these into a new tower. Prove that eventually (after finitely many turns) you get towers of the following heights: $\{{ 1,2,3,\dots,n }\}$.
For example: for $n = 6$ (number of coins $21$): and for the initial state of towers: $\{{17, 2, 1, 1}\}$
- Inital state: $\{{17, 2, 1, 1}\}$
- Turn 1: $\{{16, 1, 4}\}$
- Turn 2: $\{{15, 3, 3}\}$
- Turn 3: $\{{14, 2, 2, 3}\}$
- Turn 4: $\{{13, 1, 1, 2, 4}\}$
- Turn 5: $\{{12, 1, 3, 5}\}$
- Turn 6: $\{{11, 2, 4, 4}\}$
- Turn 7: $\{{10, 1, 3, 3, 4}\}$
- Turn 8: $\{{9, 2, 2, 3, 5}\}$
- Turn 9: $\{{8, 1, 1, 2, 4, 5}\}$
- Turn 10: $\{{7, 1, 3, 4, 6}\}$
- Turn 11: $\{{6, 2, 3, 5, 5}\}$
- Turn 12: $\{{5, 1, 2, 4, 4, 5}\}$
- Turn 13: $\{{4, 1, 3, 3, 4, 6}\}$
- Turn 14: $\{{3, 2, 2, 3, 5, 6}\}$
- Turn 15: $\{{2, 1, 1, 2, 4, 5, 6}\}$
- Turn 16: $\{{1, 1, 3, 4, 5, 7}\}$
- Turn 17: $\{{2, 3, 4, 6, 6}\}$
- Turn 18: $\{{1, 2, 3, 5, 5, 5}\}$
- Turn 19: $\{{1, 2, 4, 4, 4, 6}\}$
- Turn 20: $\{{1, 3, 3, 3, 5, 6}\}$
- Turn 21: $\{{2, 2, 2, 4, 5, 6}\}$
- Turn 22: $\{{1, 1, 1, 3, 4, 5, 6}\}$
- Turn 23: $\{{2, 3, 4, 5, 7}\}$
- Turn 24: $\{{1, 2, 3, 4, 6, 5}\}$