Peg-solitaire Torsten Sillke, BI, 1993-04-06 ============= Show the impossibility of the following two puzzles. o o o o o o o o o o o o o o o o o o o o . o o o o . o o o o o o o o o o o o o o o o o o o o o o (1,1,1,1) (1,1,1,3) (vector of length of arms of the cross) - How many pegs must remain in the first case? Some variants which are solvable. o o o o o o o o o o . o o o o o o o o o o . o o o o o o o o o o . o o . o o o o o . o o o o o o At x and y you can borrow a peg. o o o o o o o . o o x o o o o o y o o o the last problem makes sence, if you want to solve bigger problems: o o o o o o o o o o o o o o o o . o o o o o o o o o o o o o o o o here you solve the small problem (with borrowing) and the o o . . o o . . o o . x -> . . . x cleans the arms of the cross for an appropriate solution. this can be iterated. - make a set of solutions, s. t. each cross with arms (a,b,c,d) with a, b, c, d >= 1 without (1,1,1,1) and (1,1,1,3) can be solved. (which are impossible for a, b, c, d >= 0 ?) Ref: Beasley, The Ins and Outs of Peg Solitaire, (he only considers the (2,2,2,2) and (3,3,3,3) type.) Proofs: Use the given weighting factors (+ = +1, - = -1). - 0 - - 0 - - + 0 + - - + 0 + 0 + - 0 0 0 0 0 0 0 0 0 0 0 0 - + 0 + - - + 0 + 0 + - - 0 - - 0 - (1,1,1,1) (1,1,1,3) (vector of length of arms of the cross) Then you get the following values for the starting positions: Start(1,1,1,1) = -4 Start(1,1,1,3) = -2 The weight of a sequence of positions is non-increasing. As the wanted end-positions have weight zero, you can't reach them. Now calculate a lower bound for the number of pegs which must remain. This is (trivial) a LP-problem: minimise: n+ + n- + n0 with the constraints: n+ >= 0, // number of pegs with weight 1 n- >= 0, // number of pegs with weight -1 n0 >= 0, // number of pegs with weight 0 n+ - n- <= Start_Weight. This gives the following bounds: Bound(1,1,1,1) = 4 Bound(1,1,1,3) = 2 Both bounds can be reached. The Bounds are not sharp for the following pattern: o o o o o o o o o o o o o o o o o o o o o . o o o . o o o o o o o o o o o o o (1,1,1,0) (0,0,2,2) (vector of length of arms of the cross) 0 0 0 - 0 - 0 + 0 - + 0 + - 0 0 0 0 0 the weight for 0,0,2,2 gives nothing 0 0 0 0 0 0 + 0 + 0 - + 0 + - 0 0 0 0 0 (1,1,1,0) (0,0,2,2) (vector of length of arms of the cross) Bound(1,1,1,0) = 2 (but you can reach only 3.) Bound(0,0,2,2) = 1 (but you can reach only 2.) Impossible, although you can borrow at x: x x o o o o o o o o o o o o o o o o o o o o o o o o o o . o o o o . o o o o . o o o o o o o o o o o o o o o o o x x o o o x x (1,1++,1,0) (1,1,1,0++) (1,1,1,1++) + + - 0 - - 0 - 0 0 0 - + 0 + - - + 0 + - - + 0 + - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - + 0 + - - + 0 + - - + 0 + - - - 0 0 0 + + (1,1++,1,0) (1,1,1,0++) (1,1,1,1++) Start(1,1++,1,0) = 2, End(1,1++,1,0) = 2 (proofs nothing) Start(1,1,1,0++) = -4, End(1,1++,1,0) = -2 (impossible) Start(1,1,1,1++) = 0, End(1,1++,1,0) = 2 (impossible) Proofs needed: (0,0,2,2), (1,1++,1,0), a better bound for (1,1,1,0). There is no weighting-function which proofs the impossebility in the first two cases. The linear programming problem, described by Wiezorke, has the maximum zero. But this proofs nothing. References: - J. D. Beasley; The Ins and Outs of Peg Solitaire. Oxford Univ. Press, 1985. - Cristopher Moore; One-Dimensional Peg Solitaire, 2000 arXiv http://front.math.udavis.edu/math.CO/0006067 - David Singmaster; Sources in Recreational Mathematics, An Annotated Bibliography, 7th Pre. Ed., Oct. 1999 Part II, Sect. 5.R.1. PEG SOLITAIRE - http://www.cut-the-knot.com/proofs/pegsolitaire.html