Message #552

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: MC2D. Was: Something interesting and strange about permutations
Date: Wed, 13 Aug 2008 18:47:04 -0500

On Tuesday, August 12, "Melinda Green" <melinda@superliminal.com> wrote:
>I arrived at the conclusion that MC2D contains
>exactly 8 states by simply recording every sticker
>pattern that I was able to produce using the puzzle,
>ignoring all duplicates due to color or positional
>symmetries. I’m pretty sure there are only 8 of them.

Melinda, I am sorry; but I am still very unsure about
what you mean by a "state". Since the 4 face 2-cubies
exist, they give the puzzle a fixable orientation that
does not admit positional symmetries. Their presence
also makes it difficult for me to see how there could
be color symmetries as well. (They also prevent
mirror symmetries.) I thought, "Maybe she’s talking
about the 2x2 version of the 2D puzzle." Then you can
remove a rotational symmetry - leaving 6 possible
permutations. But that’s not "8" either. In this
2x2 case, you can also remove a mirror symmetry, thus
leaving only 3 ‘states’.

>I gave each of them a number and then mapped out all
>the possible transitions between the those states to
>produce the complete graph for the puzzle. Perhaps
>there are 24 states if you don’t mind duplicates, but
>since arriving at one state gives exactly the same
>options as arriving at symmetrical twins, it seems
>best to collapse all duplicates into the same logical
>state and leave only a graph containing all the truly
>unique states. I attempted to include an ASCII
>diagram in the post that you replied to
>(http://games.groups.yahoo.com/group/4D_Cubing/message/329)
>but unfortunately Yahoo stripped out my spacing
>characters and left a bit of a mess. I should
>probably sketch it up again in Visio or other
>diagraming tool for clarity.

I am struggling to discover your 8 ‘states’. I have
found a way of classifying the permutations into 8
classes with the following descriptions of a member of
each class:

Two disjoint adjacent corner pairs swapped. 2 such. even.
The identity. 1 such. even.
Both diagonal corner pairs swapped. 1 such. even.
One pair of adjacent corners swapped. 4 such. odd.
One pair of diagonal corners swapped. 2 such. odd.
One stationary corner and a 3-cycle. 8 such. even.
A 4-cycle with moves only to adjacent corners. 2 such. odd.
A 4-cycle with diagonal moves. 4 such. odd.

(For the counts: 1: horizontal or vertical swaps. 3:
which side. 4: which diagonal. 5: which corner is
stationary and the direction of the rotation for the
3-cycle. 6: which direction. 7: six total possible
4-cycles minus the 2 circular-order-preserving ones.)

The counts do add up to 24.

So I found 8 possibly relevant somethings. However, I
don’t see how to talk about transitions between
classes in a very useful way. I have trouble thinking
of the classes of permutations as "states". I
certainly do not view two members of the same class as
"duplicates". In terms of the resulting new class,
the effect of a twist on a member of a class depends
on which member of the class was picked. There is no
nice equivalence that allows the classes to play as
elements of a group.

For any pair of the above classes, you can talk about
whether, given a specific first permutation from one
class, there exists a second permutation belonging to
the other class and a twist that will transform the
first into the second. Clearly no such permutation
and twist exist if both classes have permutations of
the same parity. The types of transitions for which
the possibility exists include 1-3, 0-3, 3-5, 2-7,
4-5, 5-6, and 5-7. Not possible: 2-4, 1-7, 1-8. Etc.

I think that what is described above is somewhat like
your own graph, for which I have a copy of your
original:

0 . . 1 . . 2
\ / \ /
\ / \ /
3 . . 4
\ /
\ /
5
/ / 6 . . 7

(I recommend viewing with a fixed width font.)

I think I may even have managed to make my numbering
system match whatever you were doing. However, I
don’t see the "1 . . 2", "3 . . 4", "6 . . 7", or
"4 / / 2" relations. Indeed, to get from 1 to 2
without center slice twists, I have to go via 7. My
version of the graph would look like this:

0 1
\ / \ / 3 4
\ /
\ /
5
/ / 6 7
 2

Note that permitting center slice twists does also
enable 0-1, 0-2, 3-3, 5-5, 6-6, and 7-7. (I am
assuming that flipping two opposing slices at the same
time is equivalent to a center slice twist.) But it
also enables strange transitions like 4-6 and 3-7, so
this does not seem like a very interesting angle to
pursue. It would certainly make the graph look messy.

Assuming that I have managed to get close to what you
were talking about, I must say that I still don’t "get
it". What is the important insight which results from
this way of classifying the permutations? We seem to
have derived something complicated from a relatively
simple situation. The complications will only get
worse if we try to generalize the approach to a higher
dimensional puzzle. I do not feel enlightened, so I
must still be missing something. The analysis does
prove that no two permutations are more than 4 twists
apart; but, with only 24 permutations to start from,
that would not have been difficult to prove without
doing the classifications. And, again, extending this
‘diameter’ argument to higher dimensions does not look
to me like it would be tractable.

Regards,
David V.