2004/11/12 by David M. Bradley, Hugh Thomas, Bradley, David M. +1
Mathematics · Psychology · #00A08 (Primary) #68Q17 #68R15 (Secondary) #97A20 #97A90 #Children's Physical and Motor Development #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:00A08 #msc:68Q17 #msc:68R15 #msc:97A20 #msc:97A90
paper · pdf · doi:10.48550/arxiv.math/0411275
Original: 7 pages, recreational mathematics. Replacement: 6 pages, 6 figures, conjectured lower bound proved, retitled
openalex publication_date 2004/11/12 · arxiv created 2005/04/01 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 N2+2N moves that solves the puzzle, and prove that no solution can employ fewer moves.