# «Terminology To facilitate easy demonstration of game movements we shall employ a linear notation (i.e. a string of numbers) that begins with the ...»

Proof of Solvability for the

Generalized Oval Track Puzzle

Sam Kaufmann and Andreas Kavountzis

Research Advisor: Dr. Richard Statman

Department of Mathematics

Carnegie Mellon University

Introduction

The oval track puzzle (also known as Top Spin) is a game consisting of 20 numbered tiles in

an oval shaped track. Also, there is a ﬁxed window (the swapping window ) of 4 tiles that

reverses the order of the tiles within the window, leaving the other 16 tiles ﬁxed. The object

of the puzzle is to reorder the tiles into counting order using the mechanisms of the puzzle.

Our paper presents conditions for both solvability and non-solvability for the general oval track puzzle with n total tiles and k tiles in the swapping window.

Terminology To facilitate easy demonstration of game movements we shall employ a linear notation (i.e.

a string of numbers) that begins with the left-most member of the swapping window in considering permutations. Here we tacitly use the notion of position when determining permutations by using this notation. However at times, mostly for the purpose of illustration, we will not ﬁx the location of the swap window on the string. Finally, elements in the swap window will be enclosed by parentheses.

Deﬁnition: We represent the puzzle consisting of n total tiles and k tiles in the swapping window by the 2-tuple (n, k).

Remark: We assume that the bounds 2 ≤ k n must hold for the mechanism of the puzzle to work.

Deﬁnition: The puzzle (n, k) is solved if the puzzle’s conﬁguration is in the identity con- ﬁguration (i.e. 1 2... n).

Deﬁnition: A swap is the operation deﬁned by the reﬂection of the k tiles in the swapping window. Since the value of k can be odd or even, we have two cases for the way in which the

**k tiles in the swapping window can be rearranged:**

• Even Case:

Let a1, a2,..., ak be the k tiles inside the swapping window, in the order shown, with a1 in position 1. For k even, we have that one swap will yield a new permutation equal to (a1 ak )(a2 ak−1 )... (ak ak +1 ).

2 2 1

• Odd Case:

Let a1, a2,..., ak be the k tiles inside the swapping window, in the order shown, with a1 in position 1. For k odd, we have that one swap will yield a new permutation equal to (a1 ak )(a2 ak−1 )... (a k ).

2 Deﬁnition: A translation is the movement deﬁned by sliding the tiles within the track such that any tile in position i is moved to position i + 1 for i = 1,..., n - 1. In other words, if we let 1, 2,..., n indicate the positions of the tiles in the track, then a translation can be described by the n-cycle (1 2... n).

Remark: Note that applying a swap twice or applying a translation n times both leave the puzzle unchanged. Furthermore, due to the circular nature of the puzzle, we consider permutations to be equivalent up to translation.

Solvability

**Before discussing the solvability of the puzzle, we need to give the following deﬁnitions:**

Deﬁnition: The family of all permutations of {1, 2,..., n} is called the symmetric group on n-letters, denoted by Sn [3, pg. 107].

Deﬁnition: The subset of Sn consisting of all even permutations is called the alternating group, denoted by An [3, pg. 150].

Throughout this paper, we will be presenting cases for which the puzzle is solvable and cases for which the puzzle is not solvable. However, what does it mean for the puzzle to be solvable? The following theorem addresses this question.

Theorem 0: The puzzle (n, k) is solvable if and only if we can generate all permutations π ∈ Sn.

**Proof:**

1. If we can generate all permutations π ∈ Sn, then the puzzle (n, k) is solvable.

Assume we can generate all permutations in Sn. If this were the case, then we could go from any puzzle conﬁguration x to the identity conﬁguration by applying a permutation. This permutation is characterized by undoing the moves that it took to get to x. Thus, we can solve the puzzle.

2. If the puzzle (n, k) is solvable, then we can generate all permutations π ∈ Sn.

If the puzzle is solvable, then we have to be able to switch adjacent tiles. For instance, if the conﬁguration was 1 3 2 4... n, then we would have to switch tiles 2 and 3 in order for the puzzle to be solved. Thus, if we can switch adjacent elements, we can perform disjoint transpositions, and since any permutation π ∈ Sn is the product of disjoint transpositions, we can generate all permutations in Sn.

Cases Theorem 1: If n ≡ 0 (mod 2) and k ≡ 0 (mod 4) or k ≡ 2 (mod 4), then the puzzle is solvable.

**Proof:**

To prove this, we will present an algorithm that switches adjacent tiles in the puzzle. If we can create an adjacent transposition, then we can go from any conﬁguration to the identity conﬁguration by simply transposing the elements pairwise into their correct positions. The algorithm uses a special move called a swap-translation. Like the name describes, a swaptranslation is a swap immediately followed by a translation. Note that when using a swaptranslation, one needs to specify which direction the translation is going in. Using this special move, we can go through the steps of the algorithm. Assume without loss of generality that the starting conﬁguration of the puzzle is the identity conﬁguration

(2) Next, we ﬁx the rightmost k - 1 elements of the swap window and perform n−(k−1)−2 = n − k − 1 counterclockwise swap-translations. This will bring us to the conﬁguration

(3) Now we perform k +1 swap-translations, alternating the direction we translate, beginning 2 with a counterclockwise translation. This step moves 1 and 2 into the two center positions of the swap window. This gives us the conﬁguration

if k ≡ 2 (mod 4).

(4) Now we perform k swap-translations, alternating the direction we translate, beginning 2 with a clockwise translation if k ≡0 (mod 4) and a counterclockwise translation if k ≡ 2 (mod 4). This brings us to the conﬁguration

Thus, we can solve the puzzle.

Theorem 2: If n ≡ 1 (mod 2) and k ≡ 3 (mod 4), then the puzzle is solvable.

**Proof:**

We show this case by ﬁrst showing the existence of a k − cycle which we will use to ﬁnd a 3 − cycle. Deﬁne τ to be a clockwise translation, and σ to be a swap. Now applying the following sequence of moves to the puzzle (read from left to right) we will arrive at a k − cycle.

Informally, in employing this sequence of moves we essentially ﬁx elements 1... k-1 and move the remaining elements ”around” them. Since n − k is even and the order of σ is 2 (i.e.

σ 2 leaves the puzzle unchanged) it follows that 1... k-1 will be in the correct numerical ordering after this sequence of moves.

Using this k − cycle we will now exhibit a 3 − cycle. We shall apply the following moves to

**the puzzle:**

which yields the consecutive 3-cycle (k k+1 k-1).

Now we shall apply the following Lemma’s (Lemma 1 is borrowed from [2]).

Lemma 1: For n ≥ 3, the consecutive 3-cycles generate An.

Lemma 2: Given An and an odd permutation, we can generate all of Sn.

**Proof:**

Since τ is an odd permutation, if we take π ∈ An then

** τ ◦ π and π ◦ τ**

are odd permutations. Therefore these permutations are not in An. This implies that any other subgroup we generate will be larger than An. By Lagrange’s Theorem [3, pg. 156] we know that the order of this subgroup must divide the order of the group. Therefore since |An | is the largest divisor of |Sn | (other than |Sn |), the larger subgroup generated is Sn.

Now that we have generated An by Lemma 1, it remains to show that we have an odd permutation. By Lemma 2, the composition of this odd permutation with elements of An will generate Sn and conﬁrm the puzzle is solvable. The odd permutation we seek is σ. Therefore the game is solvable.

Theorem 3: If n ≡ 1 (mod 2) and k ≡ 2 (mod 4), then the puzzle is solvable.

Proof: We shall proceed in a similar manner similar to that of Theorem 2. We begin by mentally glueing the ﬁrst two tiles together and moving them both out of the window. This allows us to take tiles 3... k+1 and view them as f ixed (i.e. never leaving) in the swapping window. Similar to the proof of Theorem 2 we now proceed to move the remaining tiles past the ﬁxed elements in a series of n−k +1 swap−translations (i.e. (στ )n−k+1 ). Since n−k +1 is even we know that after this sequence of swap − translates that the ﬁxed elements will remain in the correct counting order.

**To better illustrate this we give the linear representation:**

This allows us to see that we now have the pair to which we can apply the same process (i.e.

begin by mentally glueing them together). We repeat this process of pairing elements of the

**swapping window k times, written linearly as:**

2

Which yields the (k + 1) − cycle (k+1 1... k).

Using this (k +1)−cycle we shall now exhibit a consecutive 3-cycle to generate An. We begin by performing a swap−translate, then a swap, (i.e. στ σ), ﬁnally we apply our (k +1)−cycle

**twice. Written linearly this is:**

Which yields the consecutive 3-cycle (k+2 k k+1). Again using Lemma 1 we can now generate the alternating group, An. Since σ is an odd permutation, we can now generate all of Sn by Lemma 2. Therefore the puzzle is solvable.

Theorem 4: If n ≡ 1 (mod 2) and k ≡ 0 (mod 4) or k ≡ 1 (mod 4), then the puzzle is not solvable.

**Proof:**

We ﬁrst note that the proofs of theorems 2 and 3 give us the same consecutive 3-cycles for these two given cases. Thus, in these two cases, we can generate An. However, also note that since σ is our only generator of the group in this case and k is even, we have that 2 σ is even and thus we do not have an odd permutation. It follows that any permutation π characterizing the conﬁguration of a given puzzle can only be π ∈ An and therefore the puzzle is unsolvable.

6 Theorem 5: If n ≡ 0 (mod 2) and k ≡ 1 (mod 4) or k ≡ 3 (mod 4), then the puzzle is not solvable.

**Proof:**

Begin by coloring tiles alternately with two colors, we shall use red and green without loss of generality. Note that the tiles are now partitioned by color and parity, that is to say, the red tiles form the set of even numbers in {1... n} and green tiles form the set of odd numbers.

Since n is even it follows that there will be pairs of oppositely colored tiles. Furthermore, since k is odd any swap will result in an element remaining ﬁxed (i.e. the center tile of the swapping window).

Next, enumerate the positions of tiles beginning with 1 on the game, again using the leftmost position of the swapping window as a reference point. Since every swap ﬁxes a center point, the only permutations generated transpose tiles of the same parity and therefore the same color. Thus, if two adjacent tiles are of the same color, we cannot create any permutation that will transpose the two. Therefore the puzzle is not solvable.

[1] E. Wilbur, Topspin: Solvability of Sliding Number Games, Rose-Hulman Undergraduate Math Journal; Vol. 2, Issue 2, 2001.

[2] A. F. Archer, A Modern Treatment of the 15 Puzzle, American Mathematical Monthly, November 1999, pp. 793-799

## [3] J.J. Rotman, A First Course in

**Abstract**

Algebra, Prentice Hall, 2006.

8