# A game relevant to moving a stone.

There is a straight line of $$10000$$ cells connected together . It contains $$n$$ stones at coordinates $$p_i(1\le p_i\le 10000,i=\overline{1,n})$$.

A and B plays a game as follow:

• 2 players take turns shifting a stone to the left.
• When moving, the player can move the stone to the left freely as long as it does not leave this straight line and can't move overlap the other stone. Player who can't move any stone is a loser.

A is the first to go. Determining that A or B win.

For example:

• With $$n=3$$ and $$p_1=1,p_2=2,p_3=3$$. The result is B, because $$A$$ can't move any stone!.
• With $$n=8$$ and $$p_1=1,p_2=5,p_3=6,p_4=7,p_5=9,p_6=12,p_7=14,p_8=17$$. The result is $$A$$.

This is my try:

I think this problem is relevant to distance between 2 any points and consecutive postions of stones. I will consider a block of consecutive positions of stones is a stuck, and the player will not pick up any stone in this block, but I can't come to finall solution!!. And I think this porblem may be relevant to Nim's game!

It turns out that you are right, the game is related to Nim. I'll formulate an additional constraint that is missing from the original problem description but seems implied by the first example:

In all valid positions $$(p_1,p_2,\ldots,p_n)$$, we have $$p_i \neq p_j$$ for $$i\neq j$$.

I'll note that $$\sum_{i=1}^np_i$$ decreases with each move, so (since the $$p_i$$ are non-negative) the game can't go on forever!

I'll reformulate the problem a bit, in order to show that connection to Nim clearly. Let's define $$p_0=0$$ and for any position $$(p_1,p_2,\ldots,p_n)$$ let

$$r_i:=p_i-p_{i-1}-1, i=1,\ldots,n.$$

That means $$r_i$$ is how many cells the stone $$i$$ (I count from the left and start with $$1$$) can be moved at max before it reaches the next stone (or the left end of the line, that's why I defined $$p_0$$ as $$0$$ to make that work out).

For the 2 examples the $$r$$-vectors look like

$$\text{Example}_1: (0,0,0)$$ $$\text{Exampl2}_2: (0,3,0,0,1,2,1,2)$$

If we go from a position $$(p_1,\ldots,p_i,\ldots,p_n)$$ to position $$(p_1,\ldots,p'_i,\ldots,p_n)$$ by a valid move of stone $$i$$, we have $$p_{i-1} < p'_i < p_i$$ as the valid range for $$p'_i$$.

In terms of our $$r$$-vector that means $$0 \le r'_i < r_i$$ and $$r'_{i+1}=r_{i+1}+(r_i-r'_i)$$, because the space we 'loose' for stone $$i$$ in future movability we gain for stone $$i+1$$. If $$i=n$$, the the adjustement for $$r'_{i+1}$$ does not happen, as there is no index $$n+1$$ in the $$r$$-vector. That's because if we move the most-right stone (index $$n$$), there is no other stone after it to profit from more space.

Taken all of this together, we can describe the game using the $$r$$-vector:

From any position $$(r_1,r_2,\ldots,r_n)$$ we choose an index $$i, 1\le i\le n$$ and a value $$s, 0 < s \le r_i$$ and go to the position $$(r_1,\ldots,r_i-s,r_{i+1}+s,\ldots,r_n)$$,where the "$$+s$$" term does not occur if $$i=n$$.

Bascially, we are moving the stone $$i$$ $$s$$ steps to the left.

In this formulation, the game looks similar to Nim, but has the difference that we also increase the values $$r_{i+1}$$, unlike Nim, which has no increase.

Claim: After lots of trials, it became apparent to me that the game is equivalent to a game of Nim (https://en.wikipedia.org/wiki/Nim), with the pile sizes being ($$r_n, r_{n-2}, r_{n-4},\ldots$$), where the last entry is $$r_2$$ or $$r_1$$, depending on $$n$$ being even or odd.

The most surprising thing is probably that $$r_{n-1}, r_{n-3},\ldots$$ don't matter at all when deciding if a position is won or lost for the starting player. I'll use the term 'relevant index' for the indices $$n,n-2,n-4,\ldots$$ and the term 'irrelevant index' for the others.

How do we prove that claim? It's two steps. First we prove that any $$r$$-vector that corresponds to a winning position for the Nim game can be transformed by the active player with a valid move into an $$r$$-vector that corresponds to a loosing position for the Nim game. Then, the second part is showing that for any $$r$$-vector that corresponds to a loosing position for the Nim game, any legal move leads to a winning position for the Nim game.

First step: If we have an $$r$$-vector with a winning position in the corresponding Nim game $$(r_n,r_{n-2},\ldots)$$, we can (by definition of a winning position in the Nim game), choose an index $$i$$ and decrease the corresponding pile in the Nim game by $$s$$ to get a loosing position. Note that $$i$$ is a relevant index. We now do the same in our game, we reduce $$r_i$$ by $$s$$. That means we get the new $$r$$-vector

$$(r_1,\ldots,r_i-s,r_{i+1}+s,\ldots,r_n)$$

and since $$i+1$$ is an irrelevant index, the corresponding Nim-vector doesn't 'see' the increase at index $$i+1$$, so it is $$(r_n,r_{n-2},\ldots,r_i-s,r_{i-2},\ldots)$$, which is by constructuion a loosing position in the Nim game. That means we have created a position in our game that corresponds to a loosing position in the Nim game, as required.

Second step: We have an $$r$$-vector that corresponds to a loosing position for the Nim game. One property of the loosing positions in a Nim game is that if you fix all but one pile size, there is exactly one pile size for the remaining pile that creates loosing position. The player in our game can make 2 types of moves, the index $$i$$ of the decreased $$r_i$$ can be relevant or irrelevant.

If $$i$$ is relevant, we see just as in step one that the only changed value at a relevant index is at index $$i$$. That means the corresponding game of Nim has also only changed at that one index, which means that it is a winning position,as by the mentioned property above.

If $$i$$ is irrelevant, then decreasing $$r_i$$ has increased $$r_{i+1}$$. Note that index $${i+1}$$ always exists, because an irrelevant index $$i$$ can be at most $$n-1$$. That means that the only change in the corresponding Nim game happened at index $$i+1$$ (which actually exists). By the property above, this again means that the corresponding Nim game after the move is a winning Nim position.

This concludes the proof. From a winning position we can always choose a move that leads to a loosing position, and from a loosing position, all moves lead to a winning position. Since the game must end (see the very beginning), it must end in the only position that does not allow a move $$(0,0,,\ldots,0)$$, which is a loosing position.

I hope it was clear enough, I fear it is not, because showing such equivalences is often lots of details, but I was trying to provide the main idea of the transformation is good as I could.

• Summary, it means that: if $r_n\oplus r_{n-2}\oplus...=0$, B always win and if $r_n\oplus r_{n-2}\oplus...\ne 0$ A always win ? Commented May 7, 2019 at 17:21
• Yes, that's right. Commented May 7, 2019 at 17:24
• How do you think about this problem: It's a variant of Nim'game math.stackexchange.com/questions/3215596/…. I only know the heaps of first operation is: $p_1\oplus p_2\oplus p_3...$ and I can't find the final winning strategy for this problem!!! Commented May 8, 2019 at 1:07