There exists $ n \in \mathbb{N}_0$ and $ (a_1,a_2,\ldots,a_n) \in \mathbb{N}^n$ such that $ \min\{a_1,a_n\} > 0$ and such that if $ a_1$ represents the (initial) number of coins in the square $ x$ then $ a_i$ represents number of coins in the square $ x + i - 1$. Define also $ y: = \sum_{i = 1}^n{a_i}$. Obviously all coins stay always in squares $ \ge x - y$ and always in squares $ \le x + n - 1 + y$, and we can wlog assume $ x - y$ the is the square number 0, so all moves is done in a finite number of squares. So for each time there exist a $ (n + 2y + 2)$-upla of non negative integer $ (a_0,a_1,a_2,\ldots,a_{n + 2y + 1})$ with sum $ y$ such that $ a_i$ represents number of coins in the square $ i$. Now the number $ \sum_{i = 0}^{n + 2y + 1}{i^2a_i}$ increases at each step by 2, and it is always less of $ y(n + 2l + 1)^2$: it shows that the algorithm finishes in a finite number of steps. It remains only to show that we'll have always the same number of moves and the final configuration is invariant by the algorithm chosen. Denote with $ h_i$ the number of moves done at the end of the game in the square $ i$. Then the final number of coins in the square $ i$ is $ a_i + h_{i + 1} - 2h_i + h_{i - 1} \in \{0,1\}$. Assume by contradiction that there exists two distinct sequence $ \{h_i\}$ and $ \{H_i\}$ that satisfies the previous relation. Then we can choose $ \{a_i\}_{0 \le i \le n + 2y + 1}$ s.t. $ S: = \min\{\sum{h_i},\sum{H_i}\}$ reaches minimum. Since the initial configuration is the same by assumption, then there exist $ 0 < j < n + 2y - 1$ s.t. $ a_j > 1$, but now the $ n + 2y + 2$ upla of non negative integers $ (a_0,a_1,\ldots,a_{j - 1} + 1,a_j - 2,a_{j + 1} + 1,\ldots,a_{n + 2y - 1})$ reaches a new minimum in S, contradiction.

bboypa wrote: There exists $ n \in \mathbb{N}_0$ and $ (a_1,a_2,\ldots,a_n) \in \mathbb{N}^n$ such that $ \min\{a_1,a_n\} > 0$ and such that if $ a_1$ represents the (initial) number of coins in the square $ x$ then $ a_i$ represents number of coins in the square $ x + i - 1$. Define also $ y: = \sum_{i = 1}^n{a_i}$. Obviously all coins stay always in squares $ \ge x - y$ and always in squares $ \le x + n - 1 + y$, and we can wlog assume $ x - y$ the is the square number 0, so all moves is done in a finite number of squares. So for each time there exist a $ (n + 2y + 2)$-upla of non negative integer $ (a_0,a_1,a_2,\ldots,a_{n + 2y + 1})$ with sum $ y$ such that $ a_i$ represents number of coins in the square $ i$. Now the number $ \sum_{i = 0}^{n + 2y + 1}{i^2a_i}$ increases at each step by 2, and it is always less of $ y(n + 2l + 1)^2$: it shows that the algorithm finishes in a finite number of steps. It remains only to show that we'll have always the same number of moves and the final configuration is invariant by the algorithm chosen. Denote with $ h_i$ the number of moves done at the end of the game in the square $ i$. Then the final number of coins in the square $ i$ is $ a_i + h_{i + 1} - 2h_i + h_{i - 1} \in \{0,1\}$. Assume by contradiction that there exists two distinct sequence $ \{h_i\}$ and $ \{H_i\}$ that satisfies the previous relation. Then we can choose $ \{a_i\}_{0 \le i \le n + 2y + 1}$ s.t. $ S: = \min\{\sum{h_i},\sum{H_i}\}$ reaches minimum. Since the initial configuration is the same by assumption, then there exist $ 0 < j < n + 2y - 1$ s.t. $ a_j > 1$, but now the $ n + 2y + 2$ upla of non negative integers $ (a_0,a_1,\ldots,a_{j - 1} + 1,a_j - 2,a_{j + 1} + 1,\ldots,a_{n + 2y - 1})$ reaches a new minimum in S, contradiction. I do not understand the lasst step. How is this a contradiction? More over, even if it is, then why does this imply that they must end in the same configuration?

lokitos wrote: Look at all the moves legal from the starting position- all of them must be made at some point. No move we make now can block off a different move in the future, so we might as well make every initially legal move simultaneously. For someone like me with terrible intuition, here's an easier way to see this (basically induction): suppose that we have two sequences of moves $(r_1,\ldots,r_m)$ and $s=(s_1,\ldots,s_n)$. Then initially, square $r_1$ must have at least $2$ coins, so there must exist $1\le i\le n$ such that $s_i=r_1$. WLOG $s_1=r_1$. (If not, then letting $i_0>0$ denote the smallest such $i$, it's easy to verify that the sequence $s'=(s_{i_0}=r_1,s_1,\ldots,s_{i_0-1},s_{i_0+1},\ldots,s_n)$ is equivalent to the sequence $s$.) Now we can just operate on $r_1$ and then induct to show that $r$ is a permutation of $s$.

It seems that I don't understand any of the solutions posted here... But combined together, they make sense. bboypa wrote: There exists $ n \in \mathbb{N}_0$ and $ (a_1,a_2,\ldots,a_n) \in \mathbb{N}^n$ such that $ \min\{a_1,a_n\} > 0$ and such that if $ a_1$ represents the (initial) number of coins in the square $ x$ then $ a_i$ represents number of coins in the square $ x + i - 1$. Define also $ y: = \sum_{i = 1}^n{a_i}$. Obviously all coins stay always in squares $ \ge x - y$ and always in squares $ \le x + n - 1 + y$, and we can wlog assume $ x - y$ the is the square number 0, so all moves is done in a finite number of squares. Sorry to say, but I don't understand any of this. What is $n$? What are the $a_i$? Why are all moves done in a finite number of squares? lokitos wrote: Note that moves are commutative- that is, the final configuration depends only on which moves we make, not on what order we make them in. Why? (I am aware that this is true, but I only know how to prove it using the stabilization property, i. e., the fact that final configurations always exist. How do you show this at this point, way before you have proven the stabilization property?) lokitos wrote: No move can create a gap between two piles of coins wider than any gap that already exists, Okay, I finally understood what you mean here with the help of Naphthalin. The claim is that the "maximum gap" (i. e., the highest distance $j-i$ between two distinct integers $i$ and $j$ such that $i<j$ and such that there are coins at the places $i$ and $j$ but no coins anywhere inbetween) can only decrease but never increase by a move. This is only true when this "maximum gap" is $>0$. Fortunately, this is okay because all we want is that this "maximum gap" is bounded a-priori. We are now discussing a more complex version of this problem at https://www.artofproblemsolving.com/Forum/viewtopic.php?f=41&t=428298 . My post there (after some minor modifications) also gives a solution of this problem.

darij grinberg wrote: It seems that I don't understand any of the solutions posted here... But combined together, they make sense. Sorry to say, but I don't understand any of this. What is $n$? What are the $a_i$? Why are all moves done in a finite number of squares? $a_1>0$ is the number of coins in the first non empty square, called $x$; $a_i \ge 0$ is the number of coins in the square $x+i-1$, for all $i=1,2,\ldots,n-1$; $a_n>0$ is the number of coins in the last non empty square, placed in $x+n-1$. why finite number of squares? Just think about the best and the worst case..

Oh, I see. You're talking about the initial configuration. I still don't see why this: bboypa wrote: Obviously all coins stay always in squares $ \ge x - y$ and always in squares $ \le x + n - 1 + y$ is "obvious". (I agree that this is true and easy to show after the problem is solved...)

bboypa wrote: Then we can choose $ \{a_i\}_{0 \le i \le n + 2y + 1}$ s.t. $ S: = \min\{\sum{h_i},\sum{H_i}\}$ reaches minimum. Since the initial configuration is the same by assumption, then there exist $ 0 < j < n + 2y - 1$ s.t. $ a_j > 1$, but now the $ n + 2y + 2$ upla of non negative integers $ (a_0,a_1,\ldots,a_{j - 1} + 1,a_j - 2,a_{j + 1} + 1,\ldots,a_{n + 2y - 1})$ reaches a new minimum in S, contradiction. We need to prove: If $\sum {{H_i}} = 0$,there not exist no zero sequence $\left\{ {{h_i}} \right\}$ satisfies ${a_i} + {h_{i + 1}} - 2{h_i} + {h_{i - 1}} \in \left\{ {0,1} \right\}$.

A terribly long, but rather straightforward approach may be found here.

I have also outlined a solution of the $2$-dimensional analogue of this exercise (i.e., coins are placed on the integer lattice $\mathbb{Z}^2$ rather than on $\mathbb{Z}$, and accordingly at each step we take $4$ coins from a point and distribute them among its $3$ neighboring squares) in Math 5707 Spring 2017 homework set #5 exercise 5. There are a bunch of illustrations in a recent popular article: Jordan Ellenberg, *The Amazing, Autotuning Sandpile*, Nautilus.

Solution from Twitch Solves ISL: First part: We start by proving the procedure always terminates. Index the squares by ${\mathbb Z}$. Claim: For any starting configuration, there exists an interval $[A,B]$ such that no coin may ever exit $B$. Proof. Let $n$ be the largest index of a square with any coins. Note that for any square $m > n$, the following property is true: if $m$ ever gains a coin, then forever after, either $m$ or $m+1$ has a coin. This follows since any move affecting either $m$ or $m+1$ will add a coin to at least one of them. Thus, we make take $B = m + 2c$ where $c$ is the number of coins. The choice of $A$ is similar. $\blacksquare$ Now note that the sum of squares of indices of coins increases each step. This shows that configurations may never repeat; but there are finitely many configurations, ensuring termination. Second part: Suppose $S = (x_1, \dots, x_n)$ is a valid sequence of moves that leads to an end state. We perform the following procedure for $i = 1, \dots, n$. Before the $i$'th move $s_i$, look at the leftmost square which has more than one coin. It must be operated on eventually, since that is the only way it can lose coins. Let $x_j$ be the first such move on this square. Rearrange the sequence so that this move $x_j$ comes next instead. That is, apply the change \[ (x_i, x_{i+1}, \dots, x_{j-1}, x_j) \longmapsto \left( x_j, x_i, x_{i+1}, \dots, x_{j-1} \right). \]Note that validity of the whole operation is preserved. In this way, any valid sequence can be rearranged to a certain canonical sequence where one always operates on the leftmost possible square. This implies that the lengths of all valid sequences are the same (actually, they are permutations of each other), and also that the ending states match.

First we claim that there exists an interval $[A,B]$ which the coins can never leave, say there doesn't exist such $B$, now if there doesn't exist such $B$, we can reach any square on the right hand side, but that's a contradiction because like consider the rightmost square in the initial configuration, note that if you start from moving $k$ coins towards the right, the number of coins moving towards the right decreases each step, it'll never be $k$ again (due to symmetry of distribution), atmost it can be of the form $k/2 + k/8 ... k/2^{n}$ but that is never equal to $k$ for some finite $k$, so eventually at some point we'll not be able to move on the right hand side. Similar argument holds for the left hand side. Now note that the sum of the square of the coin's indices increase each step so the process terminates. Now no matter how you move, you'll always have the same permutation of moves, so we end up in the same final configuration again.

Set the row of squares on the positive integer line, so we will say a square is larger than another if it represents a higher number. First note that the coins are bounded in some finite interval, meaning that there is some two squares $x$ and $y$ so that no coin will be able to reach boxes $x + 1$ and $y - 1$. This is true since any group of coins past the largest box $m$ must "leave" behind coins if we try to move the group of coins to larger boxes, so eventually our group of coins will diminish. Now consider the product of all of the coin's placements. By difference of squares the product of all coins will decrease every move, and since the coins are bounded in an interval, the process will terminate in a finite amount of moves. Now we proceed using a bit of local. Consider the sequence $(x_1, x_2, \dots, x_n)$ with each $x_i$ representing which square we chose to operate on, where on each move we greedily choose the largest square(on the number line) that we can perform a valid move on. Then consider another arbitrary sequence $(y_1, y_2, \dots, y_m)$ and FTSOC assume that the two sequences have a different number of moves/ending state. Then notice that $\{x_i\} \in \{y_i\}$ otherwise this is a contradiction since we must eventually operate on squares with more than $1$ coin. We can swap $x_1$ with $y_1$ and so on, to get a new sequence which contains exactly the same amount of moves. This sequence also has the same ending state since moves are commutative. However, we get $(x_1, x_2, \dots, x_n, \dots)$, which is contradictory since the sequence terminates after $x_n$, done.

Let the row of squares be numberd $\mathbb{Z}.$ Firstly, note that for any two neighboring squares, if a coin ever enters, than in that pair there will always be at least one coin. Therefore there is a set interval that a coin may never exit. Now, note that the product of the positions of all coins decreases by $1$ each turn. Therefore we may never repeat a position. Now, we can always operate on the leftmost square with more than $1$ coin because it won't affect any of the later moves and that the leftmost square has to be operated on in the future. The choice of leftmost is arbitrary. Becaues of this we're done$.\blacksquare$

Here are two proves to show the proccess eventually ends.

Here's a little bit different sol (outline is same tho): Consider the coins into the $\mathbb Z$ line. Claim: There exists some interval $[A, B]$ such that no coin ever exits the interval. Proof: Consider the left-most square $S_k$ having some coin(s). We will prove that, the coins cant cross beyond $S_{k-n+1}$. One can prove using induction that: $$\sum a_{k-i}+a_{k-i+1}+\cdots \ge i+1 $$for all $ i \ge 0$ (By solving the inductive assumption using proof though contradiction). Similarly for the right most square, we can get bound. WLOG assume the interval $[A, B]$ to be $[1, N]$. Now, consider the mono-variant: $I = \sum_{k=1}^{N} p_i^2$ where $p_i = a_1 + \cdots + a_i $ (prefix sum). Note that, there are only finite number of configurations and $I$ is strictly decreasing monovariant as (consider a move at square $S_k$): $$I'-I = 2(p_{k-1}-p_k) < 0.$$