# calculating lower bound



## square-1 (Sep 3, 2010)

I was reading a document on group theory via rubiks cube, i came 
across a calculation of lower bound to gods number,
(see page 31 of http://www.geometer.org/rubik/group.pdf)

It is possible to obtain a crude lower bound for God’s number with the following observation.From a solved cube, there are at most 12 possible arrangements after the first twist (six faces,clockwise or counter-clockwise).After two moves, there are at most 12·11 positions, not 12^2 since one of the 12 moves undoes the original.After three, there are at most 12·11^2 positions,and following the same reasoning, after n moves, there are at most 12·11^n−1 possible positions Since it takes as many moves to solve a position as to get to that position from solved, n must be at least large enough that 12·11^n−1 > 4.32·10^19 where the second number is the total number of cube positions.Solving for n tells us that the lower bound must be at least 19. Slightly more careful calculations (throwing out moves like FFF or FBfb, for example), one can show that God’s number must be at least 21.
notation followed in this document: lower case letters indicate counter clockwise rotations
i.e f=F',b=B' etc.,

but this is not true,we all know that it is 20!
where is the flaw??


----------



## hawkmp4 (Sep 3, 2010)

This shows that a lower bound for *QTM* is 21.


----------



## Lorken (Sep 3, 2010)

Maybe you reach a point where each rotation "un-does" (don't think its a word) another, so you would only need 20 to get it back to it's original state?


----------



## satya (Sep 3, 2010)

square-1 said:


> Since it takes as many moves to solve a position as to get to that position from solved,


i think this is not true,
secondly as hawkmp4 says its in QTM not HTM


----------



## qqwref (Sep 3, 2010)

There is only one problem and it is simple to see: you are not considering half turns at all, only quarter turns. This approach is valid in general, but you must be careful to think about what moves you want to allow.


----------



## Kenneth (Sep 3, 2010)

Puzzle orientations, you can always orient the cube so the first move is R/R' or R2 and the second will be L/L'/L2 or U/U'/U2 (if it is L the third is always U, if it is U the third is one of 5 sides), this reduces the number of combinations a good bit.

3*3*3 + 3*3*(5*3) = 162 instead of (6*3)*(5*3)*(5*3) = 4050 for the first 3 moves.

Hmm, strange, it is factor 25 but the cube has 24 orientations, how did I get to that?? Error?


----------



## qqwref (Sep 3, 2010)

Kenneth: Your 4050 figure does not consider sequences like R L and L R to be the same. When I do that I get a figure of 3888 for 3 moves which is (as it turns out) exactly 24 times 162.


----------



## Kenneth (Sep 4, 2010)

Ah, thanks =)


----------

