ADVERTISEMENT

The cycle notation and M12

More In This Article

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.

Share this Article:

Comments

You must sign in or register as a ScientificAmerican.com member to submit a comment.
Scientific American Back To School

Back to School Sale!

12 Digital Issues + 4 Years of Archive Access just $19.99

Order Now >

X

Email this Article

X