From cube-lovers-errors@curry.epilogue.com Mon Sep 30 23:21:04 1996
Return-Path: cube-lovers-errors@curry.epilogue.com
Received: from curry.epilogue.com (localhost [127.0.0.1]) by curry.epilogue.com (8.6.12/8.6.12) with SMTP id XAA12380; Mon, 30 Sep 1996 23:21:03 -0400
Precedence: bulk
Errors-To: cube-lovers-errors@curry.epilogue.com
Date: Mon, 30 Sep 1996 22:29:36 -0500 (EST)
From: Jerry Bryan
Subject: Solving One Cubie
To: Cube-Lovers
Message-id:
MIME-version: 1.0
Content-type: TEXT/PLAIN; charset=US-ASCII
Content-transfer-encoding: 7BIT
I've been thinking about a simple little problem I thought I would share.
Most of the solution is in the archives, but under other guises.
Suppose you scramble a cube and give it to a cubemeister with instructions
to solve any one cubie. This is a truly trivial problem, but let's see
what it can teach us.
The most obvious question is -- what is God's algorithm? That is, from
any position, what is the minimal solution? The cubemeister would observe
that for any position, each of the eight corner cubies and each of the
twelve edge cubies has its own individual minimal solution which is easy
to discover. The cubemeister would then choose the cubie with the
smallest minimal solution and solve it.
Given this simple technique for God's algorithm, what is the maximal
position? That is, what is the position where the minimal solution is as
large as possible?
We start with the edges. The solution is in the archives in two separate
articles. On 6 August 1980, David Vanderschel introduced the concept of
Oriented Distance from Home (ODH). On 7 January 1981, Dan Hoey used the
ODH concept to show that the Pons Asinorum position requires exactly
twelve quarter turns for solution. But for our purposes, the salient
point is that an edge cubie can be at most four quarter-turns from home.
There is exactly one such position for each edge cubie. And the only
position for which each edge cubie is four quarter-turns from home is the
Pons. So for our trivial little problem, the maximal position for the
edges is the Pons.
I have found little information in the archives concerning the same
problem for the corners. (By the way, I have this vision in my mind that
the information for the corners is in there somewhere, but I cannot find
it, neither in the archives nor in Singmaster. Am I remembering a mirage,
or is it in there somewhere and I can't find it?).
Vanderschel does not define an Oriented Distance from Home for corners,
but the generalization is obvious. The following are the ODH values for
the f facelet of the flt cubie.
1+2
+T+
2+3
l+2 0+1 1+2 2+3
+L+ +F+ +R+ +B+
2+3 1+2 2+3 3+2
1+2
+D+
2+3
The maximum distance from Start for any particular corner cubie is
therefore three quarter-turns. The question then is whether all eight
corner cubies can be three quarter-turns from Start simultaneously. There
are probably a number of ways which will work, but the following works
very nicely. Place each corner cubie in its diametrically opposed corner
cubicle. For example, place the flt cubie in the bdr cubicle. The twist
doesn't matter for the individual cubies, except that the overall
configuration for the eight corner cubies must conserve twist. The reason
that twist doesn't matter is that when a corner cubie is in its
diametrically opposed corner cubicle, all three twists are conjugate (see
below).
The maximal position for the corners can peacefully co-exist with the Pons
for the edges. That is, if each corner cubie is in its diametrically
opposed corner cubicle, the parity of the corners is even (as is the
Pons).
In a certain sense, God's algorithm for a single corner cubie is identical
to God's algorithm for the 1x1x1 cube, which is to say, it is identical to
God's algorithm for the rotation group of the cube (which we normally
denote by C). (See my note of 14 Nov 1995.)
Here is how it works. Consider any particular corner cubie such as flt,
and consider any sequence of quarter-turns such as TL where each
quarter-turn moves the cubie in question. Then, the "same" sequence of
whole cube rotations (tl, in this case) will have the same effect on the
same corner cubie. Here, we are using the lower case letters t and l to
denote whole cube quarter-turns and the upper case letters T and L to
denote the face quarter-turns.
The converse is also true if we are careful. That is, each whole cube
quarter-turn may be denoted in two ways. For example, t is the same as
d'. To convert from whole cube rotations back to quarter-turn face turns,
we would convert t to T or to D' depending on whether the cubie in
question were on the Top face or the Down face at the time.
The same trick does not work for the edges. The problem is that face
turns and whole cube turns are not fully interchangeable. For instance, T
and t are interchangeable for the Top edge cubies, as are D and d for the
Down edge cubies. But there is no equivalent interchange for the
"equator" of edge cubies fl, lb, br, and rf. (Well, maybe you could do it
if you allowed slice moves, but we are not working with slice moves.)
I am always interested in symmetry, usually as represented by conjugacy.
For whole cube rotations, there are five conjugacy classes. (Again, see
my note of 14 November 1995.) For individual cubies, we define conjugacy
as follows. Let X and Y be functions (not permutations) which are the
restriction of normal permutations to the cubie in question. Then X and Y
are conjugate if m'Xm=Y for some m in M, the set of 48 rotations and
reflections of the cube. m' must be restricted to the pre-image of the
domain of X, and m must be restricted to the range of X. With the various
permutations thus restricted to functions on the single flt cubie, the
conjugacy classes are as follows:
1. I
2. F, F', L, L', T, T'
3. FF, LL, TT
4. TL', TB, FT', FR, LF', LD
5. TL, L'T'
6. FRR, LDD, TBB
7. FTT, LFF, TLL
Note that if we treat all the moves as whole cube permutations rather than
as functions on the flt cubie, then #4 and #5 are collapsed down into a
single conjugacy class, as are #6 and #7. Then, the conjugacy classes are
the same as the ones for the 1x1x1 cube.
When I first started working on this little problem, I thought the
conjugacy classes for a single cubie might provide a non-arbitrary frame
of reference for defining twist. They almost do, but not quite.
a. When the cubie is in its home cubicle, its twist is
obvious. However, we can observe that I, TL, and L'T'
place the flt cubie in the flt cubicle. TL and L'T'
are conjugate, but they are not conjugate to I. Hence,
it is natural to take I as the untwisted state.
b. When the cubie is immediately adjacent to its home
cubicle (there are three such cubicles), the conjugacy
classes can be used to define twist. For example, the
flt cubie is placed into the ftr cubicle by F, T', and
by LFF. F and T' are conjugate, but they are not
conjugate to LFF. Hence, we can take LFF as the
untwisted state.
c. When the cubie is immediately adjacent to the
diametrically opposed cubicle (there are three such
cubicles), the conjugacy classes can be used to define
twist. For example, the flt cubie is placed into the
frd cubicle by FF, LD, and by LF'. LD and LF' are
conjugate, but they are not conjugate to FF. Hence, we
can take FF as the untwisted state.
d. When the cubie is in the diametrically opposed cubicle
(there is only one such cubicle), I don't see any way
to use the conjugacy classes to define twist. All
three twists are conjugate, and hence none is
inherently different from the other two. For example,
FRR, LDD, and TBB are all conjugate.
= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =
Robert G. Bryan (Jerry Bryan) jbryan@pstcc.cc.tn.us
Pellissippi State (423) 539-7127
10915 Hardin Valley Road (423) 694-6435 (fax)
P.O. Box 22990
Knoxville, TN 37933-0990