Message #553

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] MC2D. Was: Something interesting and strange about permutations
Date: Wed, 13 Aug 2008 23:46:12 -0700

David,

Do attachments work in Yahoo group messages now? I don’t remember but
I’m going to try to attach a version of my graph that I just made which
should clarify what I’m trying to say about states. It uses the same
layout as my ASCII graph but includes small pictures of each state. The
lines indicate the simple edge twists. The dotted lines between
horizontally adjacent states in the original version indicated states
that could be reached via a single middle slice twist if the applet
supported that. It is easy to see that in the first row. It takes a
little more work to see that in the other rows because you need to
figure out whether it requires the horizontal or vertical middle slice
and then account for positional and color symmetries. What I mean by
color symmetry is that you should be able to rename any of the colors at
any time without changing the state. It’s all about the particular
patterns of each state that matter and there appear to be exactly 8
unique ones.

We can call this the graph-theoretic approach as opposed to your
group-theoretic approach. Perhaps one can arrive at some of the same
conclusions either way such as that the diameter of the graph is 4
(because it takes a minimum of 4 twists to solve the puzzle starting
from the checkerboard state #2). Both approaches are probably useful for
different purposes. The thing I like best about the graph is that it
makes you wonder which features of it should carry over to the larger
puzzles and what the implications of those features would be if they
could be proved. For example, might all such twisty puzzles contain
something like state #5 that acts like a sort of nexus? I would really
love to see equivalent state diagrams for other, slightly larger puzzles
such as the 3x4 and 4x4. In 3D, the Pyraminx and the 2^3 might be good
"medium" sized candidates but would certainly require computer-assisted
graph layout tools to diagram well.

-Melinda

David Vanderschel wrote:
> 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:
>
> 0. Two disjoint adjacent corner pairs swapped. 2 such. even.
>
> 1. The identity. 1 such. even.
>
> 2. Both diagonal corner pairs swapped. 1 such. even.
>
> 3. One pair of adjacent corners swapped. 4 such. odd.
>
> 4. One pair of diagonal corners swapped. 2 such. odd.
>
> 5. One stationary corner and a 3-cycle. 8 such. even.
>
> 6. A 4-cycle with moves only to adjacent corners. 2 such. odd.
>
> 7. 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.