How I arrived at this question is a rather long story having to do with the honors calculus class I am teaching. At this point it's sheer curiosity on my part. Here is the game.


$\newcommand{\bZ}{\mathbb{Z}}$


We start with a finite collection of stones placed at random somewhere on the set of nodes $\newcommand{\eN}{\mathscr{N}}$ $$\eN=\{2,3,4,\dotsc\}. $$ We can view a distribution of stones as a function $s:\eN\to\bZ\_{\geq 0} $ with finite support, $s(n)=$ the number of stones at $n$. Its *weight* is the nonnegative integer


$$|s|=\sum\_{n\in\eN} s(n). $$


We say that a distribution $s$ is *overcrowded* if $s(n)> 1$ for some $n\in\eN$. A node $n$ is called *occupied* (with respect to $s$) if there is at least one stone at $n$, $s(n)>0$. 


We are allowed the following moves: choose an occupied node $n$. Then you move one stone from location $n$ to location $n+1$ and add a new stone at location $n^2$. Note that such a move increases the weight by $1$.


Now comes the question.



> 
> Is it true that for any initial distribution of stones $s:\eN\to\bZ\_{\geq 0}$ and any positive integer $N$ there exists a finite sequence of allowable moves such that after these moves we obtain a new distribution of stones which (i) is **not** overcrowded, and (ii) no node $n<N$ is occupied. 
> 
> 
> 


Empirical evidence leads me to believe that the answer to this question is positive. However, I have failed to find a conclusive argument.I'm hoping someone in the MO community will have more luck.


**Remark 1.** (*Inspired by David Eppstein's answer.*) I want to show that if the function $n\mapsto n^2$ in the definition of an allowable move is replaced by something else the answer to the question can be negative. In other words, any proof for the positive answer, would have to take into account some features of the map $n\mapsto n^2$.


Here is the example. Fix an integer $k>1$ and define $f:\eN\to\eN$, $f(n)=n+k$. Now change the definition of an allowable move as follows.



> 
> Pick an occupied node $m$. Move a stone from location $m$ to $m+1$ and
>  add a stone at the node $f(m)$. We will denote by $T\_m$ this move.
> 
> 
> 


Let $s\_0:\eN\to\bZ\_{\geq 0}$ be the configuration consisting of a single stone located at $n=2$. *I claim that there exists $N>0$ such that $s\_0$ cannot be moved past $N$ without overcrowding.* 


The proof is based on a conservation law suggested by David Eppstein's answer. Consider the polynomial $P(x)=x^k+x-1$. Note that $P(0)<0$ and $P(1)>0$ so $P$ has at least one root in the interval $(0,1)$. Pick one such root $\rho$. We use $\rho$ to define the *energy* of a configuration $s:\eN\to\bZ\_{\geq 0}$ to be


$$ E(s):=\sum\_{n\in \eN} s(n)\rho^n. $$


If $m$ is an occupied location of a configuration $s:\eN\to\bZ\_{\geq 0}$, then


$$E(T\_m s)= E(s)-\rho^m+\rho^{m+1}+\rho^{m+k}=E(s)+\rho^mP(\rho)=E(s). $$


Thus allowable moves do not change the energy of a configuration.


Let $N$ be a positive integer such that


$$\rho^{N-2}<1-\rho. \tag{1} $$


Suppose now that using allowable move we can transform $s\_0$ to a configuration $s$ such that


$$ s(n)=0,\;\;\forall n<N,\;\;s(n)\in \{0,1\},\;\;\forall n\geq N. $$


Then


$$\rho^2= E(s\_0)=E(s)\leq \sum\_{n\geq N}\rho^n=\frac{\rho^N}{1-\rho}. $$


This last inequality violates the assumption (1), thus confirming my claim.


**Remark 2.** The example in the previous remark has the following obvious generalization. Suppose that $f:\eN\to\eN$ is a function such that $f(n)>n+1$, $\forall n \in \eN$ and there exists a probability measure $\pi$ on $\eN$ such that


$$ \pi\bigl(\; f(n)\;\bigr)+\pi(n+1)-\pi(n)\geq 0,\;\;\forall n\in\eN. \tag{2}$$


Using $f$ to define the allowable moves, one can show that there exists $N>0$ such that $s\_0$ cannot be moved past $N$ without overcrowding. The proof uses the *entropy*


$$E\_\pi(s)=\sum\_{n\in\eN}s(n)\pi(n). $$


Note that this entropy is precisely the expectation of $s$ with respect to the probability measure $\pi$, and it *does not decrease* as we apply allowable moves


$$E(s)\leq E(T\_m s), \;\;\forall s. $$


For $f(n)=n+k$ we can define


$$ \pi(n)=(1-\rho)\rho^{n-2}. $$


This remark raises the following natural question.



> 
> Find the functions $f:\eN\to \eN$ such that $f(n)>n+1$, $\forall n\in \eN$,
>  and there exists a probability measure $\pi$ on $\eN$ satisfying
>  (2). How fast can such a function grow as $n\to \infty$?
> 
> 
> 


**Remark 3.** (a) For $f(n)=n^2$ the condition (2) reads


$$ \pi(n^2)+\pi(n+1)\geq \pi(n). \tag{3} $$


One can show that a series $$\sum\_{n\geq 1}p(n) $$ with nonnegative terms satisfying (3) is divergent if not all the terms are trivial. (This was the rather tricky honors calculus problem that prompted the present question.) Hence, for the function $f(n)=n^2$, there do not exist probability measures satisfying (2), suggesting indirectly that the original question could have a positive answer.


(b) If $f(n)=n +1+ \lfloor \sqrt{n}\rfloor$, $\alpha>1$ is sufficiently close to $1$ and 


$$\pi(n)=\frac{C}{n^\alpha}, \;\;C\sum\_{n\geq 2}\frac{1}{n^\alpha}=1,$$


then the condition (2) is satisfied so moving without overcrowding is not possible if the allowable moves use the function $f(n)$.


**Remark 4.** Have a look at Michael Stoll's superb answer. 



A game of stones
$\newcommand{\bZ}{\mathbb{Z}}$
$\newcommand{\eN}{\mathscr{N}}$


Here is a proof which does not treat overcrowding as a special case. As noted in some comments, it is really enough to prove the desired result for the case of one stone. The actually proofs takes up less space than the statements and all the notation. I will


* restate the desired result as a theorem in an equivalent but slightly more detailed way to aid the proof.
* claim a result, which implies the theorem for the case of one stone
* prove the theorem
* Show that the proof of the claim provides a much stronger result.


I will find it convenient to think of $s$ as a multiset (although I'll use the stone language too). I'll think of a move as removing a stone and replacing it with two offspring. Most of the time I will be trying to prove that $s$ is actually a set.



> 
> 
> > 
> > **THEOREM:** For any initial distribution of stones $s:\eN\to\bZ\_{\geq 0}$ with $2 \le p =\max{s}$ and any positive integer $N$ there exists an integer $M=M(s,N)$ and a sequence of moves after which we obtain a new distribution of stones which (i) is a set (no two stones occupy the same location), (ii) has no node $n<N+p$ occupied and (iii) has no node $n>M$ occupied.
> > 
> > 
> > 
> 
> 
> 




---



> 
> 
> > 
> > **CLAIM**: Consider an initial configuration $s(0)=\{{q+1\}}$ consisting of a single stone at position $q+1 \ge 2$. Let $$s(1)=\{{q+2,(q+1)^2\}}$$ 
> >  $$s(2)=\{{q+3,(q+2)^2,(q+1)^2+1,(q+1)^4\}}$$ and in general $$s(k)=\{{x+1 \mid x \in s(k-1)\}} \cup \{{x^2 \mid x \in s(k-1)\}}.$$ So $s(k)$ is a multiset with $2^k$ elements, the smallest being $q+k+1$ and the largest $(q+1)^{2^k}.$ Then $s(k)$ is, in fact, a set.
> > 
> > 
> > 
> 
> 
> 


Assume that we already know the $s(j)$ to be sets for all $j \lt k.$ We wish to show that $s(k)$ has no repeated elements. A number $v \in s(k)$ which is not a square can only arise as $(v-1)+1$ for $v-1 \in s(k-1).$ A value $v \lt (q+1)^2$, square or not, can only be $v=q+k+1.$ It remains to consider the square values $u^2 \in s(k)$ with $u \ge (q+1)^2.$ If $u^2-1 \notin s(k-1)$ then we know $u \in s(k-1)$ and $u \ge q+k=\min(s(k-1)).$ We will now see that, independent of $q$, if $u^2-1 \in s(k-1)$ then $u \le\frac{k+1}{2}$ so $u \notin s(k-1).$ If $u^2-1 \in s(k-1)$ then also $u^2-2\in s(k-2)$ and so on until the previous square $u^2-2u-1 \in s(k-2u+1).$ But this means $0 \le k-2u+1$ so $ u \le \frac{k+1}{2}$


This establishes the theorem for a singleton set $s=\{{p\}}$ with $M(s,N) \le p^{2^{N+1}}.$ 




---


**PROOF OF THEOREM:** The proof is by induction on the number of stones present. The case of one stone is the claim above with $M = p^{2^{N+1}}$. If there is more than one stone, let $s'$ be the position obtained by lowering the number of stones on the final occupied position by $1$. Then use the claim to move a single stone from that position and keep moving the offspring until all resulting stones are moved past $M(s',N).$ Then, by hypothesis, we can redistribute the (offspring of) the stones of $s'$ without colliding with any of the offspring of the initial stone.


As a consequence, if $s$ has at least two stones and $p$ is the largest filled position of $s$, then $M(s,n) \le M(\{{p\}},M(s',N)) \le p^{2^{M(s',N)+1}}.$ The strong claim below would allow smaller, but still enormous, upper bounds.




---


Note that the configuration $\{{p,p^2-1\}}$ leads to an immediate collision if the move is applied to both members. I will show that for a larger, but slightly thinner, configuration no collisions occur even with repeated iterations. 



> 
> 
> > 
> > **STRONG CLAIM**: Consider, for $q+1 \ge 2,$ an initial configuration $s(0)=\{{q+1,q+2,\cdots , (q+1)^2-2\}}.$ For $k \gt 0$ let $$s(k)=\{{x+1 \mid x \in s(k-1)\}} \cup \{{x^2 \mid x \in s(k-1)\}}.$$ So $s(k)$ is a multiset with $2^k(q^2+q-1)$ elements, the smallest being $q+k+1$ and the largest $\left((q+1)^2-2\right)^{2^k}.$ Then $s(k)$ is, in fact, a set.
> > 
> > 
> > 
> 
> 
> 


It is clear that $s(0)$ and $s(1)$ are sets, Assume that $1 \lt k$ and we already know the $s(j)$ to be sets for all $j \lt k.$ We wish to show that $s(k)$ has no repeated elements. A number $v \in s(k)$ which is not a square can only arise as $(v-1)+1$ for $v-1 \in s(k-1).$ A value $v \le (q+1)^2$, square or not, can only have arisen from $v-k \in s(0)$ without any squaring. It remains to consider the square values $u^2 \in s(k)$ with $u \gt (q+1)^2.$ If $u^2-1 \notin s(k-1)$ then we know $u \in s(k-1)$ and $u \ge q+k = \min(s(k-1)).$ We will now see that, independent of $q$, if $u^2-1 \in s(k-1)$ then $u \le\frac{k+1}{2}$ so $u \notin s(k-1).$ If $u^2-1 \in s(k-1)$ then also $u^2-2\in s(k-2)$ and so on until the previous square $u^2-2u-1 \in s(k-2u+1).$ But this means $0 \le k-2u+1$ so $ u \le \frac{k+1}{2}.$


