Message #1846
From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] State graph of MC2D
Date: Thu, 04 Aug 2011 17:02:28 -0500
Melinda wrote:
> You looked at my diagram and thought that what I was
> attempting had something to do with cycles and conjugates
> but was just doing it wrong.
Melinda, you are making assumptions about what I was
thinking that are not only false, but are contrary to what I
actually wrote. I hope that, after reading this, you will
apologize for the above inappropriate accusation. I hope
you will read this post carefully, because it appears that
you have failed to do so with my previous posts.
One of the first things I wrote was:
As I (fail to) recall, Melinda never made it very clear<br>
about what were her criteria for the particular<br>
partitioning of the 24 permutations she chose for her<br>
"states". I never understood what technical meaning she<br>
was ascribing to "complete" or why she used the definite<br>
article on "the complete graph". There are many ways to<br>
partition the 24 elements of S4. Nan's graphs certainly<br>
would seem to me to be closer to what I would call<br>
"complete" in this context.
As you can see, I made it clear that I was trying to
understand how you arrived at your particular partitioning.
I raised the issue of conjugacy classes because I understand
them and they seemed close to your partition. I never said
that what you were doing was "wrong" - just that I did not
understand it. And I wanted to understand it. I finally
did after Andrew Gould’s post.
I was not ignoring the value of your graph either. In that
first post, I had mentioned:
Melinda's graph accurately depicts the fact that you<br>
cannot get from any member of either of the last two<br>
states to one of the first 3 with one twist. Similarly<br>
for 0 -> 2. But I cannot turn this observation into a<br>
clue for the partitioning.
So I was acknowledging the fact that your graph puts limits
on the minimum number of twists required to solve. I did
understand that, and I would not discount its interest as an
academic issue. And note, in the above, that I was still
harping on the fact that I did not understand the rule for
your partition.
More recently I wrote:
What I am trying to get hold of is the relation which<br>
determines the partitioning. I suggested, "...
If it is not clear what I am concerned with, check out<br>
http://en.wikipedia.org/wiki/Partition_of_a_set#Partitions_and_equivalence_relations<br>
or http://preview.tinyurl.com/3u6tzeh<br>
Partitions of a set and equivalence relations on the set<br>
are equivalent concepts. I see the partitioning. I am<br>
trying to figure out a nice way to state the<br>
corresponding equivalence relation. I am also biased to<br>
try to find such a description in terms of the<br>
permutations themselves and not in terms of manipulating<br>
an abstract physical model in 2-space or 3-space. (As<br>
we have already experienced, the latter type of<br>
description is difficult to make precise in a<br>
mathematical sense.)
I was concerned that maybe you were still confused about
what I was actually concerned with, so I went into even more
detail. Alas, that apparently still did not help. It
should be very clear that, at no point, did I ever claim
that what you had done was "wrong".
> Different problems indeed. I don’t know the precise
> mathematical language to express my diagram in your terms
> but it looks like you and Nan are doing a good job of
> that.
Actually, no. It was Andrew Gould who straightened this
out, providing a way to specify the equivalence relation
that gives rise to your partition. It is mathematically
sound and elegantly simple. And, as it turns out,
conjugating is the way it’s done. It’s just that you cannot
conjugate with _any_ permutation of S4 - only those that
arise from symmetries. Thus the fact that I started talking
about conjugation early on was not irrelevant, as you seem
to imply. Nan had left me confused by omitting the
possibility of conjugating with a reflection.
Now there certainly is a sense in which I have expressed a
negative attitude about the graph. Indeed, my very first
comment in this thread was:
I think maybe a little too much is being made of this<br>
state graph business for the 2D puzzle.
There were a couple things I had in mind when I made that
remark:
One was that Nan's elaboration of it was not<br>
accomplishing anything that you had not already<br>
accomplished. His treatment struck me as being more an<br>
exploration of S4 than as offering insight into the<br>
puzzle. That is why I went on to make the point that S4<br>
is a rather well understood subject.
The other thing I had in mind is that your graph is not<br>
an effective aid for solving the puzzle. I acknowledge<br>
that it has relevance in an academic sense; but, from<br>
the practical point of view, it is most definitely not<br>
practical. I will stand by that. The puzzle is so very<br>
easy to solve directly, that one can solve it in far<br>
less time than it takes to figure out which node of the<br>
graph a given permutation corresponds to, let alone<br>
figuring out which permutation in the next node on the<br>
solution path is one you can reach from your current<br>
state.
For the purpose of actually solving the puzzle, I offered:
Whenever any cubie is diagonally displaced, then, to get<br>
a shortest solution, you must immediately do a twist<br>
that moves at least one such diagonally displaced cubie.<br>
For such a diagonally displaced cubie, there are two<br>
slices you can twist. If twisting one of them will<br>
place the other cubie in it, twist that slice. If<br>
twisting one of them will displace the other cubie from<br>
its home position and twisting the other slice won't do<br>
that, twist the other. When no cubie is diagonally<br>
displaced, the solution is obvious.
Not only is that much easier to grok than your graph, a few
more lines of reasoning will prove that it always leads to a
solution in 4 or fewer twists. (In constructing that
argument, I see that I failed to mention one (fairly
obvious) rule: If there is a slice in which both cubies are
diagonally displaced, twist that one. That rule comes
before the other which-slice-to-twist rules.) Actually, I
was somewhat embarrassed to be belaboring what seems rather
obvious to me. (My friends and I mastered tic-tac-toe when
we were in the first grade, and that problem strikes me as
being more difficult than solving MC2D.)
But, again, my criticism was not that anything was "wrong".
I was just criticizing the graph’s value from a practical
point of view when it comes to actually working the puzzle.
Now there is one rather odd thing you stated in your last
post that is indeed profoundly wrong:
"With my diagram it is trivial to see that God's number<br>
must be 3 ..."
What I see is that it takes 4 twists to get from node 2 to
node 0.
One thing that is frustrating me about this diversion is
that I thought I had made a real contribution with the Cycle
Length Signature approach to a succinct but useful way to
classify the permutation state for any sort of cubie in any
generalization these puzzles. That approach is closely
related, as the CLS characterizes the conjugacy class of an
arrangement. The difference is that these conjugates are
not limited to conjugation by a symmetry. As it turns out,
that makes it much easier to identify the CLS class of an
arrangement; and it leads to a state graph with far fewer
nodes, which could be viewed as an advantage. Furthermore,
the insights from the CLS do have real practical
significance which can be readily applied when solving. I
thought folks would be excited about this.
Regards,
David V.