# X1+X3+X5+...

Hi,

Finding the diameter of God's Algorithm for the 3x3x3 cube is equivalent to finding the length of the sequence:

X0
X1
X2
X3
X4
X5
:
:
Xn

where X0=1; Xn is all positions reachable from the Xn-1 positions.

I have noticed and proved that for any rubik like puzzle , the following identity is true:

X1+X3+X5+....+X2n+1=X0+X2+X4+X6+....+X2n

This can be verified for the 2x2x2 cube sequence for example:

1
6
27
120
534
2,256
8,969
33,058
114,149
360,508
930,588
1,350,852
782,536
90,280
276

Though I have been reading many books and articles about rubik's like puzzles, I never came across the above identity. Did anyone see the above identity somewhere? Thanks.

mdlazreg

## Comment viewing options

### Even and Odd Permutations

There's a basic theorem in group theory that says that for a finite permutation group, either all the permutations are even, or else half the permutations are even and half are odd. Most of the cube groups that people are interested in consist of permutations where half of the permutations are even and half of them are odd. The most common cube group is the complete group of the 3x3x3 cube, and it certainly has the aforementioned characteristic that half the permutations are even and half the permutations are odd.

The half even/half odd theorem depends on an even more important theorem that says that any given permutation is either odd or even but not both. That is not a trivial theorem. Any permutation can be decomposed into transpostions, where a transposition is a 2-cycle. As an old programmer from way back, I would simply call these things "swaps". However, the decomposition of a permutation into transpositions is not unique. Therefore, it is not immediately obvious that every single possible decomposition must have the same parity, and it's a difficult thing to prove. The theorem asserts that no matter which decomposition is chosen, the parity will always be the same.

When two permutations are composed, the parity rules are the familiar and obvious ones. The composition of two even permutations is even. The composition of two odd permutations is even. The composition of an even and an odd permutation is odd. And the composition of an odd and an even permutation is odd.

In the quarter turn metric, the parity of the permutations is the same as the parity of their respective distances from Start. That's because a quarter turn itself is odd. Therefore, an even permutation is an even number of moves from Start, and an odd permutation is an odd number of permutations from Start. Hence, half of all positions are an even number of moves from Start and half of all positions are an odd number from Start.

In the face turn metric, the parity of the permutations need not be the same as the parity of their respective distances from Start. As a trivial example, there are 18 positions that are one move from Start. 12 of these positions are odd (a quarter turn's worth), and 6 of these positions are even (a half turn's worth). Therefore, it need not be the case that half the positions are an even number of moves from Start and half the positions are an odd number of moves from Start in the fact turn metric.