Message #1847

From: Melinda Green <>
Subject: Re: [MC4D] State graph of MC2D
Date: Thu, 04 Aug 2011 19:08:53 -0700

On 8/4/2011 3:02 PM, David Vanderschel wrote:
> 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.

I most deeply apologize. I should definitely said "I’m guessing that you
looked at my diagram…" That seems like a small qualification, but it
is not at all. You are right to call me on it and I appreciate the risk
you took in doing that. My pennance will be to try to read this message
all the more carefully as you suggest.

> One of the first things I wrote was:
> As I (fail to) recall, Melinda never made it very clear
> about what were her criteria for the particular
> partitioning of the 24 permutations she chose for her
> "states". I never understood what technical meaning she
> was ascribing to "complete" or why she used the definite
> article on "the complete graph". There are many ways to
> partition the 24 elements of S4. Nan’s graphs certainly
> would seem to me to be closer to what I would call
> "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
> cannot get from any member of either of the last two
> states to one of the first 3 with one twist. Similarly
> for 0 -> 2. But I cannot turn this observation into a
> 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
> determines the partitioning. I suggested, "…
> If it is not clear what I am concerned with, check out
> or
> Partitions of a set and equivalence relations on the set
> are equivalent concepts. I see the partitioning. I am
> trying to figure out a nice way to state the
> corresponding equivalence relation. I am also biased to
> try to find such a description in terms of the
> permutations themselves and not in terms of manipulating
> an abstract physical model in 2-space or 3-space. (As
> we have already experienced, the latter type of
> description is difficult to make precise in a
> 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".

I understand and believe you. When I said that I felt we were talking
past each other, I meant that I felt that we had each found something
interesting that we wanted to explain but were not succeeding very well,
and to nobody’s fault.

>> 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.

I stand corrected.

> It is mathematically
> sound and elegantly simple. And, as it turns out,
> conjugating is the way it’s done.

I don’t know if it is correct to say it is THE way it’s done. It
certainly is A way, and possibly even the BEST way. This point was one
of the things that I was trying to get across. I’m sure that from your
point of view it is definitely the right way. I’m just pointing out that
there are other ways of looking at it. That was why I harped on the
question of purpose or utility.

> 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.

Nope. I never thought that anything you have ever said was irrelevant. I
was just not convinced that you had accurately translated my thoughts
into more formal language.

> 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
> 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
> accomplishing anything that you had not already
> accomplished. His treatment struck me as being more an
> exploration of S4 than as offering insight into the
> puzzle. That is why I went on to make the point that S4
> is a rather well understood subject.
> The other thing I had in mind is that your graph is not
> an effective aid for solving the puzzle. I acknowledge
> that it has relevance in an academic sense; but, from
> the practical point of view, it is most definitely not
> practical. I will stand by that. The puzzle is so very
> easy to solve directly, that one can solve it in far
> less time than it takes to figure out which node of the
> graph a given permutation corresponds to, let alone
> figuring out which permutation in the next node on the
> solution path is one you can reach from your current
> state.
> For the purpose of actually solving the puzzle, I offered:
> Whenever any cubie is diagonally displaced, then, to get
> a shortest solution, you must immediately do a twist
> that moves at least one such diagonally displaced cubie.
> For such a diagonally displaced cubie, there are two
> slices you can twist. If twisting one of them will
> place the other cubie in it, twist that slice. If
> twisting one of them will displace the other cubie from
> its home position and twisting the other slice won’t do
> that, twist the other. When no cubie is diagonally
> 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.

That statement is not at all convincing to me. I’m sure that it works
for you, and possibly for mathematicians who think symbolically, but
half of the world consists of visual thinkers like me for whom a diagram
is often more convincing.

Further, the subject of diagonals seems to only apply to a small class
of puzzles whereas I am looking for the unifying graph-theoretic
features that may apply to all twisty puzzles.

> (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.)

They feel roughly similar in complexity to me. It is actually a pretty
good comparison because when I mapped out the complete game at a
similarly young age I considered all starting corner moves to be
identical in the same way that I enumerate the 8 types of states of MC2D.

My friends and I used to like to play tic-tac-toe in our heads by
mapping squares to the corresponding telephone number pad positions, and
I could only do that by thinking visually. I can’t even imagine how to
do that otherwise.

> 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.

I knew that. I was just saying that I felt you thought that there was a
better practical choice that I could have made. The word "wrong" sums
that up but carries too much negative baggage for that purpose.

> 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
> must be 3 …"
> What I see is that it takes 4 twists to get from node 2 to
> node 0.

It’s true and clear when you allow middle slices, but clearly I
disproved myself about as completely as possible. Thanks for the correction.

> 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.

Yes, well I suggest that you not take a lack of discussion on your main
point for a lack of interest. I know that there are a lot of very
interested people reading this list who have no intention of ever
posting. Maybe you can generate interest eventually, but you may need to
continue to find ways of clarifying your thoughts even further. That
along with some pretty diagrams may just do the trick! :-)