Please post your solutions. This is just a solution template to write up your solutions in a nice way and formatted in LaTeX. But maybe your solution is so well written that this is not required finally. For more information and instructions regarding the ISL/ILL problems please look here: introduction for the IMO ShortList/LongList project and regardingsolutions

1) First of all, we need to show that we do eventually have to stop. This is clear because each time we move a pebble goes to the right, and we can't go arbitrarily far to the right, because each pebble (except for those on the first column) has another pebble immediately to its left, so we would need infinitely many pebbles. This shows that there always is a final configuration. 2) Another thing we notice is that a final configuration consists of columns of decreasing length (from left to right). This is because before and after each move, this property is clearly conserved. Moreover, the difference between a column and its right neighbour is $0$ or $1$, because otherwise we would be able to continue moving the pebbles. 3) In a final configuration we can't have three consecutive columns of equal lengths. This is true because if we look at the last move performed on one of the three columns, then we see that no matter how we make that move, before we make it we need two consecutive columns s.t. the one on the left has fewer pebbles than the one on the right, and this is impossible. In fact, this shows that we never have three equal consecutive columns (not just in final configurations). 4) In a final configuration we can't have two different pairs of equal consecutive columns. Consider two such pairs $c_1,c_2$ and $c_1',c_2'$, s.t. $c_1'$ is to the right of $c_2$, which don't have any other such pairs between them. Since this is a final config, the columns between $c_2$ and $c_1'$ inclusive form a decreasing arithmetic progression with common difference $-1$. We can now retrace the steps until we get two pairs of equal columns which are adjacent and which differ in length by $1$, and this is clearly impossible (consider, for example, $3,3,2,2$; no matter how we try to obtain this, we can't avoid either two consecutive solumns s.t. the one on the left is shorter, or three equal consecutive columns, and we have examined these situations before). These conditions show that the final configuration is unique, because each $n$ has only one decomposition as a sum of different numbers except, maybe, for a pair, and this decomposition is obtained as follows: assume we have $T_{k-1}=\frac{(k-1)k}2<n\le \frac{k(k+1)}2=T_k$. Then we write $n$ as $1+2+\ldots+(k-1)+n-T_{k-1}$. These are also the lengths of the columns.

For any $n,$ let $F_n$ denote a final configuration. Also, let $T_n$ denote the $n$-th triangular number. Firstly, for any pair $(x,y)$ with $x$ on the left, we will always have $x \ge y.$ The proof is easy. Note that $x$ can decrease if and only if it gives one pebble to $y.$ Hence if $x<y,$ then we must have had the pair $(x+1,y-1).$ But here, $(x+1)-(y-1)=x-y+2<2,$ a contradiction. Key observation: $F_n$ has exactly one pair of consecutive elements equal except when $n$ is triangular, in which case there is no equal pair. Proof: Firstly, we show we cannot have the consecutive triple $(x,x,x).$ As argued above, the triple $(a,b)$ can only be obtained from $(a+1, b-1).$ Note that all three cannot turn equal in one move if they are all distinct. Hence either the first two or the last two must be equal beforehand. But then we get a contradiction in both the cases by the line above. If $(x, x, \cdots y, y)$ occurs, with $(x, x), (y, y)$ being the closest (closest by the number of elements in between). Then we must have that all the elements between $(x, x), (y, y)$ are distinct with a distance $=1.$ So the terms that occur are $(x, x, x-1,x-2 \cdots y+1, y, y).$ Again, $(a, b)$ can only be obtained from $(a+1, b-1)$ so we can backtrack and find that a consecutive equal triple must exist between $(x,x), (y,y)$ some moves before. But this case has already been ruled out. $\square$ Let $T_k \le n < T_{k+1}.$ We will show $k \le |F_n|<k+2,$ and $k=|F_n|$ if and only if $n=T_k.$ Assume $|F_n| \ge k+2,$ then $n=S(F_n) \ge 1+1+2+\cdots+k+1=T_{k+1}+1>n,$ a contradiction. Similarly, if $|F_n| \le k,$ then $n=S(F_n) \le 1+2+\cdots+k-2+k-1+k=T_{k} \le n,$ which is only possible if $n=T_k.$ By these two observations, we find that no two elements of $F_n$ are at a distance $\ge 2,$ as well as at most one pair is at a distance $0.$ So the last element must be $1,$ and we know that the elements of $F_n$ are in decreasing order, hence the elements are fixed, i.e. from $k$ to $1$ in the same order. Also, we know the sum, so we can determine which element repeats twice. So $F$ is unqiue and has the form: If $n=T_k:$ $F_n=(k, k-1, \cdots 1).$ If $n=T_{k}+l, l>0,$ then for any $F_n=(k,k-1, \cdots,l+1,l , l, l-1 \cdots, 1).$

With Aatman Supkar, Alan Chen, Alexandru Girban, Anushka Aggarwal, Daniel Sheremeta, Derek Liu, Dhrubajyoti Ghosh, Eric Shen, Gene Yang, Jeff Lin, Paul Hamrick, Raymond Feng, Robin Son, Sean Li: First, note that the process does eventually terminate (the configuration, when viewed as a tuple, decreases lexicographically). So we only have to show there is at most one possible final configuration. The proof proceeds in three claims about showing what statements must hold at any step. Claim: The sizes of piles (from left to right) are non-increasing. Proof. Obvious. $\blacksquare$ Claim: It is impossible to achieve $(\dots,a,a,a,\dots)$ for any positive integer $a$. Proof. Clear by looking one step immediately before such a configuration is achieved. $\blacksquare$ Claim: It is impossible to achieve $(\dots,a,a,a-1,a-2,\dots,b+1,b,b,\dots)$ for any integers $a > b > 0$. Proof. Again, look one step immediately before such a configuration is achieved, and proceed by induction on $a-b$. $\blacksquare$ Finally, note that in a final configuration, any two adjacent piles differ by at most $1$. For $2001$ pebbles, one may check that \[ T = (62,61,\dots,49,48,48,47,46,\dots,2,1) \]is the unique configuration with $2001$ pebbles satisfying all four of the conditions. In the general case, since there is only one decomposition of any integer $n$ in the form \[ n = (1+2+\dots+k)+\ell \qquad \text{where} \; 1 \le \ell \le k \]this gives the unique possible final configuration. Remark: The second claim is really better interpreted as a special case of the third, when $a=b$. Remark: For concreteness, the final configurations for $1 \le n \le 10$ are shown below. \begin{align*} 1 &= \mathbf{\color{red} 1} \\ 2 &= 1+\mathbf{\color{red} 1} \\ 3 &= \mathbf{\color{red}2}+1 \\ 4 &= 2+1+\mathbf{\color{red}1} \\ 5 &= 2+\mathbf{\color{red}2}+1 \\ 6 &= \mathbf{\color{red}3}+2+1 \\ 7 &= 3+2+1+\mathbf{\color{red}1} \\ 8 &= 3+2+\mathbf{\color{red}2}+1 \\ 9 &= 3+\mathbf{\color{red}3}+2+1 \\ 10 &= \mathbf{\color{red}4}+3+1+1. \end{align*}

Number the columns $1, \dots, k$ with $C_1, \dots C_k >0$ stones in them (we let $k$ and $C_1, \dots, C_k$ be dynamic as the procedure unfolds). Note that the given precondition for a move ensures that we have $C_1 \ge C_2 \ge \dots \ge C_k$ at all times. We write $i \to i+1$ to indicate moving a stone from column $i$ to column $i+1$. Lemma: Suppose $C_i = C_{i+1}$ at some point in time. Then the most recent move which affected $(C_i, C_{i+1})$ was $i \to i+1$. Proof: Use the fact that $C_1 \ge \dots \ge C_k$ at all times. $\Box$ Corollary: We cannot have $C_i = C_{i+1} = C_{i+2}$ at any point in time. Proof: Assume the contrary and consider the most recent move that affected $C_{i+1}$. By the lemma we have a contradiction. $\Box$ We say the configuration of stones is trianglish if it has the following characterization: $C_k=1$, and $C_{i+1}= C_i - 1$ for all but at most one pair of bad adjacent columns, which instead satisfy $C_i = C_{i+1}$. We say a configuration is semi-trianglish if it is trianglish in all regards, except it has at least two bad pairs of columns (keep in mind that the corollary forbids three consecutive columns with the same number of stones, so the bad pairs of adjacent columns all have different numbers of stones). [asy][asy] size(6 cm); void token(pair P) { fill(circle(P, 0.2), black); } void col(int x, int height){ for (int j=0; j<height; ++j) {token((x, j));} } col(1, 4); col(2, 3); col(3, 3); col(4, 2); col(5, 1); label("Trianglish", (3, -1.5), fontsize(10pt)); col(8, 5); col(9, 4); col(10, 4); col(11, 3); col(12, 2); col(13, 2); col(14, 1); label("Semi-trianglish", (11, -1.5), fontsize(10pt)); [/asy][/asy]Check with some easy computations that there is a unique trianglish configuration on $n$ stones. We claim that the final configuration of our process is the trianglish one. Lemma 2: At any point in time and any $m \le k$, the configuration of stones formed by the rightmost $m$ columns is not semi-trianglish. Proof: In any semi-trianglish configuration, let $(i, i+1)$ and $(j, j+1)$ be the rightmost two bad pairs of columns, where $i<j$. We will induct on $j-i$. For the base case, suppose we arrive at semi-trianglish configuration $\mathcal{B}$ with $j-i=2$. By Lemma 1, the most recent move acting on $(i, i+1)$ was $i \to i+1$; let us examine the configuration $\mathcal{A}$ just before that move. Since $i\to i+1$ is the only move to act on column $i+1$ between $\mathcal{A}$ and $\mathcal{B}$, the moves to the left of column $i+1$ do not "interfere" with the moves to the right of column $i+1$ (e.g. all of the stones to the right of column $i+1$ in $\mathcal{B}$ must have already been to the right of column $i+1$ in $\mathcal{A}$). Consider an alternate process beginning at $\mathcal{A}$ in which we first skip the move $i \to i+1$ and instead perform all moves which act on columns to the right of column $i+1$, until that rightmost section matches its appearance in $\mathcal{B}$: trianglish with a bad pair $(j, j+1)$ just to the right of $i+1$. [asy][asy] size(4cm); void token(pair P) { fill(circle(P, 0.2), black); } void col(int x, int height){ for (int j=0; j<height; ++j) {token((x, j));} } col(0, 5); col(1, 3); col(2, 3); col(3, 3); col(4, 2); col(5, 1); draw((1.5, -0.5)--(1.5, 5), dotted); label("$i$", (0,-1), fontsize(8pt)); label("$j$", (2,-1), fontsize(8pt)); label("The altered procedure produces a contradiction.", (3, -2), fontsize(10pt)); [/asy][/asy]Since the original procedure achieves this without interference from the left, our altered procedure is perfectly valid; however, it contradicts the corollary, since we find a moment in time when consecutive columns satisfy $C_{i+1} = C_j = C_{j+1}$. This establishes the base case. The inductive step proceeds identically: if we arrive at a semi-trianglish configuration $\mathcal{B}$ with $j-i > 2$, we consider the configuration $\mathcal{A}$ just before the move $i \to i+1$, and then we (validly) alter the sequence of moves to skip $i \to i+1$ and act so that the columns to the right of $i+1$ match their appearance in $\mathcal{B}$. [asy][asy] size(4cm); void token(pair P) { fill(circle(P, 0.2), black); } void col(int x, int height){ for (int j=0; j<height; ++j) {token((x, j));} } col(0, 6); col(1, 4); col(2, 4); col(3, 3); col(4, 2); col(5, 2); col(6, 1); draw((1.5, -0.5)--(1.5, 5), dotted); label("$i$", (0,-1), fontsize(8pt)); label("$j$", (4,-1), fontsize(8pt)); label("The altered procedure produces a smaller semi-trianglish configuration.", (3, -2), fontsize(10pt)); [/asy][/asy]This yields a procedure and a point in time when the rightmost columns, starting at $i+1$, form a semi-trianglish configuration with smaller $j-i$. This is impossible, so the induction is complete. $\Box$. To finish, consider a stable, final configuration. No more moves are possible, so number of stones in each pair of adjacent columns differs by at most $1$. Lemma 2 implies that there is at most one pair of bad columns with $C_i = C_{i+1}$, i.e. the configuration is trianglish, and we are done.

Interestingly, no one posted a solution along these lines. Solution by p_square: Denote by $n_i$ the number of pebbles in the $i$th column from the left. Make a graph with $n$ vertices $v_i$, where for each suitable $i$, the vertex $v_i$ has $n_{i+1} - n_{i}$ chips. Chip fire!

Very hard to explain. Label the columns $1,2,\dots$ from left to right and let $a_i$ denote the number of pebbles in column $i$ at any given time. Rephrase the problem as follows. We are given several columns containing a total of $n$ pebbles. An $\textit{operation}$ consists of moving a pebble from column $i$ to column $i-1,$ where column $i$ contains at most as many pebbles as column $i-1.$ Given that it is possible to apply some series of operations to reach the configuration with all pebbles in column $1,$ find all possible maximal initial configurations. Say a column $i$ is "friendly" if $a_{i-1}=a_i\ne 0.$ $\textbf{Claim: }$ Initially, we have $a_{i-1}-a_{i}\in\{0,1\}$ for all $i.$ $\textbf{Proof: }$ If $a_{i-1}-a_i<0$ for some $i$ initially, then column $i$ will always contain more pebbles than column $i+1,$ so the final configuration cannot be the one with all pebbles in column $1.$ On the other hand, if $a_{i-1}-a_{i}\ge 2$ for some $i$ initially, then there is a configuration that could have occurred before the initial configuration, contradicting its maximality. $\blacksquare$ $\textbf{Corollary: }$ At $\textit{any}$ point in time, the number of pebbles is non-increasing from left to right. $\textbf{Claim: }$ The initial configuration contains at most one friendly column. $\textbf{Proof: }$ We will show the more general statement that there are no friendly columns $i$ and $i+d,$ for some positive integer $d,$ at $\textit{any}$ point in time. To prove this, we will induct on the minimum value of $d.$ $\textit{Base Case: }$ Assume, for the sake of contradiction, that there is a point in time when $a_{k-1}=a_{k}=a_{k+1}\ne 0$ for some $k.$ Since the final configuration contains no such columns, at least one operation affecting columns $k-1,k,$ or $k+2$ must have been performed. But it is easy to see that performing any such operation does not keep the number of pebbles non-increasing from left to right, so we are done. $\textit{Inductive Step: }$ Assume the claim is true for $n=1,2,\dots,m-1.$ Suppose, for the sake of contradiction, that $a_{k}=a_{k-1}\ne 0$ and $a_{k+m}=a_{k+m-1}\ne 0$ for some $k$ at some point in time. Then, by our first claim, we must have $$a_{k-1}=a_{k}=a_{k+1}+1=a_{k+2}+2=\dots=a_{k+m-1}+m-1=a_{k+m}+m-1.$$Note that the final configuration does not contain pebbles in this pattern, so we must have performed at least one move affecting columns $k-1,k,\dots,k+m.$ But it is easy to see that the first operation we perform that affects columns $k-1,k,\dots,k+m$ must result in a configuration with two friendly columns at a smaller distance, which is impossible by the inductive hypothesis. $\blacksquare$ There is only once initial configuration satisfying the conditions above, so we are done.

Remark: Bulgarian Solitaire is very similar. Move everything to the positive lattice points of the coordinate plane. Initially, let all $n$ pebbles are on the points $(1, 1) \to (1, n)$. Also, note that it is clear the column sizes remain nonincreasing from left to right. Now consider the following: Claim: The sum of all $x$ and $y$ coordinates is nonincreasing. In fact, it is unchanged if the move consists of moving a pebble between two columns with size diffence exactly $2$, and is strictly decreasing otherwise. Proof: Assume a move is done on columns $i$ and $i+1$ which go from $(i, 1) \to (i, k + \ell)$ and $(i+1, 1) \to (i+1, k)$, respectively, where $\ell \geq 2$. Then, the quantity changes by\[\delta = ((i + 1) + (k + 1)) - ((i) + (k + \ell)) = 2 - \ell\]which is indeed equal to $0$ if $\ell = 2$ and $< 0$ otherwise. Note that we can keep making moves until the difference in size between any adjacent stacks is $\in \{0, 1\}$ by definition. At this point, we will have $n$ points oriented in the positive coordinate lattice for which the quantity\[\sum_{i : 1\to n} (x_i + y_i)\]for all $n$ pebbles is minimized. This is true because if we suppose not, and that if the quantity is not minimized, then there must be two columns with difference $\ell > 2$ and hence we can make another move and this is not the end state. If we write $n = (1 + 2 + \ldots + m) + m'$ where $m' \in [0, m - 1]$, then a graphical interpretation tells us that the sum is minimized if pebbles cover all points $x + y \leq m + 1$ that have positive integer coordinates and the remaining $m'$ are sprinkled along $x + y = m + 2$. However, they must be consecutively placed from the bottom up, so in fact we will have piles from left to right of sizes\[\{m, \ldots , m', m', \ldots, 1\}\]which will always be our end state.

There's a general strategy which applies to these sorts of problems. Replace everywhere the height of the \(i^{\text{th}}\) column with the height of the \(\left(i+1\right)^{\text{st}}\) column subtracted from it. Definition(s) 0 [Generic] : Define a state to be an element \(\xi\) of the \(\mathbb{Z}\)-module \(\mathcal{S}:=\prod_{i\colon\omega}\mathbb{Z}\), a finite state to be a \(\xi\) such that \[\sum_{i\colon\omega}\left|\xi\left(i\right)\right|<\infty,\]and a real state to be a \(\xi\) such that \[\forall i\colon\omega,\ \xi\left(i\right)\geq 0.\]Equip \(\mathcal{S}\) with the left \(\mathcal{G}:=\bigoplus_{i\colon\omega}\mathbb{Z}\) action induced by the collection of maps \[\mathcal{G}\left(j\right)+\xi\left(i\right):=\begin{cases}\xi\left(i\right)-2\text{ if }i=j\\ \xi\left(i\right)+1\text{ if }i=j+1\\ \xi\left(i\right)\text{ otherwise }\end{cases}.\]Say that a state \(\xi\) is terminal iff it is real and there exists no \(j\colon\omega\) such that \(\mathcal{G}\left(j\right)+\xi\) is real and quasiterminal iff it is the difference of two terminal states, and define a game \(J\) of length \(n\colon\omega\) with seed state \(\xi\) to consist of a map \(J\colon n\to\omega\) satisfying that for each \(n'\colon n\), \[\left(\sum_{k\colon n'}\mathcal{G}\left(J\left(k\right)\right)\right)+\xi\]is real. \(J\) is said to itself be terminal iff \[\left(\sum_{k\colon n}\mathcal{G}\left(J\left(k\right)\right)\right)+\xi\]is terminal. Proposition 1 [Generic] : State \(\xi\) is terminal iff \[\forall i\colon\omega,\ 0\leq \xi\left(i\right)< 2\]and quasiterminal iff \[\forall i\colon\omega,\ -2<\xi\left(i\right)< 2.\] Proof: Clear from the definitions. \(\Box\) Definition 2 [Specific]: Given a finite state \(\xi\), define the zeroth moment of \(\xi\) to be \[m\left(0,\xi\right):=\sum_{i\colon\omega}\xi\left(i\right).\] Proposition 3 [Specific] : For any finite state \(\xi\) and \(j\colon\omega\), \[m\left(0,\mathcal{G}\left(j\right)+\xi\right)=m\left(0,\xi\right)-1.\] Proof: Immediate from the definitions. \(\Box\) Proposition 4 [Specific] : For any real finite state \(\xi\), \[m\left(0,\xi\right)\geq 0.\] Proof: Immediate from the definitions. \(\Box\) Proposition 5 [Generic] : For every finite state \(\xi\), there exists a unique minimal \(\ell\left(\xi\right)\colon\omega\) such that every game with seed \(\xi\) is of length less than \(\ell\left(\xi\right)\). (And in particular, \(\ell\left(\xi\right)>0\) if and only if \(\xi\) is real.) Proof: Immediate from the definitions, Proposition 3, and Proposition 4. \(\Box\) Proposition 6 [Generic] : The only element \(g\) of \(\mathcal{G}\) such that \(g+0\) is quasiterminal is \(0\). Proof: Clear from the definitions and Proposition 1. \(\Box\) Proposition 7 [Generic] : Given real finite state \(\xi\) and terminal games \(J_{0}\) and \(J_{1}\) of lengths \(n_{0}\) and \(n_{1}\) respectively on \(\xi\), \[\left(\sum_{k\colon n_{0}}\mathcal{G}\left(J_{0}\left(k\right)\right)\right)+\xi=\left(\sum_{k\colon n_{1}}\mathcal{G}\left(J_{1}\left(k\right)\right)\right)+\xi.\] Proof: Apply Proposition 6 to \[g=\sum_{k\colon n_{0}}\mathcal{G}\left(J_{0}\left(k\right)\right)-\sum_{k\colon n_{1}}\mathcal{G}\left(J_{1}\left(k\right)\right).\ \Box\] Porting through the evident analogies, we win. \(\blacksquare\)

jj_ca888 wrote:

This is incorrect. Here is a hopefully correct solution. Clearly, from left to right, the size of the piles must be non-increasing, else we would have had to make a move on two adjacent piles with size difference $< 2$, clearly not possible. Since this process clearly ends (for example, consider the monovariant $\sum ia_i$ where piles are numbered $i: 1 \to \infty$ from the left and there are $a_i$ pebbles in pile $i$), we need to show that there is a unique final configuration (which exists). Furthermore, in the end state, the difference between adjacent piles must $\in \{0, 1\}$ or else it is still possible to make a move. First, notice that it is impossible to arrive at three piles $i-1, i, i+1$ with $a_{i-1} = a_i = a_{i+1}$, else if we rewind one step, the piles are not in nonincreasing order. Furthermore, I claim that it is impossible for two different adjacent pairs of piles $i, i+1$ and $j, j+1$ to have $a_i = a_{i+1}$ and $a_j = a_{j+1}$. Suppose we have some two $i < j$ with $i - j > 2$ minimal such that $a_i = a_{i+1}$ and $a_j = a_{j+1}$. Then, there are no two adjacent piles between $i$ and $j$ that have the same size. Hence, if we let $a_i = a_{i+1} = x$ and $a_j = a_{j+1} = x - (j - i - 1)$ then\[\{a_i, a_{i+1}, \ldots , a_{j+1}\} = \{x, x, x-1,\ldots , y+1, y, y\}\]where everything between $x - 1 \to y + 1$ is consecutive. Backtracking far enough, we see that there must have been some $i < x, y, z < j$ with $a_x = z_y = a_z$, clearly impossible. Hence, the final state must be piles decreasing by $1$ every adjacent pair with the exception of one adjacent pair. So, we must write\[n = (1 + \ldots m) + m'\]for some $m$ such that $m' \in [0, m - 1]$. Clealy each $n$ has a unique such representation, and since $m'$ is fixed, the pair of adjacent piles with the same size is also known, so the final configuration must be of the form\[\{m, m-1, \ldots , m', m', \ldots ,1\}\]from left to right, as desired. $\blacksquare$

Let $T_{k}$ be the kth triangular number, such that $T_{k}\leq n < T_{k+1}$. Then, I claim the final configuration is where we have columns of size $1$ to $k$ from right to left, then there is are two adjacent columns of size $n - T_{k}$ (unless $n = T_{k}$). Observe that if column $i$ was to the left of column $j$, the number of pebbles in column $i$ is at least the number of pebbles in column $j$. It's not hard to see that this process must terminate then (we can only make finite number of moves from the first column due to that constraint, finite from the second column, etc.). Let a pair of adjacent columns be "sparkle" pairs. I claim that we can not have two sparkle pairs in the final configuration (which proves that we only have one such configuration, as described above). Assume there existed two sparkle pairs, let them be in columns $i, i+1, j, j+1$ where $i + 1 < j$ such that no sparkle pair is between them. Then, since this is the final configuration, and there are no sparkle pairs between them, each column $i + 1 < k < j$ must have exactly one more pebble than the one to its right (or else we can make another move). Now, consider the last operation made on a column between $i-1$ and $j + 1$. It could not have been on $i-1$, since that means column $i+1$ would've had more pebbles than column $i$ before that operation. Similarly, it can not be on column $j + 1$. If it was on column $d$, then before that operation was made, column $d$ had the same number of pebbles as column $d-1$, so now we have two new sparkle pairs that are closer to each other. We can keep on considering the last moves until the two sparkle pairs pairs coincide - that is we have $3$ columns of the same size. Let these three columns be $k, k + 1, k+2$. If the last operation was on $k+1$ or $k+2$, before that operation it would've had more pebbles than it's left column. If it was on $k-1$ or $k$, then before that operation that column would've had less pebbles than it's right column. Both cases result in a contradiction, so we can conclude that it is impossible to have two pairs of sparkle columns. Thus, the configuration we described is the only possible final configuration.

Let $T=\tfrac{k(k+1)}{2}$ be the largest trianglular number less than or equal to $n$; we show the final configuration is the multiset $\{1,2, \dots , k, n-T \}$ arranged in nonincreasing order. Note that in the final configuration, adjacent columns differ by $0$ or $1$. Then to solve the problem it clearly suffices to prove the following two claims: Claim: We never have the sequence $(\dots, a, a, a, \dots)$ for $a>0$. Proof: Assume otherwise and consider the first time when this happens; there's no possible previous move. Clima: We never have the sequence $(\dots , a, a, a-1, a-2, \dots , b+1, b, b, \dots)$ for $a>b>0$. Proof: Assume otherwise and consider the first time when this happens; it's easy to see that one move ago, there must also have been a subsequence of this form, contradicting that this is the first time.

Very hard to writeup, but easy for a C7??

The unique configuration is $62,61,60\ldots 48,48,47,46\ldots 1$. We will prove the following two claims, which together imply the desired result. Claim 1: there can be no three consecutive stacks of the same height at any point. Proof: Suppose FTSOC that $(n,n,n)$ exists. must have had one of $(n-1,n,n),(n+1,n-1,n),(n,n+1,n-1),(n,n,n+1)$ beforehand, none of which are legal positions as trivially we can't have a lower stack behind a higher stack. Claim 2: there is one pair of two consecutive stacks of the same height in the final position. Proof: Call such pairs pearly. Let $i,i,i-1\ldots j+2,j+1,j,j$ contain two consecutive pearly pairs. Then, the only possible final move in this section would be $(j+1,j-1)\rightarrow (j,j)$, from which we can ignore $j-1$ and similarly backtrack repeatedly to arrive at that $(i,i,i)$ must have happened.

We will show by induction that if $n=\frac{a(a+1)}2+k$ with $k\leq a$, then the final configuration will have piles of sizes $a$, $a-1$, $a-2$, $\ldots$, $k+1$, $k$, $k$, $k-1$, $\ldots$, $2$, $1$, where the pile of size $a$ is at the location of the original pile. Base Case: $n=1$ Then, no moves are possible, so the final configuration will have one pile of size $1$. Inductive Step: Suppose that a total of $m=\frac{x(x+1)}2+y$ moves are done on the position of the original column. Then, we must have $m<n$ since it is impossible to remove a pebble from a pile with $1$ pebble. Any final configuration must be able to be reached from a pile with $n-m$ pebbles and a pile with $m$ pebbles. Therefore, by the inductive hypothesis, a final configuration must have pile sizes of the form $n-m$, $x$, $x-1$, $x-2$, $\ldots$, $y+1$, $y$, $y$, $y-1$, $\ldots$, $2$, $1$. However, the pile sizes must be nonincreasing and differ by at most $1$. Therefore, we must have $|n-m-x|\leq1$, so either $n-m=x$ or $n-m=x+1$. This means that $n=\frac{(x+1)(x+2)}2+y-1$ or $n=\frac{(x+1)(x+2)}2+y$. In the first case, either $k=y-1$ and $a=x+1$, which means that the piles have sizes $a-1$, $a-1$, $a-2$, $\ldots$, $k+2$, $k+1$, $k+1$, $k$, $\ldots$, $2$, $1$, or $y=0$, $x=a$, and $k=x$, which means that the piles have sizes $a$, $a$, $a-1$, $a-2$, $\ldots$, $2$, $1$. In the second case, we must have $a=x+1$ and $y=k$, so the piles have sizes $a$, $a-1$, $a-2$, $\ldots$, $k+1$, $k$, $k$, $k-1$, $\ldots$, $2$, $1$. Now, suppose that the final configuration has piles of sizes $a-1$, $a-1$, $a-2$, $\ldots$, $k+2$, $k+1$, $k+1$, $k$, $\ldots$, $2$, $1$. Every move, the difference between consecutive piles changes by increasing one difference by $1$, decreasing the next difference by $2$, and increasing the last difference by $1$. The differences in the final configuration are $-a+1$, $0$, $1$, $1$, $\ldots$, $1$, $0$, $1$, $\ldots$, $1$. If this is a possible configuration, then it is possible to add $2$ to a number and subtract $1$ from the adjacent numbers and eventually get the sequence $-n$, $n$, $0$, $0$, $\ldots$, $0$. The number $2$ must be added to the second $0$ at least once. After that, the number to the left becomes $0$, so then eventually the second and the third number must be $0$. However, this means that it is impossible to make the second number equal to $n$. Therefore, the final configuration must have piles of sizes $a$, $a-1$, $a-2$, $\ldots$, $k+1$, $k$, $k$, $k-1$, $\ldots$, $2$, $1$. Therefore, the final configuration must have piles of sizes $a$, $a-1$, $a-2$, $\ldots$, $k+1$, $k$, $k$, $k-1$, $\ldots$, $2$, $1$. If $n=2001$, then since $2001=\frac{62\cdot63}2+48$, this means that the piles must have sizes $62$, $61$, $60$, $\ldots$, $49$, $48$, $48$, $47$, $\ldots$, $2$, $1$.

Represent a configuration as a sequence. Obviously, the terms in the sequence are nonstrictly decreasing, and in any final configuration the difference between consecutive terms is either $0$ or $1$. We will prove the two following claims by reversing the process, starting from the finishing position and moving stones to the left so long as we preserve the nonstrictly decreasing nature of the terms. Claim 1: We cannot ever have three consecutive equal terms. Proof: Suppose the terms are $a,a,a$. We can't ever move onto the last $a$, nor move from any of the $a$'s, without forming a nondecreasing subsequence within these three terms. $\blacksquare$ Claim 1: We can't ever have terms $a,a,a-1,\ldots,b+1,b,b$ where $b>0$. Proof: Note that the degenerate case of $a=b$ is actually claim 1. Now, we use downwards induction: to go from such a configuration to the starting configuration (2001 pebbles in one column), we have to either move from one of the terms listed, since we cannot move to the last $b$ term. It's easy to check that the first time we move, the listed terms are preserved, and making any of the specified moves creates either $a,a,a-1,\ldots,c+1,c,c$ or $d,d,d-1,\ldots,b+1,b,b$ for $c>b$ or $a>d$. $\blacksquare$ These two claims, along with the nature of the final configuration, are enough to imply that the difference between any two consecutive terms is $1$, except for at most one pair of terms where the difference is $0$. Hence the final configuration looks something like $n,n-1,\ldots,m+1,m,m,m-1,\ldots,1$, where $0 \leq m \leq n$ (where $m=0$ corresponds to no pair of terms being equal), which has sum $\tfrac{n(n+1)}{2}+m, 0 \leq m \leq n$. Simple algebra yields that for $2001$, the corresponding unique configuration has $n=62,m=48$, yielding $62,61,\ldots,49,48,48,47,\ldots,1$. $\blacksquare$

Suppose two adjacent columns are $a$ and $b$, then if you can move a pebble from the $a$ column to the $b$ column then $a\ge b+2$, so after the move, $a-1\ge b+1$ which means that at each stage, the column heights are non-increasing. Let $a_1,a_2,\dots ,a_n$ be the column heights. Note that we can consider "unmoves" as moves that put a pebble from a column to the column directly to its left while keeping the sequence of column heights non-increasing. Note that having $a_i=a_{i+1}=a_{i+2}$ is impossible because any "unmove" will bring make the sequences $a_i$s non-increasing. Suppose we have $a_i=a_{i+1}>a_{i+2}>\dots a_{j}=a_{j+1}$. As before, any "unmove" will retain the fact that there are two instances of consecutive columns being same height, so we go back to the previous case. Thus, in the final configuration we must have either zero or one adjacent piles that are the same. There is a unique configuration from these conditions: find the least number $k$ such that $\tfrac{k(k+1)}{2}$ and then make the sequence $k,k-1,\dots ,1$ then add one to some of them, suitably.a

I'm fairly sure that this solution is valid (I may be wrong); just need someone to check that the main claim outlined is actually necessary for the proof. Replace $2001$ with $s$ and note that the process must terminate eventually. It is important to note that we can interchange any operations in the sequence as long as the resulting sequence remains valid. Claim: We can interchange operations in any such sequence so that the leftmost available operation is always the next to be moved. Proof: Consider the state of the pebbles at any point $t_1$ in time. Denote the position of the leftmost available operation by $p$. Evidently, without making any operations at position $p$, the process has to terminate eventually; therefore, at some point $t_2$, operation $p$ must be performed. If we consider the sequence of moves from $t_1$ to $t_2$ (ending with $p$), then if we simply move $p$ to the start of this sequence, we find that we have created an entirely valid new sequence. Now repeating this algorithm for all such points in time proves the claim. $\blacksquare$ With this claim, we can assume that one final configuration must exist. Now we can induct to show that if $s=1+2+\dots+n+r$ with $0\le r\le n$, the final positions of the piles must be \[n,n-1,\dots,r,r,r-1,\dots,1,\]with this definition being trivially altered on the edge cases. The procedure is simple: clearly the base case is trivial, and otherwise we can WLOG that one pebble stays at the first column, and note that after all other pebbles are moved to completion, the lone pebble travels down to the first value equal to $r$ and increments that value. The answer for $s=2001$ is then \[62,61,\dots,48,48,47,\dots,1\]and we are done. $\blacksquare$

We write the piles as a sequence of their lengths. Define a \textbf{reverse-operation} as reversing the operation. Claim 1: The sequence must be non-increasing. Proof This is obvious due to the rule that an operation can't occur if there aren't at least two more pebbles to the right of it. This proves that there will eventually be no operations possible. Now, we prove that the final configuration is unique. Claim 2 The final configuration can only differ by $0$ or $1$ for every consecutive pile. Proof Or it won't be final. Claim 3 The final configuration cannot have at least $3$ of the same numbers in a row. Proof For the sake of contradiction, we assume that it is possible to have at least $3$ of the same numbers in a row. Then, we must have \[\cdots, a, a, a, \cdots\]There's no possible way to achieve this because any reverse-operation we apply to this creates an increasing sequence, contradiction. Claim 4 The final configuration cannot have more than $1$ pair of consecutive equal integers. For example, this configuration is impossible \[\cdots, n+k, n+k, n+k-1, n+k-2, \cdots, n+1, n, n, \cdots\]Proof For the sake of contradiction, we assume that it is possible. We wish to perform reverse-operations until the configuration becomes one pile. We must perform a reverse-operation on the pairs, but eventually they will become next to each other, like so \[\cdots, n+k+1, n+k, n+k, n+k-1, n+k-1, n+k-2, \cdots \]We can't perform any more reverse operations without creating a row of $3$ or an increasing sequence, contradiction. Note that these claims create a unique final sequence. To find this unique configuration, let $k = \lfloor\frac{-1+\sqrt{1+8n}}{2}\rfloor$. $k$ is the greatest integer such that $n> \frac{(k)(k+1)}{2}$. Then, we form the sequence, $k, k-1, k-2, \cdots, 2, 1$ and add on another $n-\frac{(k)(k+1)}{2}$ to the sequence. For $n = 2001$, we have. \[\boxed{62, 61, \cdots, 49, 48, 48, 47, \cdots, 1}\]

First, we will show that the process must terminate as long as its initial position is finite. We do this by strong induction. The base case is trivial. Now for the inductive step, suppose we have $n$ pebbles. Notice that there must be at least one pebble that never leaves the first pile, since if the first pile reaches a height of $1$ then its pebble cannot be moved. Now consider the configuration after all pebbles that leave the first pile have left. There must be at most $n-1$ pebbles in the piles starting from the second pile, so starting from this point, the process terminates. Therefore the whole process terminates, completing the induction. Now, let the difference between the heights of pile $i$ and pile $i+1$ be $a_i.$ Notice that for any $i,$ we have that pile $i+1$ cannot be taller than pile $i.$ Any operation is now equivalent to subtracting $2$ to $a_i$ and adding $1$ to $a_{i-1}$ and $a_{i+1}$ if they exist. In our initial position, we have $a_1=n$ and $a_i=0$ for $i>1.$ Clearly in our final position, we must have $a_i \in \{0,1\}$ for all $i.$ We will show that there does not exist $i,j$ with $i<j$ such that in our final position we have $a_i=a_j=0$ and $a_{j+k}=1$ for some $k \ge 1.$ Suppose we do. We may assume without loss of generality that there is no $k$ with $i<k<j$ and $a_k=0.$ Now consider the last step that changed an $a_k$ with $i \le k \le j.$ If this changed $a_i$ then we know that it was an operation on pile $i$ since operating on pile $i+1$ or $i-1$ increases $a_i.$ Thus, we know that prior to this operation, we had $a_{i+1}=0,$ since in the final step we have $a_{i+1}=1.$ Similarly, we find that if the last step changed $a_j$ we would have had $a_{j-1}=0$ prior to it. Finally, notice that if this final step operated on some pile $k$ with $i+1<k<j-1$ then we would have had $a_{k-1}=a_{k+1}=0$ prior. Notice that each of these steps decreases the distance between a pair of nearest zeros, since $j-(i+1)=(j-1)-i<j-i$ and $(k-1)-i<j-i.$ Additionally, we can notice that the $a_x$ between each of these pairs are all still $1,$ and we can also notice that if at any point during this working backwards we reach a pair $x,y$ with $x<y$ and $a_x,a_y$ a pair of nearest zeros, then we have $a_{y+1}$ is nonzero. Therefore, working backwards from here, we eventually find a $k$ such that $a_k=a_{k+1}=0,$ and $a_{k+2} \ne 0.$ This final observation must mean that pile $k+1$ has been operated before, and we clearly see that this implies that pile $k$ has also been operated before. However, consider the first operation changing one of either $a_k$ or $a_{k+1}.$ This cannot be an operation on piles $k-1$ or $k+1$ since this would have had to start with $a_k$ being negative. However, this also cannot be an operation on piles $k$ or $k+2,$ since these would have had to start with $a_{k+1}$ being negative. However, these are the only four piles that can affect $a_k$ or $a_{k+1},$ so this is a contradiction, and accordingly we find that in the final state such a pair $i,j$ does not exist. Next, we easily see that we have $n=a_1+2a_2+3a_3+\dots+ia_i$ so let $a_k$ be the index that is zero in the final state with $a_{k+1}=1$ if it exists. Then we have $n+k=\frac{i(i+1)}{2},$ with $1 \le k < i.$ From here we can easily see that given any positive integer $n$ there is a unique choice of $k$ and $i$ unless $n$ is a triangular number, in which case we find $a_k$ does not exist and $\frac{i(i+1)}{2}=n.$ Therefore, we can define $f(n)$ as the smallest triangular number greater than or equal to $n,$ and we may let it be the $g(n)$th triangular number. Then, converting this back into pile heights we find that the $i$th pile will end up having height $g(n)-i$ if $i \le f(n)-n$ and $g(n)-i+1$ otherwise. In particular we find that for $n=2001$ we get the configuration $62,61,\dots,49,48,48,47,\dots,2,1.$

\textbf{Claim: } Let use have $m$ total pebbles. All final configurations are of the form \[(n, n-1, n-2, \ldots n-x+2, n-x+1, n-x +1, n-x, \ldots 3, 2, 1)\]where $n$ is the smallest integer such that $\binom{n+1}{2} \geq m$ and $x = \binom{n+1}{2} - m$. Notice that if $x = $ then we never have two numbers the same. Our base case is obvious. Now for the inductive step. We now have that our pile must go to the piles \[(n+1, n-1, n-2, \ldots n-x+2, n-x+1, n-x +1, n-x, \ldots 3, 2, 1)\]Notice that we can (and must) operate an all piles until we get to the point where we have the two consecutive $n-x+1$. Thus we get \[n, n-1, n-2, \ldots n-x+3, n-x+2, n-x+2, n-x+1, \ldots 3, 2, 1\]and our induction is complete. $\blacksquare$

Can someone please verify this solution . This problem felt very very rigid in that sense. Let $m_i$ denote the move on the $i$th pile. Note that if after swapping $m_i$ and $m_{i+1}$ in the sequence of the moves, the final sequence of moves can be still executed fully, then swapping them does not change the final configuration after all the moves. This is kind of obvious. We use induction to show that the final configuration is unique. Base case for $1$ is clearly true. Now we assume the inductive hypothesis for $k$ stones and then prove for $k+1$ stones. If there is any move that uses the extra stone added to the first pile, we push the move forward in the sequence. If the move gets restricted by some other move, we push both of them forward and keep doing so until we cannot anymore. Now note that all the moves that are currently at the end of the sequences that we pushed forward are the moves related to that extra stones that we add. But then the set of moves preceding the ones we pushed forward are the ones that are used in the case with $k$ stones. So this is more like performing all the moves on the case with $k$ stones and then after we reach final configuration, then we add the extra stone into the first pile. After adding it, note that our set of moves is totally fixed which ensures that there is only one final configuration until we can stop. $\textbf{CLAIM: }$ If $n = \dfrac{t(t+1)}{2}$, then the configuration is like $\left( t, t-1, \ldots , 1, 0 \right)$. And for any $\dfrac{t(t+1)}{2} < n < \dfrac{(t+1)(t+2)}{2}$, then we get the configuration by adding $1$ to each of the $n - \dfrac{t(t+1)}{2}$ from the end. Proof: We first proceed by using induction on $t$. This is clearly true for $t=1$. So now we assume the base case for some $t=k$ and we then prove it for $t=k+1$. Thus from the inductive hypothesis, we know that for $n=\dfrac{(t+1)(t+2)}{2}-1$, our final configuration is somewhat like $(t, t, t-1, \ldots , 2,1)$. Now if we add $1$ to the first pile, then the final configuration just simply becomes $(t+1,t, \ldots , 1, 0)$. Now we use induction inside inside induction lmao. We now induct on $n$. We already proved the base case for $n = \dfrac{(k+1)(k+2)}{2}$. Now assume the hypothesis for some $n=\dfrac{(k+1)(k+2)}{2} + l$ where $0\le l\le k$. So for our base case, the sequence is something like $(t+1 , t, \ldots, l,l,l-1,\ldots, 1)$. Now adding one stone to the first pile, note that we keep passing the stone on until we reach the first $l$. Then that $l$ becomes $l+1$ and thus our induction is complete. Thus our claim is proved. Now note that $\dfrac{62\times 63}{2} < 2001 < \dfrac{63\times 64}{2}$. Now $2001 - \dfrac{62 \times 63}{2} = 48$. Note that the configuration for $n=\dfrac{62\times 63}{2}$ is just $(62,61,\ldots, 1,0)$. Now by our lemma, we get the configuration for $2001$ is $(62,61,\ldots, 48,48,47,\ldots, 1)$.

Nice problem! Let the number of pebbles in $i^{th}$ stack be $a_i$ Call a subsequence $(s_i,s_{i+1})$ weird if $s_i=s_{i+1}$. We claim that there are at most $2$ weird subsequences in the final configuration FTSOC assume that there exist two $k,l$ such that $(s_k,s_{k+1});(s_l,s_{l+1})$ are weird, then there must exist a first configuration $\mathbb{K}$ in which there are two wierd subsequences. Notice the move made before $\mathbb{K}$ must be played in $k^{th}$ or $m^{th}$ place both of which imply the configuration before it must also have $2$ weird subsequences, which contradicts the minimality of $\mathbb{K}$ Now this determines the final configuration, because for any non-weird subsequence $s_{i+1}=s_i-1$.

We can easily prove the following observations by induction on the number of moves that happened to reach a configuration(the inductive hypothesis should be all of these at the same time). \begin{itemize} \item If $a<b$, then $a$ $b$ is not a substring of the configuration. \item $a$ $a$ $a$ is not a substring of the configuration. \item For any $k\in\mathbb N$, $a+k$ $a+k$ $a+k-1$ $a+k-2$ $\dots$ $a+1$ $a$ $a$ is not a substring of the configuration. \end{itemize} Since the ending configuration also cannot have $a$ $b$ where $a\ge b+2$, the configuration must be just $k$ $k-1$ $k-2$ $\dots$ $1$ along with at most one repeat for some $k$. Finding such a configuration with a given sum is indeed unique. Take the largest triangular number that is at most $n$, then make the repeat as necessary. Now we will prove that this process indeed terminates. But since the numbers must be nonincreasing, the $n+1$-th position(1-indexed) will never have any pebbles, so only finitely many moves may be performed. $\blacksquare$

Let $n = 2001$ and let $k$ be a positive integer such that $\frac{(k+1)(k+2)}{2} > n \ge \frac{k(k+1)}{2}$ and let $s = n - \frac{k(k+1)}{2}$. Then we'll prove that we'll reach $(\dots, 0, 0, 0, k, k-1, \dots, s, s, s-1, \dots, 2, 1, 0, 0, 0, \dots)$ no matter how we operate. It's clear that we'll reach a final configuration. Let $A = (\dots, 0, 0, 0, a_m, a_{m-1}, \dots, a_1, 0, 0, 0, \dots)$ be the final configuration that we've reached. Then it's clear that $a_1 = 1$ and for all $1 \le i \le m-1$, $a_{i+1} \ge a_i$ and $a_i + 1 \ge a_{i+1}$. Claim 1: It is impossible to achieve a configuration $\dots, a, a, a, \dots$ for some $a \ge 1$. Proof. Assume for some moment we've reached a configuration $\dots, a, a, a, \dots$. Then looking one step immediately before such a configuration is achieved, we get a contradiction. $\blacksquare$ Claim 2: There is no such $a > b > 0$ such that $\dots, a, a, a-1, \dots, b + 1, b, b, \dots$ is achievable. Proof. Looking one step before such a configuration is achieved, we get a configuration $a, a, a-1, \dots, b+2, b+1, b+1, b-1$. Repeating this, we get a configuration that contradicts claim 1. $\blacksquare$ From above 2 claims, we can easily see that the final configuration is $(\dots, 0, 0, 0, k, k-1, \dots, s, s, s-1, \dots, 2, 1, 0, 0, 0, \dots)$. For $2001$, the final configuration is $(62,61,\dots,49,48,48,47,46,\dots,2,1)$. $\blacksquare$

Note that at every step of the process, the pebbles in each box are non-increasing, and at the end it only decreases in increments $\leq 1.$ Claim: There cannot be two pairs of equal numbers at the end. Proof: Going backwards, note that $n,n,n-1$ must have been $n+1, n-1,n-1$ and continuing this until we get to the other pair, which would then be something like $a+1, a-1, a.$ Therefore we can only repeat any number once. As $2001-63 \cdot 31=48,$ the end sequence are the number counting down consecutively from $62,$ where instead of one $48$ there is two next to eachother$.\blacksquare$

We claim that our unqiue final configuration is \[\boxed{(62, 61, \ldots, 49, 48, 48, 47, \ldots, 2, 1)}.\] We make the following observations about this final configuration: Notice the pebble columns weakly decrease in size going from left to right. It's clear through induction that our process does terminate at some point. In this final state, the size of each pair of consecutive columns differ by 0 or 1, and the rightmost column has size 1. Notice that we can never have consecutive columns of form \[(a,a,a), (a,a,a-1,a-1), (a-1,a-1,a,a),\]as we have a contradiction attempting to consider the previous move. Notice that we can't have multiple numbers with frequency greater than 1, as we can determine that working backwards will always result in one of the above configurations, which we know are impossible to reach. Thus our final configuration is a list of consecutive integers ending at 1 with at most one number repeated, which gives us the desired claim. $\blacksquare$