Message #2111

From: Melinda Green <melinda@superliminal.com>
Subject: Re: [MC4D] Calculating the number of permutation of 2by2by2by2by2 (2^5)
Date: Sun, 06 May 2012 19:13:13 -0700

Hello Roice,

Since neither yours nor David’s message was a reply to the other, I’ll
just pick yours for my reply though I will reference David’s.

I think that your interpretation of my post is correct though I wonder
about the quantities. For example, I would factor out (6-1)! = 120 from
the 3D cube due to color symmetry, and (8-1)! = 5,040 for the 4D cube
but then I’ve not yet read your citations.

Thanks for bringing up reflections because it makes sense to include
mirror symmetry as well. If I have two scrambled puzzles which differ
only in the handedness of their pattern, all of their other properties
are identical.

David: Regarding your comments, I didn’t completely follow your
description but I do not think we are talking about the same thing but I
could easily misunderstand. Here is a way that I think might clarify
what I am saying: Imagine that you toss me a scrambled Ribik’s cube. I
then pick two sticker colors, peal them off the cube and swap them. I
may repeat that process several times and then toss it back to you. I
claim that I’ve not changed your puzzle state at all. For example, if
you were to then solve it, you could use exactly the same sequence of
moves to solve it. This operation doesn’t involve mirror symmetry
because no color swapping is going to turn a right-handed pattern into
it’s left-handed twin.

You said:

"you could take it that reassigning the colors corresponds to redefining the standard orientation of the pile."

This is /not /what I am saying. If for example I take a pristine Rubik’s
cube and swap the colors of adjacent faces I will get a coloration that
you cannot duplicate by reorienting the puzzle. Your permutations are
therefore only a subset of it’s color symmetry.
Agreement or not, all three of us seem to come up with different
numbers. Can someone set us straight?

-Melinda

On 5/6/2012 6:00 PM, Roice Nelson wrote:
>
>
> Hi Melinda,
>
> To help solve the "God’s Number" problem, the cube20
> <http://www.cube20.org> guys used the trick of considering states that
> /only differ by a symmetry of the cube/ to be the same. I think this
> is precisely what you are describing. Their site links to a cube
> lovers post titled "The real size of cube space
> <http://www.math.rwth-aachen.de/%7EMartin.Schoenert/Cube-Lovers/Dan_Hoey__The_real_size_of_cube_space.html>",
> which writes:
>
> In the sense that (for instance) there is really only one position
> 1 QT from start, even though that QT may be applied in twelve
> different ways, this task amounts to counting the true number of
> positions of the cube.
>
>
> By identifying states like this, they reduced the number of states
> they had to search by a factor of 48 (a factor of 24 from cube
> rotations and an extra factor of 2 from reflections). The cube lovers
> post has more detail about counting numbers of particular states that
> are equivalent when looked at from this perspective. This is also
> described in the paper "25 Moves Suffice for Rubik’s Cube
> <http://arxiv.org/abs/0803.3435>" (and probably in their later papers
> as well, though those don’t look to be available on the arxiv).
>
> So in the 4D case, the state space size would get reduced by 384 (192
> rotational symmetries of the hypercube * 2 for reflections). For any
> dimension, the factor can be calculated as:
>
> 2^n * n!
>
> I grabbed that formula from the wikipedia page on the hyperoctahedral
> group <http://en.wikipedia.org/wiki/Hyperoctahedral_group>. For other
> shapes besides hypercubes, we could also use the size of the
> underlying symmetry group to find out how many states there are which
> are "the same" in this sense. So for Klein’s Quartic, we’d get to
> divide by a factor of 336.
>
> Cheers,
> Roice
>
>
> On Sun, May 6, 2012 at 6:39 PM, Melinda Green
> <melinda@superliminal.com <mailto:melinda@superliminal.com>> wrote:
>
>
>
> I may have answered my own question which is that to account for
> color symmetry we can simply divide by (n - 1)! where n is the
> number of colors. For a 2-colored puzzle there is only one color
> permutation whereas for 3 color puzzles there are two because we
> can fix one color and either swap or not swap the other two. (n -
> 1)! gives the number of unique color swapping patterns. Is that
> right? I usually don’t expect to fully understand the equations here.
>
> -Melinda
>
>
> On 5/6/2012 4:18 PM, Melinda Green wrote:
>> I feel that it’s not just tricky but it is wrong in most
>> conceptualizations of the idea of puzzle state spaces. Taking
>> this natural idea one step further, I would argue that states
>> that have identical patterns of stickers should be thought of as
>> the same state. For example, if you scramble any twisty puzzle
>> and then swap all red and green stickers, then I feel that you
>> still have the same state in terms of permutations since anything
>> you can say about one version also applies to the other. For
>> example, twist one face of a Rubik’s cube. For our purposes, it
>> doesn’t matter which face was twisted. When talking about that
>> state with each other we will never think to ask about the
>> particular colors.
>>
>> Would anyone like to attempt to find the formula for the 3D and
>> 4D cubes with this extra "color symmetry" constraint?
>>
>> -Melinda
>>
>> On 5/6/2012 2:35 PM, Andrew Gould wrote:
>>>
>>> The choice between 31 and 32 comes down to how you define the
>>> locations of pieces. If you define all their locations relative
>>> to one of the pieces it’s 31, but if you define what moves and
>>> what doesn’t for each twist you can make it 32. I note that for
>>> 32, it would be tricky to say that rotating the entire puzzle
>>> doesn’t change the state.
>>>
>
>
>
>
>
>