3
$\begingroup$

If you want to count the number of distinct positions of a standard 2x2x2 Rubik's Cube simple counting arguments will suffice:

  • There are 8 corners, all distinct
  • The 8 corners can be in any permutation (because a quarter turn is an odd cycle)
  • The twist of the 8th corner is determined by the twist of the other 7
  • There are 24 orientations of the cube that must be accounted for

$$\frac{8! \cdot 3^7}{24} = 3674160$$

But there is an implicit assumption in this calculation that each counted position occurs 24 times, once for each orientation of the cube. When this is true the $8! \cdot 3^7$ overcounts by a factor of 24. Since every corner on a normal 2x2x2 is unique there is no extra symmetry and this assumption is true.

But there are variations on a 2x2x2 like the following:

2x2x2 variation with some identical corners

On this 2x2x2 there are two identical all-white corners and six identical red and yellow corners along the equator. The position shown has extra symmetry (e.g. rotating by $120^{\circ}$ through the axis that keeps the white corners stationary).

Now if you try to use simple counting arguments you run into trouble: $$\frac{\frac{8!}{2! \cdot 6!} \cdot 3^6}{24} = \frac{1701}{2}$$

Obviously $\frac{1701}{2}$ can't be right since it isn't even a whole number. The problem is that with the extra symmetry, Burnside's Lemma must be used. Thanks to Jaap Scherphuis this isn't too hard to do by hand:

24 rotations are:

Identity rotation: All $\frac{8!}{2! \cdot 6!} \cdot 3^6 = 20412$ positions stay the same if you don't rotate it.

$\pm 120^{\circ}$ corner rotation: There are $8$ of such rotations. The two white corners must lie on the axis, and the other 6 pieces form two orbits of 3 pieces. The only freedom we have is to orient each orbit, so there are $3^2$ position that stay the same under such a rotation.

$\pm 90^{\circ}$ degree face rotation: There are $6$ of these rotations, but there is no position that has this symmetry. We only get 4-cycles, and don't have 4 pieces of each type.

$180^{\circ}$ face rotation: There are $3$ of these rotations. The pair of white pieces can be in 4 pairs of locations. The other 6 pieces form 3 pairs that can be oriented at will, so there are $4 \cdot 3^3$ positions with this symmetry.

$180^{\circ}$ edge rotation: There are $6$ of these rotations. This is the same as above, $4 \cdot 3^3$ positions with this symmetry.

Putting all that together: $$\frac{(1 \cdot 20412) + (8 \cdot 3^2) + (6 \cdot 0) + (3 \cdot (4 \cdot 3^3)) + (6 \cdot (4 \cdot 3^3))}{24} = 894$$

So there are 894 distinct positions for this 2x2x2 variation (which matches the output of a program I wrote to enumerate them all).

But, if you want to use GAP you run into the same problem. Using the labels in the above image:

# Turn U face
TU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12);
# Rotate whole puzzle around U face
RU := (1, 2, 3, 4)(5, 7, 9, 11)(6, 8, 10, 12)
      (13, 15, 17, 19)(14, 16, 18, 20)(21, 22, 23, 24);
# Rotate whole puzzle around L face
RL := (5, 6, 14, 13)(1, 7, 22, 20)(2, 15, 21, 12)
      (4, 8, 23, 19)(3, 16, 24, 11)(10, 9, 17, 18);

# The whole 2x2x2 cube group
custom222 := Group([TU, RU, RL]);

# The 24 orientations of a 2x2x2
custom222o := Group([RU, RL]);

gap> Size(custom222o);
24

gap> Size(custom222) / 24;
3674160

samecolors := [[1, 5, 12, 16, 17, 23],[3, 7, 10, 14, 19, 21],
               [2, 4, 6, 8, 9, 11, 13, 15, 18, 20, 22, 24]];

gap> (Size(custom222) / Size(Stabilizer(custom222, samecolors, OnTuplesSets))) / 24;
1701/2

Note that the samecolors list identifies which stickers are indistinguishable and the Stabilizer() call finds the group of positions that are all identical. Unfortunately GAP is running into the same issue as the naive calculation and not taking into account positions that have extra symmetry.

I would like to use GAP to apply Burnside's Lemma and get the correct value of 894. You can see that I defined the custom222 using only 3 generators where the first is a face turn and the other two are $90^{\circ}$ rotations of the whole puzzle about different axes. It's these rotations that define the 24 orientations of the cube and I suspect I'll have to use another group with just these two orientation generators to guide GAP about the specifics of what positions are considered identical.

For example, using the group of the 24 rotations of the cube I can get the number and types of symmetries of the cube which are needed by Burnside's Lemma:

gap> List(ConjugacyClasses(custom222o), Size);
[ 1, 6, 3, 8, 6 ]

I think this problem is nearly identical to There are 5472730538 essentially different Sudoku grids but I don't see how they used GAP to apply Burnside's Lemma. It seems to have something to do with ConjugacyClasses() but I don't understand the details.

Note that this question isn't really about this specific 2x2x2. If I can figure out how to use GAP with Burnside's Lemma on this simple 2x2x2 I should be able to handle much more complex puzzles like this one that defy manual applications of Burnside's Lemma.

So, how do I use GAP with Burnside's Lemma to analyze variations on the Rubik's Cube like the one I've shown here?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.