Given a finite number of stones. We place every stone on an integer. Prove that, given different movements, we can only make finite number of moves

Question

Given a finite number of stones. We place every stone on an integer (a number $x$ where $x\in Z$) and maybe multiple stones on an integer.

On each move we can make one of the following movements:

1. Remove a stone from numbers $n-1$ and $n$ and place one stone in integer $n+1$.
2. Remove $2$ stones from $n$ and place them in integers $n+1$ and $n-2$.

Prove that we can only make finite number moves.

I attempted to do it as follows:

On each stone we give it the weight $x^n$ where $x^2-x-1=0$, hence $x=\frac{1+\sqrt{5}}{2}$.

Hence we have that $x^{n-1}(x^2-x-1)=0$ and $x^{n+1}+x^{n-2}-2x^n=x^{n-2}(x^3+1-2x^2)=x^{n-2}(x^2+x+1-2x^2)=x^{n-2}(x+1-x^2)=0$.

Which proves that the total weight of the stones is an invariant.

This is as far as I got. I do not know how to finish it off although I do believe that this question is logically solved like this. Could you please explain to me how to solve this question?

Answer 1

This proof is rather semantic, since my technical notation is rather poor, but it works nonetheless. I've switched move 2 around, 1 to the left, and 2 to the right. The symmetry of the line shouldn't make it any different:

Assume you can do it indefinitely. With $x$ stones, you cannot do the first move indefinitely due to the fact that you lose 2 stones and gain 1, meaning a net loss of 1. More importantly, the number of stones before and after move 2 does not change it. Hence, we can take the 'start' position of the stones to be the point at which we stop doing move 1, and continue doing move 2 (still on the assumption that doing it indefinitely is possible)

Now all that's left is to prove that no matter how you do move 2, you'll end up with no moves left (we don't need to consider if two stones are in a row since we've safely assumed that all of those moves are done). To do this we just have to prove that the number of spaces occupied is equal to the number of stones. We can show this by pointing out that in a finite time, the number of spaces occupied will grow.

Consider the stone in the highest position $c$. There's no guarantee we'll perform the second move on it, so let's consider the highest position $Y$ that will be a move, that initially has at least 1 stone on it. I.e consider a set $X$ of positions with a stone on them at the beginning (I refer to the highest position with the highest ordinality that will eventually make a move).

When that position makes its move, it will

A) Donate a stone either to an empty position ($+1$ or $0$ [if the position we chose loses all its stones] positions occupied in total)

B) Donate to a position that has already has a stone on it (that will never be activated thereafter).

This same argument can be applied on the side of less stones.

Now we just need to disprove BB (which implies that every move will continue within finite bounds), and AB and BA (which implies that the rest of the stones will move to the left or to the right or otherwise donating stones indefinitely to a position that will grow but never be activated). We also need to disprove that A can occur forever with a net gain of occupied positions of 0

BB:

Consider the highest activated stone, same thing we did earlier. When that makes it's move it will place a stone a further distance, thus disproving BB

AB, BA:

Same argument as BB, just take it to the B side.

AA (0):

Consider below to be what happens directly after moving stones on $c$ whereby c is no empty:

0000010??????

That (previously) empty position was not in set $X$. A stone can be added to it. Since we pointed out that moves cannot have bounds, inevitably we'll get:

0000002???????

Again, moves cannot have bounds; that 2 will be activated. Therefore:

0000010???????

A $-1$ is, inevitable.

Answer 2

Suppose that there is a counterexample, i.e. an infinite set of moves from some configuration with a finite number of stones, $S$ say. If $S=1$, then no moves are possible and so we can suppose that we have a counterexample with $S$ minimal.

If the sequence contained a move of Type 1 then, after that move, there would only be $S-1$ stones and, by minimality of $S$, there could only be a finite number of further moves. All moves are therefore of Type 2 and, as in the post, this means that the total weight $W$ is unchanged for $x=\frac{1+\sqrt{5}}{2}$. A stone on position $n$ contributes $x^n$ to $W$ and, in consequence, the integer values for any occupied position is bounded above by the log of $W$ to the base $x$.

Since we are dealing with integers, this upper bound, $m$ say, is attained. Now consider moves from a configuration with at least one stone at position $m$. No move of Type 2 from this configuration can involve stones on $m$ and so the remaining moves involve at most $S-1$ stones. By minimality of $S$ there can only be a finite number of further moves after all.