From:

Subject:

I wonder about the validity of your Monte Carlo analysis. It seems

to be based on an intuition about how fast the number of configurations

falls off with the distance from SOLVED. I share the intuition, but

I'm not sure I can rigorize it, and that makes me cautious.

I am not sure (that is obvious). But when looking at other (similar)

puzzles I did I think it is a save guess.

What prevents a group from having a "pointy tail", that is, a "corridor"

of elements at increasing distances from the identity?

The groups I did calculate in full do *not* have a pointy tail. This holds

for 2x2x2, 3x3x3 corners only, magic domino. I think it would be a big

surprise if there is a pointy tail. Obviously we can say a priory that

there is not a single configuration opposite from start, so the tail is

not very pointy, if it is at all. For instance for the magic domino the

tail of the list of number of configuration a certain distance from start is:

14: 508704668

15: 232904952

16: 14508468

17: 129376

18: 112

With the maximum at 14 turns. (Here I took the table where only a single

solution is allowed; i.e. no full rotations of the domino.) 1 in 2 (approx.)

configurations requires 14 turns or more. 1 in 100 requires 16 turns or

more. Of course the number of configurations of the cube is quite a bit more.

Still after doing about 9000 configurations not a single one is found that

requires more than 20 turns. If we assume a picture similar to the domino

(which in my opinion is a save guess), there might be configurations that

retuire 21 or perhaps 22 turns, but more is extremely unlikely.

However, there is a remaining question; is the random choice of configuration

unbiased? I think it is. To create a random configuration I do 100 random

turns chosen from 18 possible turns (quarter turns, half turns and reverse

turns). The random number generator is (as far as I know) quite good

(Berkeley Unix's random).

dik