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

notovercrowded, 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 storm of surdssounds very intriguing. $\endgroup$ – Liviu Nicolaescu Nov 26 '14 at 14:53