From:

Subject:

On 10/11/95 at 22:56:15 hoey@aic.nrl.navy.mil said:

But I can report that my search found 16 unique (*not* unique up to

conjugacy) half-way positions. I use the term "half-way" advisedly.

The "half-way" positions are 9q from Start and 8q from B or vice

versa. I guess you could say that the vice versa gives you a total

of 32=16+16 half-way positions, but the whole concept of "half-way"

is pretty slippery in this case anyway.If I understand this, there are 16 positions at 9q from Start and 8q

from B, and there are 16 other positions at 8q from Start 9q from B.

Is each of the first bunch adjacent to exactly one of the other? And

vice versa? It would be good to get them reduced by Q2-conjugacy, as

well.

I don't think I can answer your questions without further analysis,

and I don't have much time to devote to the problem. But let me

clarify as follows. First, the search looked as follows:

Distance from Distance from Total Number of Start B Distance Matching Positions0 1 1 0 1 2 3 0 2 3 5 0 3 4 7 0 4 5 9 0 5 6 11 0 6 7 13 0 7 8 15 0 8 9 17 16

There is a certain arbitrariness in at least two respects. For one

example, to test for a total distance of 11, you could just as well use

distances from Start and B respectively of 4 and 7 instead of 5 and 6.

For another example, the Start-rooted tree and the B-rooted tree have

identical structures, so the first two columns could be reversed.

Indeed, you could get the B-rooted tree simply by pre-multiplying the

Start-rooted tree by B. (This reminds me of one of my most

foolish errors on Cube-Lovers. For search trees where the nodes are

conjugacy classes (or representatives of conjugacy classes), the

tree looks different depending on which class or representative is at

the root. But when the nodes are all the positions, then the tree is

essentially the same in all cases, just pre-multiplied by the root.

I once claimed the tree structure depended on the root for trees

containing all positions, confusing that situation with the situation

for trees of conjugacy classes. Arrg!)

Hence, I am not especially comfortable talking about "half-way" positions.

But continuing anyway, denote the 16 positions which are 8 moves from

Start and 9 moves from B as X_i for i in 1..16. Then, the 16 positions

which are 8 moves from B and 9 moves from Start are B(X_i) for i

in 1..16. A solution to the problem would then look something like

(X_j)Y(X_k)', where Y is in Q-{B,B'}. But I don't think we can say

a priori that there is no Z in Q-{B,B'} and no X_m such that

(X_j)Z(X_m)' is also a solution (Z not equal Y and X_m not equal X_k).

I think to analyze the problem properly you would have to take the

positions X_i for i in 1..16 and the positions B(X_j) for j in 1..16

and match up each X_i with each B(X_j) to see which ones differ

by a quarter turn. Each X_i is going to match up with at least one

B(X_j) and vice versa, but there might be more than 16 matches

overall.

Reduction by Q2-conjugacy is important, but I don't think it would

tell you how many solutions there are that you would really want to

consider to be unique. Recall the solution of Pons Asinorum by

half-depth searches. There are 5 positions unique up to M-conjugacy

which are 6q from Start and 6q from Pons. But most people would

consider that there are only two minimal solutions to Pons that are

really different. The trouble is that 4 of the 5 half-way positions

for the Pons are in the middle of a sub-process which commutes.

= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = Robert G. Bryan (Jerry Bryan) (304) 293-5192 Associate Director, WVNET (304) 293-5540 fax 837 Chestnut Ridge Road BRYAN@WVNVM Morgantown, WV 26505 BRYAN@WVNVM.WVNET.EDU