Cut the knot: learn to enjoy mathematics
A math books store at a unique math study site. Learn to enjoy mathematics.
Google
Web CTK
Best sites for teachers
Sites for teachers
Sites for parents
Terms of use
Awards

Interactive Activities
CTK Exchange
CTK Insights - a blog

Games & Puzzles
What Is What
Arithmetic/Algebra
Geometry
Probability
Outline Mathematics
Make an Identity
Book Reviews
Eye Opener
Analog Gadgets
Inventor's Paradox
Did you know?...
Proofs
Math as Language
Things Impossible
Visual Illusions
My Logo
Math Poll
Cut The Knot!
MSET99 Talk
Other Math sites
Front Page
Movie shortcuts
Personal info
Reciprocal links
Privacy Policy

Guest book
News sites

Recommend this site

Best sites for teachers
Sites for teachers
Sites for parents

Education & Parenting

Manifesto: what CTK is about Search CTK Buying a book is a commitment to learning Table of content Things you can find on CTK Chronology of updates Email to Cut The Knot Recommend this page

Sliders Puzzle, Proof of solvability

On a torus, every 4x4 configuration is solvable.

First I will establish the following

Lemma

Let n=4. For any two adjacent counters there exists a sequence of moves that leaves all counters but the given two untouched. The two given counters, as the result of this sequence of moves, swap their locations.

Proof of the Proposition

Let's show how to swap two counters a and b without disturbing all the rest. One (horizontal) move is needed to slide a into position d one column to the right from b. With the second (vertical) move we can slide a into position c adjacent to d. Now we swap counters at c and d. Next we execute reverses of the original moves; first vertical and then horizontal.

Since one can just swap any two adjacent counters one can also swap any two counters which are not necessarily adjacent. Thus the Lemma renders the Proposition obvious. First swap the counter #1 with whichever occupies its rightful location in the upper left corner. Locate the counter #2 and swap it into its position, next to the #1, and so on.

Proof of the Lemma

Since the proof is constructive, i.e. I am going to describe the sequence of moves that proves the Lemma, the main difficulty is in inventing concise notations to describe the sequence. Let's agree in advance that the sequence consisting of two moves A and B executed consecutively will be denoted AB. Now for the notations:

S-i _ slide the i-th row left
S+i _ slide the i-th row right
Sj- _ slide the j-th column up
Sj+ _ slide the j-th column down
V(-i, j-) S-iSj+S+iSj- rotate three counters. (i,j) is in the right corner
H(-i, j+) Sj+S+iSj-S-i rotate three counters. (i,j) is in the right corner
V(+i, j-) S+iSj+S-iSj- rotate three counters. (i,j) is in the right corner
H(+i, j+) Sj+S-iSj-S+i rotate three counters. (i,j) is in the right corner
G(-i, j) H(-i, j+)V(-i, j-) rotate three counters. (i,j) is in the middle
G(+i, j) H(+i, j+)V(+i, j-) rotate three counters. (i,j) is in the middle
F(i, j, j+1) G(+i, j+1)G(i, j)S-i swap two counters. (i,j) is on the left

F(i, j, j+1), the last transformation in the table, swaps two horizontally adjacent counters. Rotating the tray 90o and applying the same transformation we'll get a sequence of moves that flips two vertically adjacent counters. This proves the Lemma.

Note that the sequences in the table produce the desired effect (diagrams) for any n > 2, not necessarily 4. However, the last line, the transformation F is specific to the 4x4 puzzle. This is due to the fact that the last move in the sequence, S-i, for n > 4, would rotate a row thus shifting (n-4) counters out of their original locations.

Note also that the proof, although constructive, is far from optimal. With little ingenuity it's always possible to find a shorter solution.

Lastly, for n=3, F is an identical transformation. This shows that the group of sliding transformations is not free.

Remarks

The theory above applies only to the Sliders on torus. Don Greenwell offers different sequences of moves that cover the cases of n > 4 and even the Klein bottle and the projective plane cases.

Copyright © 1996-2008 Alexander Bogomolny

28764946Page copy protected against web site content infringement by Copyscape


Search:
Keywords:


Latest on CTK Exchange
Math
Posted by Laura
2 messages
06:56 AM, Apr-15-08

Divisibility rules - Jargon buste ...
Posted by Carolyn
2 messages
08:35 AM, Apr-04-08

drawing puzzle
Posted by martin gran
31 messages
06:53 PM, May-09-08

conway's game of life
Posted by frequency
0 messages
11:52 PM, May-12-08

Mistake on the page (an aside, Be ...
Posted by Max
4 messages
10:28 AM, Feb-28-08

A Riddle
Posted by idavis1
33 messages
06:59 AM, May-15-08

Josephus Flavius (correction)
Posted by David Turner
1 messages
09:42 AM, May-14-08