In this post, I will analyse the single player game brainvita (also known as peg solitaire). The game is described by having a board with holes having the pattern:
Initially all holes except the central one are filled with pegs. The player may jump a peg horizontally or vertically over another peg into an empty hole. The jumped peg is then removed by the player. The objective is to finish the game with just one peg left.
The aim of this post is to show that there are (at most) 
ending board positions in brainvita. In other words, assuming the player wins, his last peg left on the board can be only among fixed board positions.
The proof uses abstract algebra. Suppose that the pegs correspond to coordinates in the plane in the natural fashion described below: The central peg is at 
, and all others have integer coordinates as well. For convenience adjacent pegs may be taken a unit distance apart. Some coordinates are described below:
Now consider all possible ways of placing pegs on the board. There are 
of them. Many of these ways are impossible to reach in a valid game. Regardless of this fact, let 
be the set of all possible ways and for a given 
, let 
denote the set of all the coordinates where there is a peg in 
. Now define a function ![f:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)}](http://s0.wp.com/latex.php?latex=f%3AW%5Cto+%5Cfrac%7B%5Cmathbb%7BZ%7D_2%5Bx%5D%7D%7B%28x%5E2%2Bx%2B1%29%7D&bg=ffffff&fg=333333&s=0 "f:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)}")
by 
where ![\frac{\mathbb{Z}_2[x]}{(x^2+x+1)}](http://s0.wp.com/latex.php?latex=%5Cfrac%7B%5Cmathbb%7BZ%7D_2%5Bx%5D%7D%7B%28x%5E2%2Bx%2B1%29%7D&bg=ffffff&fg=333333&s=0 "\frac{\mathbb{Z}_2[x]}{(x^2+x+1)}")
is the finite field on 
elements. (If there are no pegs on the board we define 
to be 
.)
The function has the property that for any given way of placing pegs on the board, if a legal move is performed to yield another way 
then 
. To see this, suppose that in the way there were pegs at 
and 
positions and the hole at the 
position was empty. A legal move may be performed by jumping the peg over the peg to yield a way where the holes at and are empty and there is a peg at . Clearly the only change between 
and 
occurs on account of these three coordinates and 
. But as 
in so 
following which . The same holds if instead of moving a peg to the right we had moved it above, below or to the left. Moreover all this is regardless of the fact whether the way can actually be reached by a valid sequence of moves in the game.
Now we define another function ![g:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)}](http://s0.wp.com/latex.php?latex=g%3AW%5Cto+%5Cfrac%7B%5Cmathbb%7BZ%7D_2%5Bx%5D%7D%7B%28x%5E2%2Bx%2B1%29%7D&bg=ffffff&fg=333333&s=0 "g:W\to \frac{\mathbb{Z}_2[x]}{(x^2+x+1)}")
by 
(the no pegs way means 
is ) and by a similar piece of reasoning conclude that also has the same property enjoyed by . It is also easy to observe that both and are onto functions and so 
has 
elements.
Next we partition the set as follows. Any corresponds with a pair 
and so with exactly one among the elements of . In this way all the elements of are partitioned in parts. Further each part has the curious property that for any in that part, any sequence of legal moves will never change the value of and so the resultant will also be in the same part. It is now obvious that among these parts one and only part consists of all the 
which can actually occur in a game of brainvita. All other correspond to ways which can never occur in a legal game.
What is the value of that this one special part corresponds to? The initial board (assuming it corresponds with 
) is set up so that 
. So any way that arises during the game also has 
. Assume now that the game has been successfully finished with a single peg at , and that this corresponds to the way 
. We therefore have 
. But by definition 
and 
. So we must have 
. Since the multiplicative group 
is cyclic of order 
so as a consequence of Lagrange’s theorem we must have 
. Similarly we have 
. Combining these facts together we have dividing both 
and 
. The only five coordinates which satisfy this condition are 
and . So the player has to end up at one among these positions. This completes the proof.
It should be noted that we have only found an upper bound on the number of positions the final peg can end up at. However by explicitly giving a sequence of moves for each of these coordinates it is possible to show that all these endings are indeed possible.
Like this:
Like Loading...
This analysis is far more complicated than necessary. The same result can be obtained more quickly with no reference to group theory, field theory, or Lagrange’s theorem! See Beasley’s book or the web site:
http://home.comcast.net/~gibell/pegsolitaire/index.html#pre