3
$\begingroup$

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 _ _ _ _ _ _
$\endgroup$
  • $\begingroup$ @HagenvonEitzen exactly as you said, you can move them as far as you want, as long as you don't jump over another stone, will add it to the post, thanks :) $\endgroup$ – The New Guy Nov 1 '15 at 20:55
  • 1
    $\begingroup$ A Game of Stones. :-$)$ $\endgroup$ – Lucian Nov 1 '15 at 21:11
  • $\begingroup$ It is good for a player if after his move, all stones (except for the ones that can never be moved anymore) can be divided into pairs where every stone is adjacent to their pairmate. For instance, if the came looks like _ _ S S _ S S S S _ _ after your move, you win by keeping it that way. $\endgroup$ – Arthur Nov 1 '15 at 21:13
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.