WWW.DISSERTATION.XLIBX.INFO
FREE ELECTRONIC LIBRARY - Dissertations, online materials
 
<< HOME
CONTACTS



«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 fixed window (the swapping window ) of 4 tiles that

reverses the order of the tiles within the window, leaving the other 16 tiles fixed. 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 fix the location of the swap window on the string. Finally, elements in the swap window will be enclosed by parentheses.

Definition: 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.

Definition: The puzzle (n, k) is solved if the puzzle’s configuration is in the identity con- figuration (i.e. 1 2... n).

Definition: A swap is the operation defined by the reflection 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 Definition: A translation is the movement defined 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 definitions:

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

Definition: 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 configuration x to the identity configuration 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 configuration 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 configuration to the identity configuration 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 configuration of the puzzle is the identity configuration

–  –  –





(2) Next, we fix 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 configuration

–  –  –

(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 configuration

–  –  –

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 configuration

–  –  –

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 first showing the existence of a k − cycle which we will use to find a 3 − cycle. Define τ 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 fix 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 confirm 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 first 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 fixed 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 fixed 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. στ σ), finally 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 first 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 configuration 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 fixed (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 fixes 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





Similar works:

«Sensors 2013, 13, 10151-10166; doi:10.3390/s130810151 OPEN ACCESS sensors ISSN 1424-8220 www.mdpi.com/journal/sensors Article Measuring Center of Pressure Signals to Quantify Human Balance Using Multivariate Multiscale Entropy by Designing a Force Platform Cheng-Wei Huang 1, Pei-Der Sue 1, Maysam F. Abbod 2, Bernard C. Jiang 3,4 and Jiann-Shing Shieh 1,4,* 1 Department of Mechanical Engineering, Yuan Ze University, Chung-Li 32003, Taiwan; E-Mails: s1005058@mail.yzu.edu.tw (C.-W.H.);...»

«Bibliotheca Hagiotheca ∙ Series Colloquia II Saintly Bishops and Bishops’ Saints: Proceedings of the 3rd Hagiography Conference organized by Croatian Hagiography Society 'Hagiotheca' and International Hagiography Society, Poreč, 27-30 May 2010 Edited by John S. Ott and Trpimir Vedriš Copy-editing: Marina Miladinov Bibliotheca Hagiotheca ∙ Series Colloquia, vol. 2. Series editors: Ana Marinković and Trpimir Vedriš First published 2012 Croatian Hagiography Society 'Hagiotheca',...»

«Dedication This edition is dedicated to my old Dungeons & Dragons group, The Mutants of the Round Table (you know who you are), friends and family, and all those who supported me with encouragement, comments, reviews, and suggestions. Books by D.L. Morrese ~*~ ~Stories of the Warden's World~ An Android Dog’s Tale Defying Fate (Combined eBook Edition) The Warden Threat (Defying Fate Part 1) The Warden War (Defying Fate Part 2) Amy’s Pendant Disturbing Clockwork ~*~ ~Adventures of the Brane...»

«Automatic Extraction of Generic House Roofs from High Resolution Aerial Imagery ? Frank Bignone, Olof Henricsson, Pascal Fua+ and Markus Stricker Communications Technology Laboratory Swiss Federal Institute of Technology ETH CH-8092 Zurich, Switzerland + SRI International, Menlo Park, CA 94025, USA Abstract. We present a technique to extract complex suburban roofs from sets of aerial images. Because we combine 2-D edge information, photometric and chromatic attributes and 3-D information, we...»

«Pour citer cet article : LE BRETON, D. « Concepts et significations majeures des conduites à risque », Journal des socio-anthropologues de l'adolescence et de la jeunesse, Revue en-ligne. Date de publication : janvier 2012. [http://anthropoado.com/le-journal-des-socio-anthropologues-de-l-adolescence-et-de-lajeunesse-textes-en-ligne/] Concepts et significations majeures des conduites à risque Par David Le Breton Significations des conduites à risque Paradoxalement les conduites à risque...»

«CIGE Insights Internationalizing the Tenure Code Policies to Promote a Globally Focused Faculty ACE and the American Council on Education are registered marks of the American Council on Education and may not be used or reproduced without the express written permission of ACE. American Council on Education One Dupont Circle NW Washington, DC 20036 © 2015. All rights reserved. No part of this publication may be reproduced or transmitted in any form or by any means electronic or mechanical,...»

«Determination of Texture From Individual Grain Orientation Measurements John E. Blendell, Mark D. Vaudin and Edwin R. Fuller, Jr. Ceramics Division Materials Science and Engineering Laboratory National Institute of Standards and Technology Gaithersburg, MD 20899 USA Abstract We present a technique for determining the texture of a polycrystalline material based on the measurement of the orientation of a number of individual grains. We assumed that the sample has fiber (i.e. axisymmetric) texture...»

«How-To Guide CUSTOMER Document Version: 1.5 – 2015-12-28 How to Scramble Data Using SAP Test Data Migration Server Release 4.0 Typographic Conventions Type Style Description Example Words or characters quoted from the screen. These include field names, screen titles, pushbuttons labels, menu names, menu paths, and menu options. Textual cross-references to other documents. Example Emphasized words or expressions. Technical names of system objects. These include report names, program names,...»

«Installation Manual Frameworx Gutter and Capping August 2012 / 84-900030-000 Frameworx Gutter and Capping Installation Manual © August 2012 by the Brunswick Bowling and Billiards Corporation. All rights reserved. A-2, BallWall, Frameworx, GS-Series, Pinball Wizard, and Tel-E-foul, and are registered trademarks of the Brunswick Bowling and Billiards Corporation. Reorder Part No. 84-900030-000 Notice: If available, updates to this manual can be found on-line at www.centermaster.com. All...»

«14. CONGRESS OF THE INTERNATIONAL SOCIETY FOR PHOTOGRAMMETRY HAMBURG 1980 COMMISSION IV, WORKING GROUP 1 PRESENTED PAPER HEINRICH EBNER, BERNHARD HOFMANN-WELLENHOF, PETER REISS, FRANZ STEIDLER LEHRSTUHL FOR PHOTOGRAMMETRIE TECHNISCHE UNIVERSIT~T MONCHEN ARCISSTR. 21 POSTFACH 202420 08000 MONCHEN 2 HIFI A ~1INICOMPUTER PROGRAM PACKAGE FOR HEIGHT INTERPOLATION BY FINITE ELEMENTS *) ABSTRACT A general minicomputer program package for height interpolation is presented. It is written in FORTRAN...»

«NEVADA LEGISLATURE NEVADA SILVER HAIRED LEGISLATIVE FORUM (Nevada Revised Statutes 427A.320 through 427A.400) SUMMARY MINUTES AND ACTION REPORT The sixth meeting of the Nevada Silver Haired Legislative Forum (NSHLF) for the 2007-2008 interim period was held on Tuesday, May 13, 2008, at 10 a.m. in Room 4401 of the Grant Sawyer State Office Building, 555 East Washington Avenue, Las Vegas, Nevada. The meeting was also videoconferenced to Room 3138 of the Legislative Building, 401 South Carson...»

«THAMES BASIN HEATHS SPA TECHNICAL BACKGROUND DOCUMENT TO THE CORE STRATEGY DPD June 2007 INCLUDING AN APPROPRIATE ASSESSMENT OF THE CORE STRATEGY DPD AND AVOIDANCE AND MITIGATION STRATEGY Thames Basin Heaths SPA – Technical Background Document to the Core Strategy DPD JUNE 2007 1 Thames Basin Heaths SPA – Technical Background Document to the Core Strategy DPD JUNE 2007 2 Thames Basin Heaths SPA – Technical Background Document to the Core Strategy DPD JUNE 2007 Contents Section...»





 
<<  HOME   |    CONTACTS
2016 www.dissertation.xlibx.info - Dissertations, online materials

Materials of this site are available for review, all rights belong to their respective owners.
If you do not agree with the fact that your material is placed on this site, please, email us, we will within 1-2 business days delete him.