Oval Track and Other Permutation Puzzles, and just enough group theory to solve them

John O. Kiltinen
Publisher:
Mathematical Association of America
Publication Date:
2003
Number of Pages:
304
Format:
Paperback
Series:
Classroom Resource Materials
Price:
42.50
ISBN:
:0-88385-725-1
Category:
Monograph
[Reviewed by
Ruth I. Berger
, on
04/12/2004
]

Oval Track and other permutation puzzles is a fantastic book for anyone who loves to play with puzzles similar to Rubik's cube, or anyone interested in "practical" applications of permutations. The main feature of the book is the enclosed CD-ROM that contains several computerized puzzles. The very well designed PC and Mac compatible software comes with an easy to use tool bar and can be used even without reading the book, just like Rubik's cube can be picked up and played with by anyone. But one quickly realizes that in order to solve the puzzles some knowledge of mathematics is needed. As the sub-title accurately states, the book provides the group theory knowledge that is necessary to solve the puzzles. It is written for an audience with no previous exposure to group theory, and it is certainly accessible to any beginning mathematics student. The more mathematically experienced reader can skip the explanations of inverses and other basic group theory concepts and go straight to the chapters that explain how this knowledge can be applied to solving the puzzles.

The puzzles featured are the Oval track puzzle, the well known Slide puzzle, and the very challenging Hungarian Rings puzzle (see details below). These puzzles are inspired by existing games, but this computerized version generalizes them by offering you the option of choosing variations, such as reducing the number of active disks. All of the puzzles shuffle disks in a two-dimensional setting: a disk goes from position #1 to position #2. The moves can therefore be viewed as permutations of the set {1, 2, ..., n}, where n is the number of active disks.

This book is intended to be read while sitting at the computer and trying out the ideas presented. You can either literally follow the example in the book, or experiment with examples along the same lines, using the ideas presented in the text. Exercises are presented at end of each section to guide reader through more explorations. It is up to the reader to decide how much guidance they need.

While working through the book you feel as if the author is standing behind you, looking over your shoulder and giving helpful hints and suggestions on what you may want to try next. This is by no means a manual with step by step descriptions on how to proceed. The author never provides a complete solution, instead he provides just enough theory to enable you to work successfully on the puzzles. This book actually contains a surprising amount of group theory, but never presented in lecture style. All problems are first presented in the terminology of the puzzles, then translated to mathematical terms, and finally the relevant mathematical theory is introduced in great detail.

This book is published in the "Classroom Resources Materials" series of the MAA. And indeed, working with these puzzles serves as a great introduction to permutations. If the readers go on to an Abstract Algebra course they already have a good working knowledge of permutations and can better appreciate the theory. The style is very informal. Even the occasional "proof" is really just an illustration in a concrete case, asking the readers to try more examples and convince themselves that the statement is true. The author wants the readers to have fun working with the puzzles and gain an appreciation of mathematics in the process.

The Puzzles:

The Oval track puzzle consists of a circular track with disks numbered from 1 to 20, or less if desired. Two types of moves can be performed: you can rotate the whole ring, keeping the disks in order, and you can perform a fixed permutation in an "active zone". In the first Oval Track puzzle this permutation is (1,4)(2,3), modeling the original game where the disks in positions #1, 2, 3, 4 can be rotated by 180 degrees. The other versions of Oval Track have different permutations in the active zone, you even have the option of designing your own! The object of the game is to mix up the disks (the shuffle button can do that for you) and then try to get them back into the original order.

The Slide puzzle is the well known 4 x 4 square with tiles numbered 1 through 15 and one empty slot. Any piece that is adjacent to the empty slot can be moved into that slot. Again the object is to try and put a shuffled game back into order. This computerized version lets you select less than 15 active tiles and also has the option of working with a second empty slot.

The very challenging Hungarian Rings puzzle is also modeled after an existing game. It basically consists of two circular tracks of disks numbered 1 through 38. The tracks intersect in two places and can only exchange disks at these intersection points. Again, you have the option of reducing the number of active disks, and you can also select a simpler "color-only" version.

It is very easy to learn how to use the software. All puzzles have the same menu bar including a scramble disks button, view moves, save settings, "undo last moves", and "program a macro" button.

The latter lets you input a particularly useful set of moves which can then all be performed at once by pressing a single "do macro" button. The Puzzle Resource menu allows you to either load a pre-programmed configuration, or to store and retrieve an unlimited number of your own settings. The capacity of the program is too large to be accurately described here, you need to try it out for yourself! It is noticeable that the author spent many years working on it and perfecting it before releasing it to the public.

Overview of some of the content:

The book starts out by explaining how the puzzles work and encourages the reader to experiment with solving them. You soon discover that you can get many disks back in order relatively easily. It is only the last few disks that are very difficult to get into order without undoing all the previous work. For this "endgame" it would be nice to be able to perform a specific permutation, such as a single 3-cycle. The reader is now ready to read the chapter that explains the mathematics needed to do exactly that. So how can one find a set of moves that result in only moving a few of the up to 20 active disks in an Oval Track puzzle, leaving all other positions fixed? The author suggests looking at commutators aba-1b-1, since they stand a good chance to be "close to the identity". For the first Oval Track puzzle a set of moves resulting in the 3-cycle (7,4,1) is provided. For the other puzzles the reader is left to experiment with commutators on their own. More guidance is provided in the exercises where specific commutators are suggested for examination. Having found a set of moves that perform (7, 4, 1) they can be programmed into a macro. Now one push of the button will perform all steps at once: the disk in position 7 goes to position 4, the disk in position 4 goes to position 1 and the disk in position 1 goes to position 7, leaving all other positions fixed. By the way, the notation introduced in the book reads permutations from left to right, i.e the function acting on an object is written to the right of the object.

But how often will one end up with a puzzle that needs the 3-cycle (7, 4, 1) performed? What if one needs the 3-cycle (3, 5, 12) instead? The author again uses the opportunity to introduce more helpful mathematics: the concept of conjugates. He suggests you try to find a set of moves that puts 3, 5, 12 into positions 7, 4, 1, respectively. This is not easy, but at least you don't need to worry about leaving all other disks fixed. It does not matter how "mixed up" they get, because the inverse permutation will put them back into order later. Having macro B perform (7,4,1), and macro A implementing a permutation that puts 3, 5, 12 into positions 7, 4, 1 (while possibly shuffling others), you can now perform ABA-1, which will result in (3, 5, 12), affecting only the three disks that you wanted to shuffle! Even the most uninterested Abstract Algebra student will appreciate the concept of conjugates when presented in this concrete form!

Besides giving the reader the tools to solve the puzzles, the author also discusses how to predict if a particular random shuffle can be solved. If you are working with the first version of Oval Track and an odd number n of disks you can only perform moves generated by T = (1,4)(2,3) and the rotation R = (1,2,3,...,n). Both of these generators are even permutations, hence a random shuffle of disks that represents an odd permutation can never be brought back to the original position. A random shuffle of the n disks in Oval Track represents an element of Sn. Which fraction of all possible permutations can be solved depends on the number of active disks, and which version of the puzzle you are working with. The author gives concrete code for Maple and GAP that the interested reader can use to find the size of the subgroup of Sn generated by R and T.

Of course all this theory also applies to the original puzzles, so why should one prefer the computerized versions? As mentioned already, the software lets you introduce many variations on the original puzzles, so you actually have hundreds of different puzzles to work with. But the main advantage of using the computer version of the puzzles is the speed with which moves can be completed. It may sound easy to perform moves that result in a simple 3-cycle, but this may take twenty or thirty moves! Completely solving a puzzle by hand would be a very time consuming and tedious process. Utilizing the built-in macro buttons allows you to concentrate on the theory and really have fun with the puzzles.

This well written book and included software is highly recommended. Get a copy and try it out for yourself. You may not be able to put it down and neither will your students!

System requirements for the included software:

• Windows: Windows 95 or later, 8.1 MB on Hard Drive
• Macintosh OS X: OS X, any version, 10.6 MB on Hard Drive
• Macintosh Classic: System 7.1 or later, 11.2 MB on Hard Drive

Ruth I. Berger (bergerr@luther.edu) is Associate Professor of Mathematics at Luther College. Her favorite upper-level courses to teach are Abstract Algebra, Number Theory and Geometry. She is currently representing the Iowa section on the MAA board of governors.