A game of stones

Question

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.

Answer 1

$\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}.$

Answer 2

Something very very similar to this is already known. If your moves are to replace a crowded stone at $n$ with two stones at $n+1$ and $n(n+1)$, then these moves preserve the value of $\sum_n s(n)/n$, and in an uncrowded configuration this sum is an Egyptian fraction (a sum of finitely many distinct unit fractions). The algorithm that repeatedly applies these moves (order doesn't matter) until everything is uncrowded is called the splitting method for Egyptian fractions. Its eventual termination was proven by

L. Beeckmans. The splitting algorithm for Egyptian fractions. J. Number Th. 43, 1993, pp. 173–­185.

There's also a description of the same method, with its termination attributed to Graham and Jewett, in

S. Wagon. Mathematica in Action. W.H. Freeman, 1991, pp. 271–277.

But I don't have the original Graham–Jewett reference at hand.

Answer 3

EDIT: The proof below has a gap, see the comments.

I will rephrase the observations below as some reductions of the problem instead.

• We we can in a finite number of steps make sure that the first $N$ nodes are empty. It therefore remains to solve the issue about overcrowded nodes.
• Let $n$ be a node, such that all nodes to the right of $n$ are not overcrowded. If we can prove that it is always possible to increase the length of the run with empty nodes to the right of $n$, without introducing any overcrowded nodes to the right of $n$, we are done. Why? Since then, we can consider the rightmost crowded node $n$, increase the empty run to a sufficient size, and then apply a move at site $n$ and thus be guaranteed to strictly decrease crowdedness.
• It suffices to be able solve the case with one crowded node (with two stones), and some non-crowded nodes to the right of this node.

Here is the incomplete proof

As pointed out, we can always pick the smallest occupied site, and repeatedly apply the move until this is empty. Hence, the second condition can easily be taken care of first, so we only need to worry about overcrowdness.

First we do induction over the number of crowded nodes.

Main assumption: Assume we can fix overcrowdedness for $\leq k$ overcrowded nodes (with multiplicity).

Consider the largest crowded node $n$. Create a large enough gap (see below) to the right of this node, such that we can apply one move on $n$, and be sure that this reduces the overcrowdedness.

Thus, it suffices to show the following lemma:

Lemma: For any node $n$ with no crowded nodes to its right, we can create an arbitrary large gap of unoccupied sites to the right of $n$, and such that no nodes to the right of $n$ are overcrowded.

It is clear that it suffices to show that we can increase the gap by 1. We now do induction over number of stones to the right of $n$. Assume we have done this for $j$ stones (one stone is trivial, just apply the move to this stone), and that there are $j$ stones to the right of $n$.

Consider the stone which is on the leftmost node $m$ to the right of $n$. There less then $j$ stones to the right of $m$, so by induction hypothesis, we can make a large stone-free gap to the right of $m$. After that, we can apply the move on $m$ without introducing new overcrowded sites and thus increasing the gap to the right of $n$ by one.

Answer 4

This does not answer the original question, but explores a more general version.

Let $\mathcal N = \{n_0,n_0+1,n_0+2.\ldots\}$ for some fixed $n_0 \in \mathbb Z$. Let $f \colon {\mathcal N} \to {\mathcal N}$ be a map such that $f(n) > n$ for all $n \in \mathcal N$. We consider the game with stones on $\mathcal N$, where a legal move replaces a stone at position $n$ with two stones at $n+1$ and $f(n)$. Let us say that $f$ is good if for any finite configuration of stones and any $N \in \mathcal N$ there is a sequence of legal moves that transforms it into one that is not overcrowded and does not occupy a position $n < N$. We say that $f$ is bad otherwise. The original question was wether $f(n) = n^2$ is good and was answered positively by Aaron Meyerowitz. The question I want to discuss here is

Question.
Where (in terms of growth behavior of $f$) is the "phase transition" between bad and good?

I am going to argue that this is at a growth behaviour like $f(n) \sim n^2/2$.

For this, I will combine the entropy approach mentioned in the OP's Remarks and the idea of the proof in Aaron's answer.

Lemma 1.
Assume that there exists a discrete measure $\mu$ on $\mathcal N$ such that
(i) $0 < \mu(\mathcal N) < \infty$ and
(ii) for all sufficiently large $n \in \mathcal N$, $\mu(\{n+1,f(n)\}) \ge \mu(\{n\})$.
Then $f$ is bad.

Proof. For a configuration $s$ we define $\mu(s) = \sum_{n \in \mathcal N} s(n)\mu(\{n\})$. Let $n' \in \mathcal N$ satisfy $\mu(\{n'\}) > 0$ and be large enough so that (ii) holds for all $n \ge n'$. Consider a configuration $s$ of $m$ stones at $n'$ where $\mu(s) = m \mu(\{n'\}) > \mu(\mathcal N)$. Then by (ii) any sequence of legal moves leads to a configuration $s'$ with $\mu(s') \ge \mu(s) > \mu(\mathcal N)$, whereas any non-overcrowded position $s''$ has $\mu(s'') \le \mu(\mathcal N)$. So in fact no position we can reach by legal moves from $s$ avoids overcrowding. $\Box$

Lemma 2.
Assume that there is a constant $C$ such that $f(n+1) + C \ge f(n) + n$ for all sufficiently large $n \in \mathcal N$.
Then $f$ is good.

Proof. Fix $q \in \mathcal N$ such that $q > C+2$ and the condition on $f$ holds for $n \ge q$. Let $s_0$ be the position consisting of one stone at $q$. We let $s_{m+1}$ be the position obtained from $s_m$ by applying the legal move to every stone in $s_m$. I claim that no $s_m$ is overcrowded. This is certainly true for $m = 0$. Assume the claim is false and let $m \ge 0$ be the smallest $m$ such that $s_{m+1}$ is overcrowded. Then there are $n_1, n_2 \in s_m$ such that $n_1+1 = f(n_2)$. There are two possibilities. Either $n_1 = q+m$; then $n_1$ is the smallest occupied place in $s_m$ and we have the contradiction $n_1+1 = f(n_2) > n_2 + 1 \ge n_1 + 1$ (we use $n_2 \ge q > C+1$ here). Or we obtain $n_1$ from $q$ by a sequence of steps $n \mapsto n+1$ and $n \mapsto f(n)$ containing at least one application of $f$. In this case, at least the last $f(n_2) - f(n_2-1) - 1 \ge n_2 - (2+C)$ steps must be $n \mapsto n+1$ (since there is no value of $f$ between $f(n_2-1)$ and $f(n_2)$). So $m \ge n_2 - (2+C)$. On the other hand, $n_2 \ge q + m$, so we get a contradiction again, since $q > C+2$.

This shows the defining property for good $f$ for single-stone positions at places $> C+2$. It has already been observed in this thread that this is sufficient to establish that $f$ is good. $\Box$

Theorem.
(1) If $\limsup_{n \to \infty} \dfrac{f(n)}{n^2} < \frac{1}{2}$, then $f$ is bad.
(2) If $\liminf_{n \to \infty} \bigl(f(n+1)-f(n)-n\bigr) > -\infty$, then $f$ is good. In particular, if $f(n) = n^2/2 + k n + O(1)$ for some $k \in \mathbb R$, then $f$ is good.

Proof. Part (2) follows immediately from Lemma 2. For part (1), fix $\alpha > 1$ such that $2^{-\alpha} > \beta = \limsup f(n)/n^2$ and consider a measure $\mu$ given by $\mu(\{n\}) = (n (\log n)^\alpha)^{-1}$ for $n \gg 0$. Then $\mu(\mathcal N)$ is finite. Also, $$ \mu(\{n\}) - \mu(\{n+1\}) \sim \frac{1}{n^2 (\log n)^\alpha} ,$$ which grows more slowly than $$ \mu(\{f(n)\}) \ge \frac{1}{\beta 2^\alpha n^2 (\log n)^\alpha}(1 + o(1)), $$ so the assumptions of Lemma 1 are satisfied. $\Box$

Corollary.
If $f$ is a polynomial, then $f + O(1)$ is good if and only if $\deg f \ge 3$ or $\deg f = 2$ and the leading coefficient of $f$ is $\ge 1/2$.