The M_{12} group is generated by the permutations
- M (“merge”) = (1 12 2 11 3 10 4 9 5 8 6 7)
- I (“invert”) = (12 11 10 9 8 7 6 5 4 3 2 1)
In Scientific American, Kriz and Siegel discuss several games based on sporadic simple groups, including this one based on M_{12}.
The puzzle is to start with a “random” configuration and find a sequence that takes it to O.
The size of the group is 12 x 11 x 10 x 9 x 8. This is the number of ways to put five numbers into 12 positions. Given the positions of five numbers (e.g. 1 through 5), there is only one configuration reachable from O with those numbers in those positions. That is, only one group element takes those five elements to those positions from O. As a corollary, aside from E, no group element leaves more than four numbers undisturbed. This explains the quotation marks around “random” above: you can’t start with a random permutation of the digits 1 through 12, because few such permutations can be reached from O. Instead you have to start with O scrambled by some (unknown) sequence of M and I.
The lack of group elements that leave most numbers undisturbed means you can’t use a technique analogous to what’s used to finish solving Rubik’s Cube, where one uses sequences that e.g. permute three corner cubies or reorient two corner cubies without disturbing the rest of the cube. On the other hand, the fact that only five numbers have to be placed to reach a given configuration in all twelve positions means you don’t need to. Instead you can do something like what’s done early in a Rubik’s Cube solution, when one puts e.g. all the cubies of one layer in their proper places and orientations without concerning oneself with the other two layers. This involves using sequences that leave n cubies undisturbed to place and orient one more cubie. Likewise, in this puzzle, we can use sequences that leave the first n positions undisturbed to place the correct number into the n+1 position. We’ll call such a sequence an n-invariant sequence.
I is a 0-invariant sequence. Obviously I^{2} = E (that is, I is its own inverse). M is 1-invariant, as is M^{n} for n<11:
n | M^{n} |
1 | (1 12 2 11 3 10 4 9 5 8 6 7) |
2 | (1 7 12 6 2 8 11 5 3 9 10 4) |
3 | (1 4 7 10 12 9 6 3 2 5 8 11) |
4 | (1 11 4 8 7 5 10 2 12 3 9 6) |
5 | (1 6 11 9 4 3 8 12 7 2 5 10) |
6 | (1 10 6 5 11 2 9 7 4 12 3 8) |
7 | (1 8 10 3 6 12 5 4 11 7 2 9) |
8 | (1 9 8 2 10 7 3 11 6 4 12 5) |
9 | (1 5 9 12 8 4 2 6 10 11 7 3) |
10 | (1 3 5 7 9 11 12 10 8 6 4 2) |
11 | (1 2 3 4 5 6 7 8 9 10 11 12) |
So M^{11} = E (that is, M^{10} = M^{-1}). For every 3 <= n <= 12 there is a power of M that puts the number in position n into position 2 while leaving position 1 unchanged. So powers of M provide a complete set of 1-invariants. Furthermore there is another sequence that puts the number in position n into position 12. So we can begin our solution as follows:
- If 1 is not in 1, then do M repeatedly until 1 is in 12, then do I. Now 1 is in 1.
- If 2 is not in 2, then do M repeatedly until it is.
We can also make a 2-invariant by scrambling O with some sequence of M and I, then using the above prescription. For example, IMI takes O to (6 7 5 8 4 9 3 10 2 11 1 12); then doing three more M takes it to (6 8 3 11 12 2 9 5 7 4 10 1); I puts 1 into 1 and M^{2} puts 2 into 2: IMIM^{3}IM^{2} = (1 2 6 9 10 12 8 5 4 11 3 7). At this point let’s introduce some more convenient notation: since I is self inverse it occurs only once between powers of M, so we can represent M^{n}IM^{p}IM^{q}I…IM^{r} by the digit string npq…r (using 0 to represent the power 10); then our above 2-invariant is I132 Or better yet, i132 since i is harder to confuse with 1 than I is.
It would be nice if i132^{n} gave us a complete set of 2-invariants, with each of the numbers from 4 to 12 in position 3, but it doesn’t: (i132)^{8} = E, and we get 2-invariants for 5, 6, 7, 8, 10, 11, and 12, but not 4 or 9. But we can use the same strategy with other initial scramblings to come up with another 2-invariant, and even if none of its powers gives a 2-invariant for 4 or 9, then perhaps some product of powers of both 2-invariants will.
Note that these will not be the shortest possible 2-invariants by any means, but this is an easy method for finding invariants without exhaustive searching.
Having found a complete set of 2-invariants we can now put 3 from position n into position 3 using the 2-invariant with n in the third position.
Now it’s just a matter of more of the same: We can find a couple of 3-invariants (by starting with a scrambling sequence followed by moves that put 1, 2, and 3 into 1, 2, and 3), use products of powers of those 3-invariants to come up with a complete set of 3-invariants, and use the appropriate one of them to put 4 into 4. Finally make a complete set of 4-invariants and use one to put 5 into 5. At the same time 6 through 12 fall into 6 through 12 and we’re done.
By the time we get to the 4-invariants this prescription leads to some pretty long sequences. When I first worked this out one of my basis 4-invariants was something like 444 moves long, and then one had to use powers of that to make other 4-invariants. It’s nice to be able to come up with a solution not using a computer (other than using the sciam.com Flash widget to perform the permutations), but it won’t be a very efficient solution.
I wrote a Perl script to search for invariants based on digit strings up to 5 digits long (optionally preceded and/or followed by i). These are not necessarily the shortest possible sequences but they’re presumably close:
Permutation | Sequence |
2-invariants: | |
1 2 4 12 3 6 8 10 9 11 7 5 | 1143i |
1 2 5 3 9 8 6 12 4 10 11 7 | 1136 |
1 2 6 9 10 12 8 5 4 11 3 7 | i132 |
1 2 7 3 6 12 10 5 9 4 11 8 | i2123i |
1 2 8 6 12 7 11 10 4 9 3 5 | i361 |
1 2 9 3 6 7 11 4 8 10 5 12 | 22111 |
1 2 10 3 12 7 6 9 11 5 4 8 | i3214 |
1 2 11 9 3 6 7 5 12 4 8 10 | i3122i |
1 2 12 5 8 4 9 10 7 11 3 6 | 342i |
3-invariants: | |
1 2 3 5 9 12 10 8 11 6 4 7 | i41347 |
1 2 3 6 7 11 9 10 5 12 4 8 | 63361i |
1 2 3 7 12 4 9 8 6 5 10 11 | 46223 |
1 2 3 8 6 10 11 9 4 5 12 7 | 3135 |
1 2 3 9 8 6 5 10 11 7 12 4 | 12112 |
1 2 3 10 12 9 5 7 4 6 11 8 | i12342 |
1 2 3 11 12 5 6 10 9 4 8 7 | 43151i |
1 2 3 12 8 5 7 9 6 11 4 10 | 1354i |
4-invariants: | |
1 2 3 4 6 12 8 10 7 9 5 11 | 13235i |
1 2 3 4 7 9 12 6 11 5 8 10 | 3251 |
1 2 3 4 8 7 11 12 5 6 10 9 | 16381 |
1 2 3 4 9 10 6 5 12 11 7 8 | 28320 |
1 2 3 4 10 8 5 11 6 12 9 7 | 0426 |
1 2 3 4 11 5 9 7 10 8 12 6 | 6364 |
1 2 3 4 12 11 10 9 8 7 6 5 | i8111i |
Using these one should be able to:
— place 1 in no more than 11 moves
— place 2 in no more than 10 moves
— place 3 in no more than 11 moves
— place 4 in no more than 20 moves
— place 5 in no more than 25 moves
giving 77 moves as the maximum required. This is then an upper limit on the number of moves required by God’s algorithm.
How about a lower limit?
In 0 moves one has 1 group element (E).
In 1 move, 2 (M, I). Total: 3.
In 2 moves, 3 (MM, MI, IM). Total: 6.
In 3 moves, 5 (MMM, MMI, MIM, IMM, IMI). Total: 11.
In 4 moves, 8 (MMMM, MMMI, MMIM, MIMM, MIMI, IMMM, IMMI, IMIM). Total: 19.
Generally, in n moves, the number of group elements is the number of n bit binary numbers in which 0 does not appear in two consecutive positions and 1 does not appear in 11 consecutive positions. Ignoring the second of these restrictions, an n-1 bit number ending in 0 gives rise to one n bit number (append a 1) while one ending in 1 gives rise to two n bit numbers (append a 0 or 1). If the number of even (odd) (any) n bit numbers is E(n) (O(n)) (T(n)) then
- E(n) = O(n-1)
- O(n) = E(n-1) + O(n-1) = T(n-1)
so
- T(n) = O(n-1) + T(n-1) = T(n-2) + T(n-1)
and T(0) = 1, T(1) = 2; i.e. the number of n bit numbers is the n+2th Fibonacci number F(n). The number of n-or-fewer bit numbers is the sum of the first n+2 Fibonacci numbers minus 1, which is F(n+4)-2. This is an upper limit on the number of group elements we can reach in n moves.
Now, the size of M_{12} is 12 x 11 x 10 x 9 x 8 = 95,040. The 25th and 26th Fibonacci numbers are 75025 and 121393. So in 21 moves one cannot reach all the members of M_{12}; in 22 moves one might be able to. Conclusion: a lower limit on the number of moves required in the worst case by God’s algorithm is 22 moves. Rather a big gap from the lower limit to the upper…
Addendum 1:
About a month after writing the above, I received an email from Robert H. Douglass who said he’d done a computer search to show the “normalized positions” (ones with 1 and 2 in positions 1 and 2) can be solved in 28 moves in the worst case. He conjectured that this was the upper limit for all positions.
Addendum 2:
Actually it’s not hard to write a Perl script to generate all possible move sequences, in order of increasing length, and tabulate the resulting permutations until all 12 x 11 x 10 x 9 x 8 are found. At least I didn’t find it hard — assuming I did it without errors. Nor does it take more than a few seconds to run. Almost all positions are solved in 28 moves or fewer, but I find 12 configurations that I claim require 29 moves to solve:
4 9 5 7 11 2 8 12 1 3 10 6
8 12 1 3 10 6 4 9 5 7 11 2
10 3 2 4 1 12 5 9 6 8 11 7
2 5 10 12 7 4 3 8 11 9 6 1
10 2 5 4 12 7 11 3 8 1 9 6
9 1 6 3 11 8 12 4 7 2 10 5
1 6 9 11 8 3 4 7 12 10 5 2
7 11 8 6 9 5 12 1 4 2 3 10
12 8 4 2 6 10 1 5 9 11 7 3
8 3 7 6 9 5 10 1 2 4 11 12
1 5 9 11 7 3 12 8 4 2 6 10
5 10 6 7 4 8 3 12 11 9 2 1