# The cycle notation and M12

• Overview

#### Simple Groups at Play

The M12 puzzle has 12 pieces arranged in a row and numbered 1-12 (see Fig. 1). There are two moves. The 'Invert' (I) move reverses the order of the pieces (Fig. 2) and the 'Merge' (M) move shuffles the pieces as a deck of cards (Fig. 3). The group of all possible moves we can get by repeating the I and M moves in arbitrary order is the Mathieu group M12. The 'Randomize' function displays a result of a random sequence of moves, and the player is supposed to reach the initial position by repeated use of the I and M moves.

To solve the M12 puzzle, it is convenient to represent moves in cycle notation. In this notation, in each parenthesis, each number is moved to the position of the next number, and the last number moves back to the first. Thus, for example, the I move is represented as

I = (1,12)(2,11)(3,10)(4,9)(5,8)(6,7)

and the M move as

M = (1)(2,3,5,9,8,10,6,11,4,7,12).

The strategy for solving the M12 puzzle is to device sequences of moves which accomplish particular tasks. The basic piece of information is that the group M12 can move any 5 numbers to any 5 positions in any orderchosen, but has precisely 12.11.10.9.8 elements, so the positions of all other numbers are determined by the positions of the first 5. Thus, if we can get, from a random position, the numbers 1, 2, 3, 4, 5 into their right places, the other numbers will fall into place automatically!

Now it is easy to get 1 into its right place: if it is not already there, move it to 12 by repeating the M move, and then get it to 1 by the I move. Furthermore, we can then get 2 to its right place by repeating the M move. When 1 and 2 are in their right places, consider the moves

X1=IM2IM5IM4=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)

and

X2=IMIM3IM2=(1)(2)(4,9)(3,11,10,5,8,7,12,6).

Clearly, if 3 is at the positions of 4, 5 or 10, we can get it to its right place by repeating X1. If it is in any other position except 9, we can get it back to its place by repeating X2. If it is at 9, we can use X2 to get it to 4, and then repeat X1 to get it to its right place.

With 1, 2 and 3 in place, consider the moves

Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,11,8,9)

and

Y2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11,10).

If 4 is at any of the positions 6, 7, 12, we can get it to its place by repeating Y1. If it is at 5, 8, 9, 10, 11, we can repeat Y1 until it gets to 8, then use Y2 to get it to 12, and then Y1 to get it to its place.

Finally, with 1, 2, 3, 4 in place, consider the moves

Z1=IM9IM7IM8IM7IMIM5=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)

and

Z2=IMIM3IM2(IM7IMIM5)2=(1)(2)(3)(4)(5,11,12,6)(7,9,10,8).

If 5 is at 7, 10 or 12, we can repeat Z1 to get it to its place. If 5 is at 6,8,9 or 11, repeat Z1until it gets to 6, and then apply Z2 to get 5 to its right place, and complete the solution of the puzzle.

View
1. 1. Douglas23 03:14 PM 8/5/08

Description of Y1 is not quite right. It cycles (5, 10, 8, 9) but does not move 11.
Description of Y2 is not quite right. It cycles (9, 11) but does not move 10.
If number 4 is in position 11, use Y2 to move it to position 9, then solve with Y1.

Reply | Report Abuse | Link to this
2. 2. Douglas23 03:33 PM 8/5/08

Here is another way to solve the M12 Puzzle.
Define three Custom Moves:
F = (im3im6im)^4
B = (im)^4 im2im8
Cycle = (imm)^4 imim5

Starting with the solved state 1 2 3 4 5...
F gives 1 2 4 3 5...(exchanging the Front two of the Triad 3, 4, & 5).
Then B-F-B gives 1 2 3 5 4... (exchanging the Back two of the Triad 3, 4, & 5).
Together these two moves can give all six arrangements for positions 3, 4, & 5.

To solve the Puzzle:
Place numbers 1 and 2 as described in the article.
Use "Cycle" until one of the numbers 3, 4, or 5 appears in position 5.
Use "B-F-B" to move it to position 4.
Use "Cycle" until another of the numbers 3, 4 or 5 appears in position 5.
Use "B-F-B" either once or twice so that both selected numbers are in positions 3 and 4.
Use "Cycle" until the remaining number of 3, 4, and 5 appears in position 5.
Now place the numbers 3, 4 and 5 in their correct sequence as follows:
If 5 is not yet in place, use "B-F-B" once or twice until it is in place.
If 3 & 4 are not yet in place, use "F" and the Puzzle is solved.

Reply | Report Abuse | Link to this
3. 3. Douglas23 06:17 PM 8/5/08

Here is another way to solve the M12 Puzzle using "Restricted Moves", each of which taken alone gives a visually pleasing and highly symmetrical result:

Define six custom moves as follows:
Z1 = mim10
Z2 = m2im9
Z3 = m3im8
Z8 = m8im3
Z9 = m9im2
Z10 = m10im

Define two more custom moves as follows:
Shift = Z3 I Z3 I Z10
Solve = Z9 Z10 I Z3 I Z3 Z8 I Z8

The first three moves, Z1, Z2, & Z3 all respect the "Triplets" (successive groups of three numbers). Z1 & Z2 exchange the Triplets in different ways, and Z3 rearranges the numbers within each Triplet.

Starting with 1 2 3 4 5 6... the sequence Z3 I gives 3 1 2 6 4 5...
Repeating Z3 I gives 2 3 1 5 6 4...
And repeating Z3 I once more restores 1 2 3 4 5 6...

The second three moves, Z8, Z9, & Z10 all respect the "Tetrads" (successive groups of four numbers). Z9 & Z10 rearrange the numbers within each Tetrad in different ways, and Z8 exchanges the Tetrads.

Starting with 1 2 3 4 5 6... the sequence Z8 I gives 9 10 11 12 4 3 2 1 8 7 6 5
Repeating Z8 I gives 8 7 6 5 12 11 10 9 1 2 3 4
And repeating Z8 I once more restores 1 2 3 4 5 6...

An interesting combination is Z8 I Z8 Z9 Z10 which gives 1 2 3 4 12 11 10 9 8 7 6 5

To solve the Puzzle, first get the numbers 1 through 6 (the "low numbers") all in the first six positions, then get them into the correct sequence. Use only the custom moves above, plus "I".

Starting from any random state, one of the Triplets will always have at least two low numbers. Move this to the first position with moves Z1 and Z2. If the second Tetrad does not contain any low numbers, use Z8 I Z8 and then it will.

Use Z3 I once or twice so that positions 1 & 2 are both low. Next goal is to get low numbers in positions 1, 2, & 3. If there is a low number in position 4, use Z10. If there is a low number in position 5 or 6, use Z3 I once or twice to move it to position 4, then use Z9 and Z10 as needed. If there is a low number in position 8, use Z10 to move it to position 7. If there is a low number in position 7, use Z3 I Z9 Z10 Z3 I Z3 I Z10.

Now be sure the second Tetrad still contains a low number. If not, use Z8 I Z8 and it will.

The next goal is to get low numbers in positions 1, 2, 3, & 4. If there is a low number in position 5 or 6, use Z3 I once or twice to move it to position 4. If there is a low number in position 7, use Z3 I to move it to position 8. If there is a low number in position 8, use Z9 Z3 I Z10 Z3 I.

Again be sure the second Tetrad still contains a low number. If not, use Z8 I Z8 and it will. Then use Z9 and Z10 to move that low number to position 5. Now positions 1, 2, 3, 4, and 5 are all low.

The remaining low number will be in position 6, 7, 8, 9, 10, or 11 (never 12). If it is in position 6, we are set. For position 7, 9, or 10 use "Shift" until it is in position 11. For position 11, use "Solve" twice, and all six low numbers will be on the left half of the puzzle. For position 8, use "solve" twice, then Z9 Z10 Z3 I Z3 I Z9, then use "solve" twice.

For the second half of the puzzle, we need to produce one triplet containing 1, 2, and 3. Typically two of these will be together in a triplet, and the third will need to be exchanged with one of the numbers in the other triplet. See which numbers need to be exchanged. Use Z3 I once or twice so these numbers are either together (in positions 3 & 4) or apart (in positions 1 & 6). If apart, use Z2 and they will be together. If together, use Z10 and the triplets will be defined (1, 2, & 3 in the same triplet).

If the numbers to be exchanged are in the same positions within their respective triplets (both first, both second, or both third in their own triplets), this technique will not work. If they are both second, use Z3 I. Then in any case use Z10, and the triplets can then be solved by using the previous paragraph on the new arrangement.

Once a triplet contains 1, 2, & 3 we are nearly done. Use Z3 I once or twice until the sequence is either 1, 2, 3 in order or 3, 2, 1 in order. If 3, 2, 1, use "Invert", then Z1.

If the puzzle is not yet solved, use Z2.

The End.

Reply | Report Abuse | Link to this
4. 4. eleven 08:17 AM 8/9/08

Seems, that my moves posted here
http://www.sudoku.com/boards/viewtopic.php?p=58484#58484
are shorter.

Reply | Report Abuse | Link to this
5. 5. math618 in reply to Douglas23 03:08 AM 8/19/08

Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,8,9)
Y2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11)

Reply | Report Abuse | Link to this
6. 6. math618 03:19 AM 8/19/08

Y1=IMIM3IM2IM9IM7IM8=(1)(2)(3)(4,7,6,12)(5,10,8,9)
Y2=IM3IM6IMIM9IM7IM8=(1)(2)(3)(4,7)(5,6)(8,12)(9,11).

Reply | Report Abuse | Link to this
7. 7. math618 08:48 PM 8/25/08

We can simplify Y1,Y2,Z1,Z2 like this Y1=IM3IMIM3IMIM2IM3,Y2=MIMIMIM4IM2IMIMIM6IM,Z1=M3IM2IM5IM,Z2=MIM3IM2IM3IM5I.

Reply | Report Abuse | Link to this
8. 8. jasonleeijk 05:17 PM 11/25/08

Z1=M3/M2/M5/M=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9).
Z2=M6/M3/M6/M4=(1)(2)(3)(4)(5,6,12,11)(7,8,10,9).

Reply | Report Abuse | Link to this
9. 9. Lou Piciullo 11:23 PM 12/31/08

An interesting coincidence: I first read this article this afternoon. This evening my wife and I chose, as our evening's entertainment, a rewatching of the movie 'Memento'. As I was viewing the film it occurred to me that the system which the director uses [ to convert the chronological sequence of events into the order in which they are shown in the film ] is, with a little tweaking, very much like the Merge move in the M12 puzzle.

Reply | Report Abuse | Link to this
10. 10. MATH 09:04 PM 6/2/10

Isn't it true that we can get all transformations with composite permutations

Reply | Report Abuse | Link to this
11. 11. MATH 09:07 PM 6/2/10

Isn't it true that we can get all transformations by compositing permutations

Reply | Report Abuse | Link to this
12. 12. MATH in reply to eleven 10:04 PM 6/2/10

WHERE

Reply | Report Abuse | Link to this
13. 13. MATH 04:10 AM 6/3/10

IMIM3IM2
IM2IM5IM4
IM3IM6IM
IM4IM2IM5
IM5IM8IM7
IM6IM9IM7
IM7IMIM5
IM8IM10IM6
IM9IM7IM8
IM10IM4IM7
are sequences which let (1,2)stay!
Keep trying!

Reply | Report Abuse | Link to this
14. 14. MATH 04:27 AM 6/3/10

IMIM3IM2
IM2IM5IM4
IM3IM6IM
IM4IM2IM5
IM5IM8IM7
IM6IM9IM7
IM7IMIM5
IM8IM10IM6
IM9IM7IM8
IM10IM4IM7
are sequences which let (1,2)stay!
Keep trying!

Reply | Report Abuse | Link to this
15. 15. MATH 07:17 AM 6/3/10

DEFINE:
X1=IMIM3IM2=(1)(2)(3,11,10.5,8,7,12,6)
X2=IM2IM5IM4=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
X3=IM3IM6IM=(1)(2)(3,11,7,6,4,9,10,8)(5,12)
X4=IM4IM2IM5=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X5=IM5IM8IM7=(1)(2)(7)(10)(3,6,4,9)(5,8,12,11)
X6=IM6IM9IM7=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X7=IM7IMIM5=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X8=IM8IM10IM6=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X9=IM9IM7IM8=(1)(2)(3,12,6,4,5,8,10,11)(7,9)
X10=IM10IM4IM7=(1)(2)(3,10,9,7,4,12,8,5)
then:
Y1=X1X9
Y2=X7X5
Y3=X9X7=Z1
a solution unfinished.

Reply | Report Abuse | Link to this
16. 16. MATH 11:26 PM 6/3/10

First of all, I want to apologize for two things:
(1)As my computer runs so slowly , I often thought of my comments as missed , consequently , I sent my comments twice sometimes .
(2)Yesterday, I called it "a new solution ." Actually, it's a more complete version of the original solution.
Then, I want to announce a new way to solve the M12 puzzle.
For the first thing :Define:
X2,1=IMIM3IM2=(1,3,2)=(1)(2)(3,11,105,8,7,12,6)
X2,2=IM2IM5IM4=(2,5,4)=(1)(2)(8)(9)(3,10,4,5)(6,7,11,12)
X2,3=IM3IM6IM=(3,6,1)=(1)(2)(3,11,7,6,4,9,10,8)(5,12)
X2,4=IM4IM2IM5=(4,2,5)=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X2,5=IM5IM8IM7=(5,8,7)=(1)(2)(7)(10)(3,6,4,9)(5,8,12,11)
X2,6=IM6IM9IM7=(6,9,7)=(1)(2)(11)(12)(3,4,7,8)(5,6,9,10)
X2,7=IM7IMIM5=(7,1,5)=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X2,8=IM8IM10IM6=(8,10,6)=(1)(2)(3,9,5,4,8,10,11,12)(6,7)
X2,9=IM9IM7IM8=(9,7,8)=(1)(2)(3,12,6,4,5,8,10,11)(7,9)
X2,10=IM10IM4IM7=(10,4,7)=(1)(2)(3,10,9,7,4,12,8,5)
X3,1=(1,3,7)=(1)(3)(4)(6)(2,10,11,12)(5,7,8,9)
X3,2=(3,6,6)=(1)(3)(4)(2,10,7)(5,8,6)(9,12,11)
X3,3=(4,2,9)=(1)(3)(2,8,10,6,1)(4,5,12,9,7)
X3,4=(5,8,2)=(1)(3)(2,6,9,11,4,7,8,10)(5,12)
X3,5=(7,1,3)=(1)(3)(10)(12)(2,7,8,9)(4,5,6,11)
X3,6=(8,10,4)=X3,5
X3,7=(9,7,10)=(1)(3)(2,5,6,12,4,8,11,9)(7,10)
X3,8=(10,2,3)=(1)(3)(2,11,5,4,6,9,10,12)(7,8)
,and xa,b means 1 and a stay
Y1=X2,1X2,9=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
Y2=X2,7X2,5=(1)(2)(3)(11)(4,12,6,7)(5,9,8,10)
Y3=X2,9X2,7=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
Y4=X3,1X3,4=(1)(2)(3)(4,7,10)(5,8,11)(6,9,12)
Y5=X3,2X3,4=(1)(2)(3)(11)(4,7,6,12)(5,10,8,9)
Y6=X3,5X3,2=(1)(2)(3)(5)(4,8,12,11)(6,9,10,7)
Y7=X3,4X3,7X3,1=(1)(2)(3)(8)(4,11,9,5)(6,10,7,12)
Y8=X3,4X3,7X3,8=(1)(2)(3)(8)(4,12,9,10)(5,6,11,7)
Z1=Y3
Z2=Y7Y6=(1)(2)(3)(4)(5,8,12,9)(6,7,11,10)
Z3=Y8Y5=(1)(2)(3)(4)(5,12)(6,11)(7,10)(8,9)
Z4=Y4Y2=(1)(2)(3)(4)(5,10,12,7)(6,8,11,9)
It's a advanced version of the original solution.
Then it will be very helpful to me to figure out a combination of I,M that composes (1,2,3,4,5,6,7,8,9,10,11,12).
Thank you!

Reply | Report Abuse | Link to this
17. 17. MATH 02:34 AM 6/5/10

I found that (1,2,3,4,5,6,7,8,9,10,11,12) is equevalent with
M10(1,3,5,7,9,11,12,10,8,6,4,2)M.
But i can only get(1,3,5,7,8,6,4,2)(9,10,11,12).

Reply | Report Abuse | Link to this

### Add a Comment

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Click one of the buttons below to register using an existing Social Account.

## More from Scientific American

• AccuWeather | 6 hours ago | 1

### Large 200 MPH Tornado Hits Suburb of Oklahoma City

• Guest Blog | 7 hours ago

### Angelina Jolie and the One Percent

• Molecules to Medicine | 13 hours ago

### The s**t hits the fan - FDA, INDs, and fecal microbiota transplants

• Observations | 13 hours ago

### See Mercury, Venus and Jupiter in Tightest Night Sky Cluster until 2026

• News | 13 hours ago

### Drought Gobbles Up Texas Turkey Hunt

See what we're tweeting about

More »

## Latest from SA Blog Network

• ### #SciAmBlogs Monday - eating healthfully, DSM-5, polyploidy, fecal transplants, non-identical twins, and more.

STAFF
The Network Central | 5 hours ago
• ### Angelina Jolie and the One Percent

Guest Blog | 7 hours ago
• ### A Beautiful Fungus Graveyard

Oscillator | 10 hours ago
• ### Self-Publishing Tools for Science Artists

Symbiartic | 10 hours ago
• ### The s**t hits the fan - FDA, INDs, and fecal microbiota transplants

Molecules to Medicine | 13 hours ago

## Science Jobs of the Week

The cycle notation and M12

X

### Subscribe Today

Save 66% off the cover price and get a free gift!

X

X

###### Welcome, . Do you have an existing ScientificAmerican.com account?

Yes, please link my existing account with for quick, secure access.

No, I would like to create a new account with my profile information.

X

Are you sure?

X

### Institutional Access

It has been identified that the institution you are trying to access this article from has institutional site license access to Scientific American on nature.com. To access this article in its entirety through site license access, click below.

X

X