A game with stones, sure win strategy?

Question

There are two players. They alternate taking turns to move a stone (only one stone per turn) of their choosing. Stones can be moved only left as far as you want, as long as you don't jump over another stone. At the beginning they are placed randomly in a line. The player without any valid moves left loses. Whats the winning strategy for N stones.. is there any?

I figured out winning strategy if there are only 2 stones.

example of a starting position (S = stone):

_ _ S _ _ S S _ _ S

end of the game looks like this:

S S S S _ _ _ _ _ _

Answer 1

This is equivalent to a variant of Nim. In this variant you have piles $P_1,\ldots,P_n$ for some $n$. A move consists in choosing a pile $P_k$ with $k>1$ and transferring any positive number of stones from $P_k$ to $P_{k-1}$, or removing any positive number of stones from $P_1$. The first person who has no valid move loses. Equivalently, the person who takes the last stone off the board wins.

I claim that this game is equivalent to ordinary Nim with piles $P_{2k-1}$ for $k=1,\ldots,\lceil n/2\rceil$, i.e., with the odd-numbered piles of the original variant game. Suppose that I leave my opponent with a position in which the nim sum of the sizes of the odd-numbered piles is zero. If he moves stones from pile $P_k$ to pile $P_{k-1}$, where $k$ is even, I move the same number from $P_{k-1}$ to $P_{k-2}$ (or off the board, if $k=2$), again presenting him with a position in which the nim sum of the sizes of the odd-numbered piles is zero. If he moves stones from pile $P_k$ to pile $P_{k-1}$, where $k$ is odd, the nim sum of the odd-numbered piles is no longer $0$. Thus, there is an odd-numbered pile $P_k$ from which I can remove stones to make the nim sum of the odd-numbered piles zero again, and I simply move those stones to $P_{k-1}$ (or off the board, if $k=1$). In short, no matter how he moves from such a position, I can present him with such a position on his next move.

In the traditional terminology, positions in which the nim sum of the sizes of the odd-numbered piles is zero are P-positions, and all other positions are N-positions. The winning strategy is to ignore the even-numbered piles and to make what would be the winning move in a game of ordinary Nim with just the odd-numbered piles.