  We consider the problem of determining the minimum number of moves needed to
solve a certain one-dimensional peg puzzle. Let N be a positive integer. The
puzzle apparatus consists of a block with a single row of 2N+1 equally spaced
holes which, apart from the central hole, are occupied by an equal number N of
red and blue pegs. The object of the puzzle is to exchange the colors of the
pegs by a succession of allowable moves. Allowable moves are of two types: a
peg can be shifted from the hole it occupies into the empty hole adjacent to
it, or a peg can jump over an adjacent peg into the empty hole. We exhibit a
sequence of N^2+2N moves that solves the puzzle, and prove that no solution can
employ fewer moves.

Combinatorics