## Cut The Knot!An interactive column using Java applets
by Alex Bogomolny | |

SlidersDon Greenwell |

April 1999

What if applet does not run? |

This paper focuses on a variation of an old puzzle, called the Fifteen puzzle, invented by Sam Loyd in the early 1870's. The puzzle above, contains 15 counters which can be moved using a vacant position in an attempt to reach this desired configuration. The original puzzle was constructed with the 14 and 15 counters permuted. A $1,000 prize was offered by the inventor to anyone who could solve the puzzle. Historical accounts of the puzzle indicate that it generated an excitement similar to the Rubic's cube in the 1970's. Despite this no one ever collected the prize. Why? The answer to this question is not difficult^{(1)}. Suppose you record your moves using **(n,b)**, to indicate that you slid the counter **n** into the blank position. Then you would represent a sequence of moves, that start and end with the blank in the lower right hand corner, as **(n _{1},b), (n_{2},b), ..., (n_{k},b)**, where

**k**is an even number. So reachable permutations of the counters that fix the blank position are an even number of transpositions away from the desired configuration. This does not include the one which Sam Loyd was willing to pay money for, since it is a single transposition from the desired configuration. A mathematical explanation that the puzzle could not be solved (known to Loyd much earlier) surfaced in the early 1880's and the excitement petered out.

Richard Wilson [3], in 1974, gave a complete treatment of puzzles on graphs of which the Fifteen puzzle is a particular case. He considered labeling all but one vertex of a graph with counters and allowing a counter to move along an edge to the unlabelled vertex. He showed that 2-connected graphs without odd cycles generate precisely the even permutations of their counters (eg. The Fifteen puzzle or similar puzzles of different sizes). The argument given in the previous paragraph could also be used here to show that only even permutations are possible. The existence of an odd cycle (but not just being an odd cycle) in a 2-connected graph (with at least 8 vertices) was enough to guarantee that any labeling could be generated. An example of a puzzle that will generate any labeling is
**Lucky 7** (so named and described in [1]).

What if applet does not run? |

We will give a proof here, independent of Wilson's theorem, that all permutations are possible.

Let **L** denote a clockwise rotation of the left cycle (click on
position 1). Let little **l** denote a counterclockwise rotation of the
left cycle (click on position 3). Similarly let **R** and **r**
denote clockwise (click on position 7) and counterclockwise (click on
position 5) rotations of the right circle. Then applying the sequence **lRLrl**^{(2)} three times will swap counters 4 and 5, leaving the other counters fixed. With this sequence we now argue that any pair of counters can be swapped. Let **x** and **y** be any pair of counters. Rotate the outer circle (click on position 4, just below the vertical bridge) until one of either **x** or **y** is in position 5 and the other is in the left cycle. Now, if necessary, rotate the left cycle to get the other counter in position 4. Apply the sequence **lRLrl** three times to swap **x** and **y**. Now simply reverse the moves (both their order and direction) used to move **x** and **y** to these positions.

With digital technology it is now easy to create puzzles analogous to the Fifteen and Lucky 7 but with more elements. We can go one step further and construct puzzles that were not feasible in Sam Loyd's time. First, there is no need to restrict ourselves to planar surfaces. Fifteen can be played on a *cylinder* or a *Möbius strip*. More than that, there is no need to have the empty space either, as required by these mechanical puzzles. An interesting variation of the Fifteen puzzle that takes advantage of this great new technology is a puzzle called **Sliders**.

What if applet does not run? |

In this puzzle we are allowed to slide the rows and columns of the puzzle. On the *torus* version of Sliders, the
counters simply wrap around the row or column they are in. Note that in this
digital world there is no need for a vacant position. We can imagine, as Wilson
did with the Fifteen puzzle, the slider puzzle on a graph. In addition to the
4x4 grid of vertices and edges, we would need eight new edges that connect ends of the rows and columns to form 4-cycles. The moves allowed on the graph would be to rotate the counters
along these eight 4-cycles. Can we achieve all permutations of the counters or
will we again be limited to just the even permutations? See what permutations
of the counters you can produce.

Despite the similarities, this puzzle is much different from Sam Loyd's Fifteen puzzle. We will show that swapping the counters 14 and 15 does not result in an unsolvable arrangement. By this time you've noticed that odd permutations of the counters, as well as even ones, abound. Each move is an odd permutation.

We will first prove that the Sliders puzzle, for even sizes, played on the torus, can generate any permutation of its counters.

It is easy to see that there is enough freedom of movement to
be able to move any two counters to any two positions (as long as we don't
care where the other counters wind up). So consider the sequence
**(aBAba)(aBAba)(aBAba)**, where **B** represents moving the first row
to the left, **b** to the right, **A** moves the first column up,
and **a** moves it down. Applying this sequence swaps the counters in
the 1 and 2 positions, leaving the other counters in their place. Give it a
try! This shows we can swap any two counters by first moving them into these
positions, swapping them, and then moving them back (taking care to reverse
the moves used to get them there). Try swapping counters 5 and 12.
Furthermore, **(aBAba)** applied five times, yields a transposition of the 1 and 2 counters in the 6x6 puzzle and **(aBAba)** applied seven times does likewise for the 8x8.

Note that the moves in the 3x3, 5x5, and the other odd sizes, give only even permutations of the counters. So, as with the original Fifteen puzzle, not all configurations are possible. Also, the sequence that switches the counters in positions 1 and 2 involves movements along just one row and one column. This is represented in the underlying graph by sliding counters along two 4-cycles that intersect in a single vertex. The same sequence could be used with any slider type puzzle that has two cycles that intersect in a single vertex, as long as one of the cycles is even.

Another variation of the Sliders puzzle defines the wrap
around condition as though the puzzle is constructed on the surface of the
*Klein bottle*. The columns wrap as before, but the first row wraps with the
fourth and the second row with the third.

We will show that Sliders puzzle on the Klein bottle generates any configuration:

The method of proof is the same as before. We first note that
it is not difficult to move any two counters to any two locations. It will
be enough to find a sequence of moves that swap two counters, leaving the
other counters fixed. Again let **B** represent moving the first row to
the left (only now the bottom row moves left also), **b** to the right,
**A** moves the first column up, and **a** moves it down. For the
3x3 puzzle on the Klein bottle, the sequence **(abbAB)** applied five times
will swap counter 1 with counter 9. Try it! Note after doing **abbAB** we
get the permutation (1, 9)(2, 4, 8, 3, 7). On the 4x4 puzzle
**(abbAB)** yields the permutation (1, 16)(2, 3, 9, 14, 15, 4, 13). So
if we apply it seven times we
will have what we need to solve the puzzle. Likewise, **(abbAB)** raised
to the ninth power will switch the two corner counters on the 5x5 puzzle.

The final variation of the puzzle defines the wrap around
condition as though the puzzle is on the *projective plane*. Now the columns
and rows wrap as the rows did in the Klein bottle version. The proof here
follows the same line as the earlier arguments.

Again, it is easy to see that all we need to find is a sequence of moves that
will swap two of the counters, leaving the rest in their place. For the odd
size projective plane puzzles we can use the middle column and first row moves
and apply the sequence used with the Klein bottle puzzle (or use the middle
column and middle row and apply the sequence used with the torus puzzle).
For even puzzles let: **A** and **a** represent moving column 3 (and
column 2 along with it) up and down, respectively; and **B** and **b**
represent moving the top row (and bottom row along with it) left and right,
respectively. Then the sequence **bAAbaBaBB** applied nine times will swap
the counters in positions 2 and 3. For the 6x6 puzzle, the same sequence
applied fifteen times will swap the counters in positions 4 and 5. For the
8x8, applying the same sequence nine times will swap the counters in position
6 and 7. For the 10x10 apply it 39 times to swap 8 and 9. See the pattern?
It would help to apply the sequence once to each of the 6x6, 8x8, and 10x10
puzzles and examine the permutation you get. How many times should it be
applied to swap the 10 and 11 positions in the 12x12 puzzle?

**Projective Plane Sliders Puzzle Graph**

We can formulate a similar "Puzzles on Graphs" problem as Rick Wilson did,
but the situation seems far more complex. Consider a graph **G** which
is formed by taking the union of **k** cycles. Place counters on the
vertices and allow the counters to slide around each of these cycles. Under
what conditions on the cycles and the graph will we be able to reach any
configuration. The graph, so constructed, would need to be connected, but
would not have to be 2-connected. There would have to be at least two cycles,
and at least one of them would have to be an even cycle. For example: the
graph for the 4x4 Torus Slider puzzle is the union of eight 4-cycles that are
either pairwise disjoint or pairwise intersect in a single vertex; the graph
for the 4x4 Klein Bottle Slider puzzle is the union of two disjoint 8-cycles
and four disjoint 4-cycles (the 4-cycles each intersect the 8-cycles in two
different vertices); and the 4x4 Projective Plane Slider puzzle Graph is the
union of four 8-cycles that are either pairwise disjoint or intersect in
4 vertices (see picture).

If a graph **G** is the union of cycles
**C _{1}, C_{2}, ..., C_{k}** and we know that

**G**is connected,

**C**is an even m-cycle, and

_{1}**C**intersects it in a single vertex, then all configurations are possible. The Torus Sliders puzzle is a special case of this. Let

_{2}**a**and

**A**be counterclockwise and clockwise rotations of the counters on

**C**, and

_{1}**b**and

**B**be counterclockwise and clockwise rotations of the counters on

**C**. The sequence

_{2}**aBAba**(used with the torus puzzle) applied

**m - 1**times will swap the vertex in common with the two cycles and its adjacent vertex on

**C**. Being connected is enough to guarantee that any two counters can be moved to these two positions. What about other ways that

_{2}**C**can intersect

_{2}**C**? We conclude with a few special cases below

_{1}^{(3)}.

If two cycles intersect in two adjacent vertices we have, as
a special case, the **Happy 8**^{(4)} puzzle (*that is to Lucky 7 as Sliders is to Fifteen*.) The graph of the Happy 8 puzzle would be the union of three cycles, **C _{1}**,

**C**, and

_{2}**C**, where

_{3}**C**and

_{1}**C**intersect in an edge and

_{2}**C**is the cycle formed by taking the union of

_{3}**C**and

_{1}**C**and throwing away their common edge. At least one of these cycles would be even for if

_{2}**C**and

_{1}**C**were both odd, then

_{2}**C**would be even.

_{3}What if applet does not run? |

We can prove that all arrangements of the counters are possible for any size Happy 8 puzzle.

Indeed, the sequence **LRlrLRc** (where **L**
and **l** are clockwise and counterclockwise rotations of the counters on
the left circle, **R** and **r** are clockwise and counterclockwise
rotations of the counters on the right circle, and **c** is a
counterclockwise rotation of the counters on the outside cycle) will transpose
the two counters at the center, bottom, right of the puzzle for all puzzle
sizes containing more than 4 counters. The 4 counter Happy 8 puzzle can be
solved using the sequence **cl**.

Suppose the cycles C_{1} and C_{2} intersect
in two non-adjacent vertices. We have, as a special case of this situation, the
**Blithe 12** slider puzzle. The three 6-cycles pairwise intersect in two
non-adjacent vertices. Try to find a sequence of rotations that swap two
counters and leave the rest in their place. Can you find a sequence of
rotations that only involve two of the three cycles?

What if applet does not run? |

### Reference

- E.R.Berlekamp, J.H.Conway, R.K.Guy,
*Winning Ways for Your Mathematical Plays*, v2, Academic Press, 1982. *The Lighter Side of Mathematics*, R.K.Guy and R.E.Woodrow (eds), MAA, 1994.- R. M. Wilson,
*Graph Puzzles, Homotopy, and the Alternating Group*,__J. of Combinatorial Theory__, Ser B 16, 86-96 (1974).

### Endnotes

(1) As simple as the argument is, it apparently did not come up during the decade of initial craze in the United States and Europe that followed invention of the puzzle. The puzzle became classic ever since and has been included into various puzzle collections, none of which, to my knowledge, gave an explanation close in simplicity to Don's. However, for the general case, or even for the second puzzle distributed by Sam Loyd (the left upper corner blank with counters arranged in the natural order) a more general argument is needed.

(2) The applet has a "Cycles" button. When the button is checked, the permutation that represents the current state of the puzzle is shown as a product of cycles. In particular,

**lRLrl**= (1 3 2)(4 5)(6)(7). Therefore, (**lRLrl**)^{3}= (4 5).(3) We use this opportunity to introduce additional sliding puzzles. The special case of the Fifteen puzzle on the cylinder and the Möbius strip is left as an exercise.

(4) In a chapter in [2], J.A.Eidswick describes a family of

*circle*puzzles generalizing the one known as*Engel's Enigma*. The latter, like the Happy 8 puzzle, is a union of two cycles; but there are two distinct types of nodes -*stones*and*bones*- that permute independently. Generalizations compare favorably in complexity with the Rubik cube puzzle.

Don Greenwell is Professor of Mathematical Sciences and Foundation Professor at Eastern Kentucky University. During his thirty years in teaching he has taught mathematics or computer science at Louisiana State Universtiy, Auburn University, Iowa State University, Emory University, and Arkansas State University. He holds M.S. and Ph.D. degrees from Vanderbilt University.

## Related material
| |

## Sliders and Puzzles on Graphs | |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

| |

|Contact| |Front page| |Contents| |Geometry|

Copyright © 1996-2017 Alexander Bogomolny

62685775 |