Consider the following two-player pebble game. We have finitely
many stones on a finite linear track of squares. We take turns, and
the allowed moves are:


* move any one stone one square to the left, if that square is empty, or
* remove any one stone, or
* remove any two adjacent stones.


Whoever takes the last stone wins.


**Question.** What is the winning strategy? And which are the
winning positions?


The game will clearly end always in finitely many moves, and so by
the fundamental theorem of finite games, one of the players will
have a winning strategy. So of course, I know that there is a
computable winning strategy by computing with the game tree, and we have a computable algorithm to answer any instance of the question. What I am hoping for is that there will be a simple-to-describe winning strategy.


This is what I know so far:


**Theorem.** It is a winning move to give your opponent a position
with an even number of stones, such that the stones in each successive pair stand
at even distance apart.


By even-distance, I mean that there are an odd number of empty
squares between, so adjacent stones count as distance one, hence
odd. Also, I am only concerned with the even distance requirement *within* each successive pairs, not *between* the pairs. For example, it
is winning to give your opponent a position with stones at 



```
..O...OO.O....O.....O...........

```

We have distance 4 in the left-most pair, distance 2 in the next pair, distance 6 in the third pair, ignoring the distances in front and between the pairs.


**Proof.** I claim that if you give your opponent a position like
that, then he or she cannot give you back a position like that, and
furthermore, you can give a position like that back again. If your
opponent removes a stone, then you can remove the other one in that
pair. If your opponent moves the lead stone on a pair, then you can
move the trailing stone. If your opponent moves the trailing stone
on a pair, then either you can move it again, unless that pair is
now adjacent, in which case you can remove both. And if your
opponent removes two adjacent stones, then they must have been from
different pairs (since adjacent is not even distance), which would
cause the new spacing to be the former odd number plus another odd
number plus 2, so an even number of empty squares between, and so
you can move the trailing end stone up one square to make an odd
number of empty squares between and hence an even distance between
the new endpoints. Thus, you can maintain this even-distance
property, and your opponent cannot attain it; since the winning
move is moving to the empty position, which has all even distances,
you will win. $\Box$


What I wonder is whether there is a similarly easy to describe
strategy that solves the general game. 



What is the winning strategy in this pebble game?
The positions which are a win for the second player are those with:


* an even number of pebbles in odd-numbered squares, and
* an even number of pebbles in even-numbered squares.


Indeed, from a position in this set $P$, any move will be to a position not in that set, whereas from a position not in that set one can always make a move to a position in that set (if only the number of pebbles in the odd-numbered squares is odd, you can remove one, similarly for the even-numbered, and if both are odd, choose any pebble — that is not at the very leftmost square — and either more it to the left if that square is unoccupied or remove it along with the one to the left if it is).


So, systematically moving to a position in $P$ (as described in the parenthesis in the previous paragraph) provides a winning strategy provided one starts with a position not in $P$.


