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
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.