# Message #2129

From: Melinda Green <melinda@superliminal.com>

Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)

Date: Wed, 09 May 2012 22:08:38 -0700

David,

I’m sorry that I have exasperated you. I really don’t mean to argue

anything and I believe that I get what you are saying. I think the

tension is due to the fact that each of us is interested in related but

different concepts here. In the 2D case you see 24 distinct states in a

way that is both mathematically clean, meaningful and interesting to

you. I on the other hand see only 8 states that are interesting to me,

however messy they may be to count.

Regarding recolorings, please don’t think that I care about the

particular colors. I only care about the patterns that they create.

Perhaps we can clear this up by talking about those color pairs that are

important to you. Imagine a pristine cube. If you swap two opposite sets

of stickers, then you feel that nothing has changed even though you

can’t rotate the whole cube to match the original colors. (Perhaps you

mean to allow only an even number of pair swaps.) For the things that I

care about, definitely nothing has changed when you do that because the

puzzle is still in what I consider to be *the* solved state which I

define as the one in which all sides have a single different color. For

that matter I am also perfectly happy swapping the stickers of two

adjacent faces because that gives the same result as when swapping

opposite sides. The puzzle remains solved.

Unless I’ve just said something whacky, I think we can leave it at that.

At least I hope so!

-Melinda

On 5/9/2012 9:11 PM, David Vanderschel wrote:

> Melinda wrote:

>> On 5/7/2012 6:34 PM, David Vanderschel wrote:

>>> Melinda wrote:

>>>> It sounds like we are getting closer to closure.

>>>>> Does this mean that you now understand why you must

>>>>> maintain the pairs of opposing colors when reassigning

>>>>> sticker colors? With all my effort at trying to explain

>>>>> it for you, I was hoping for an "I see now!" I was also

>>>>> hoping that you would realize that it is easier to talk

>>>>> about conjugation by a symmetry than to get involved in

>>>>> talking about remapping sticker colors, which are

>>>>> actually somewhat tangential to the real problem.

>> I’m not sure that I feel much closer to that "ah ha" moment

>> but I do feel as if we are converging on a story that will

>> feel right for all of us.

> Unfortunately, I can tell from your later questions that you

> have yet to get it.

>

>> If conjugation is the operation that allows us to compose

>> all the symmetries into one state space, then it does feel

>> like a useful way to describe what we are doing.

> I don’t think there is any "if" to it. However, I am not

> sure that I can interpret your "compose all the symmetries

> into one state space" meaningfully. In particular, we are

> not composing symmetries. Without reducing to the

> equivalence classes of states related by conjugation by a

> symmetry, we have a perfectly meaningful state space; and I

> don’t really understand why you are fighting it. Why do you

> suppose Dan Hoey titled his article "The _real_ size of cube

> space"? It is because the approach of regarding states as

> distinct just by sticker color arrangement was already well

> established even back in ‘94. He was "injecting the

> complication" of grouping those states which were related by

> conjugation by a symmetry, and he realized that that was not

> the accepted approach. His observation became relevant to

> those who were actually trying to analyze relationships

> between _particular_ states for the conventional 3D puzzle

> because the reduction actually brought the problem into a

> range that was computationally feasible. When we are just

> interested in counting distinct states, that is not our

> issue. You get just as good a sense of how many states

> there are without the much more complex additional reduction

> by a factor somewhat less than n!*2^n.

>

> I think the important thing about the distinction is that,

> when we reduce to equivalence classes of the (first pass)

> distinct states with the conjugation approach, we are

> focusing more on the nature of the _process_ (aka permutation)

> which gives rise to a state rather than to the state itself.

> The result of that process depends on the initial

> orientation of the pile.

>

>>>> The main MC4D page claims to give the exact counts for

>>>> the 3D and 4D puzzles. Is that not true? If not, then I

>>>> need to change it.

>>>>> It is true. Also the counts that David Smith came up

>>>>> with for 5D are intended to be exact. (I am not ruling

>>>>> out the possibility of an error.) As I said, the

>>>>> problem that Eric and David were solving is much more

>>>>> straightforward and admits a precise answer. The

>>>>> problem only arises when you start trying to get the

>>>>> number of equivalence classes of the distinct states

>>>>> they counted that are related through conjugation by a

>>>>> symmetry, which is the complication that it would seem

>>>>> you were trying to inject. That would result in a

>>>>> reduction of Eric’s and David’s numbers by a factor

>>>>> close to (but less than) n!*2^n. But it is not

>>>>> practical to do that in an exact sense.

>> I am not trying to inject a complication, rather I am trying

>> to account for what appears to be an error in our claim. I

>> certainly don’t want to count two states as unique when they

>> share all the same properties other than handedness. I

>> understand that attempting to account for this one rare

>> symmetry won’t change the state count by much and that maybe

>> it is currently impractical to attempt to do that.

> Melinda, it is not an error! The configurations are truly

> different in the sense that no amount of reorientation will

> cause a matchup of sticker colors all around. There is no

> unavoidable reason to want to regard the assignment of

> sticker colors as being mutable.

>

>> This may be covered in previous messages, but would you

>> please explain how you derive the n!*2^n and why it is not

>> (n-1)! as I had thought?

> Melinda, I am losing patience on this one. Brandon tried to

> explain it in his recent post. Nan mentioned it in that old

> one I cited. It comes down to the fact that many of the

> remappings of sticker colors you are proposing are just not

> physical - the puzzles can’t do that! In particular, the

> two sticker colors that are on the same axis in initial

> state must always be on the same axis no matter how you

> otherwise remap the stickers. Thus what is really possible

> for remapping colors comes down to a permutation of the axes

> and possible swapping of the two colors on an axis. E.g.,

> on a standard Rubik’s cube, yellow/white and blue/green are

> so paired. Thus you could not swap yellow with blue unless

> you also swapped white and green. You could also swap just

> blue and green. The n in the formulae Roice and I were

> tossing about is the dimension of the puzzle. So, with

> that understanding, I thought you were saying (2n-1)!, where

> 2n is the number of sticker colors. (Not sure why you took

> out one factor of 2n. I guess you were thinking of one

> color as being a reference with respect to which the others

> were being permuted.)

>

> I will make one more brief attempt at the end; but you

> should really try to reread earlier postings in this thread

> more carefully. It has been explained.

>

>>> You have already worked out a simple example giving

>>> representative members of the equivalence classes for the

>>> case of the 2D puzzle with mirroring twists allowed. I

>>> would hope you would remember the previous occasion on which

>>> some folks on the list tried to explain the relationship of

>>> your equivalence classes to conjugation by a symmetry:

>>> http://games.groups.yahoo.com/group/4D_Cubing/message/1843

>>> Perhaps that previous discussion will make better sense to

>>> you now.

>> A little bit. Nan’s link to

>> http://kociemba.org/math/symmetries.htm on that message is

>> definitely what I am talking about. I think that the fact

>> that MC2D appears to require reflections to operate at all

>> probably confused the issue more than clarifying, because

>> the real issue applies to all of our puzzles, not just to

>> that one.

> I don’t think that allowing mirroring twists makes any

> difference at all with respect to the problems of

> enumerating the distinct states or the equivalence classes

> of these distinct states under conjugation by a symmetry.

>

>> I definitely do not get the bit about how using axes and

>> color pairs is better than thinking about color

>> equivalencies but it is good enough if the result is the

>> same.

> It is important, because, if you fail to maintain the opposing

> color pairs, then you do _not_ get the same result.

>

> More generally, I regard the whole issue of remapping

> colors as a red herring. If you understand conjugation

> by a symmetry, then the recoloring is just an obvious side

> effect which is not worth getting worked up about. It is

> true; but it is not what is important. The actual colors

> themselves were always unimportant. What you should

> actually regard as identifying a sticker ‘color’ is the

> direction it faces in initial state - not some particular

> hue that is being used to render it for visualization

> purposes.

>

>> I am still a little troubled by the "exact" values that you

>> guys seem to prefer. MC2D is indeed a great example of the

>> problem and I just can’t see how we can really say that

>> there are 24 states in that puzzle that I think David S

>> claimed in Wikipedia. Looking at my state graph on the MC2D

>> page there are clearly only 8 that make any real sense to

>> me.

> It is really quite simple. The state of this particular

> puzzle is characterized solely by the permutation of the 4

> corner cubies, and any permutation of the 4 cubies is

> possible. Thus there are 4! different arrangements. This

> is a perfectly legitimate way to count distinct states. You

> have observed that lots of them are not essentially

> different. E.g., you would regard as being essentially the

> same any two states for which just two adjacent corners have

> been transposed without regard to which pair that is. That

> is an additional complication by which you are grouping the

> states into equivalence classes; and, yes, the relation is

> conjugation by a symmetry.

>

> The relevant conjugator for the example is rotation by a

> multiple of 90 degrees in the plane of the puzzle. So start

> with "swap the top 2". Then, if I rotate a quarter turn

> clockwise, swap the top 2, and rotate back, I will have

> achieved "swap the left 2". Those two _different_

> permutations of the cubies are related by conjugation by a

> 90 degree rotation. It really is a different pair of cubies

> that get swapped in the two cases. It is perfectly

> legitimate to regard the two states as being different

> without worrying about their relationship by conjugation.

> Melinda, whether you wish to recognize it or not, you really

> are trying to unnecessarily complicate the problem of

> counting distinct puzzle states. And, as may be seen from

> the "real size" article, the complication is by no means

> trivial.

>

> Let me go back once more to a more complex puzzle and some

> non-trivial twist sequence. Do that sequence starting with

> the pile in initial state and you get one particular

> arrangement. Now get another identical puzzle in initial

> state, but, without twisting any slices, first reorient the

> whole pile so that it is no longer in initial state. Now

> perform the same twist sequence again. You get a new

> arrangement which is not the same as the arrangement on the

> first puzzle. You cannot (in general) make them match up

> sticker-for-sticker just by reorienting one. However, your

> sticker color remapping approach will make them match up

> with appropriate relative orientations. But there is no

> mystery about the required sticker remapping!: It is

> precisely that which was induced by the initial

> reorientation of the second puzzle before performing the

> twist sequence. So there is no need to talk about it.

> Furthermore, it is clear that a reorientation of the pile

> cannot change which pairs of sticker colors occur facing in

> opposite directions on the same axis. Other than that

> restriction, lots of sticker color mappings are possible via

> the orientation step preceding the twist sequence. Indeed,

> that number is n!*2^n.

>

> Mirroring transforms for the conjugator are perfectly

> legitimate even if they are not allowed for the puzzle,

> because the conjugate will not induce any mirroring if none

> of the twists do. (Indeed, you can actually practice

> conjugation by a reflection on a 3D cube by watching what

> you are doing in a mirror. Left/right and up/down do not

> change, but front/back switches as well as the directional

> sense of all twists (always looking towards the twisted

> slice from its side of the cube).)

>

> Regards,

> David V.

>

>

> ————————————

>

> Yahoo! Groups Links

>

>

>

>