October 27, 2011

Oval Track Puzzles

The puzzle known as TopSpin consists of 20 circular pieces, numbered 1 to 20, filling and sliding along an oval track. TopSpin was introduced by ThinkFun (formerly Binary Arts) in 1988.

Pieces can be moved around the track in either direction, keeping their order. Or any four consecutive pieces can be maneuvered into reverse order. For example, consecutive pieces labeled 1, 2, 3, and 4, can be reversed into the order 4, 3, 2, 1.

TopSpin allows two types of moves. Numbered tokens can be moved around the track in either direction (left) or the order of four consecutive tokens can be reversed.

Interestingly, this puzzle has no impossible positions. Any possible arrangement (or permutation) of the pieces can be turned into any other arrangement. That would not be true if the puzzle had either 19 or 21 pieces.

This puzzle was the subject of a recent Numberplay blog, titled "From Sledgehammer to Scalpel," on the New York Times website. Pradeep Mutalik introduced the puzzle and noted: "The challenge is to create a way of moving a single unit without affecting the rest."

The puzzle has a long history and has been the subject of both research papers and books. In his article "TopSpin on the Symmetric Group," published in the September 2000 Math Horizons, Curtis D. Bennett illustrated how abstract algebra and group theory can be used to analyze the puzzle and develop a strategy for solving it.

In the book Oval Track and Other Permutation Puzzles—And Just Enough Group Theory to Solve Them (MAA, 2003), John O. Kiltinen describes TopSpin, in permutation group terms, as "a concrete realization of the subgroup of the symmetric group S20 which is generated by the twenty-cycle (1, 2, 3, . . . , 20) and the product (1, 4)(2, 3) of two disjoint transpositions."

"Group-theoretically, the puzzle is simple to describe, but from a practical standpoint, it is nontrivial to solve," Kiltinen writes. "This makes it an excellent object of study for students of abstract algebra, giving them a concrete representation of a nontrivial and fruitful application of the theory of permutation groups."

Kiltinen's book comes with software (on a CD-ROM) to try and to study the puzzle, including variants that could not be realized in plastic. The book is currently available from the MAA bookstore at a special bargain price.

In his Numberplay blog, Mutalik poses the following problem: The puzzle's initial configuration has all the tokens in order, except that 19 and 20 are reversed. He asks: How can you move token 19 into its proper place without affecting the order of the others? Could you have done so if the tokens were arranged linearly and not in a loop?

Finally, Mutalik asks, "Can you analyze the analogous problem where you flip the order of five tokens at a time?"

"At ten I was fascinated by permutation puzzles like the fifteen puzzle," Bennett remarked. "At seventeen, I became enamored of the Rubik's cube, and today I still look for puzzles like these whenever I visit a toy store."

"For me today, however, the beauty of these puzzles is how easily they lead to deeper mathematics," he added.

Bennett's article was reprinted in the book The Edge of the Universe: Celebrating Ten Years of Math Horizons (MAA, 2006), edited by Deanna Haunsperger and Stephen Kennedy.

Further References:

Kaufmann, S. 2011. A mathematical analysis of the generalized oval track puzzle. Rose-Hulman Undergraduate Mathematics Journal 12(Spring):70-90.

Wilson, J.H. 1993. Permutation puzzles. College Mathematics Journal 24(March):163-165.

No comments: