CHAPTER 1: GARY RUBINSTEIN & CYCLE NOTATION
It's a slippery slope, aiming to not write a post. I thought it was harmless to watch
They were short and fun and I'd recommend them.
From there, I learned cycle notation!
Let me show you cycle notation.
First, here's a graphic from wiki on the 15 puzzle.
Cycle notation, however, is this:
(1, 2, 3, 16, 13, 14, 15, 4, 12) (5, 7, 9, 11) (6) (8) (10)
See how I got there? I won't bother explaining it because I have faith in you.
When cycles only contain one element, they are omitted, so this is the same:
(1, 2, 3, 16, 13, 14, 15, 4, 12) (5, 7, 9, 11).
Here's another example.
According to Michael Kim, this is one of the hardest positions for the 15 puzzle:
In cycle notation, that's this:
(1, 12, 4, 15) (2, 9, 7, 14) (3, 13, 8) (5, 11, 6, 10) (16)
which is simplified to this:
(1, 12, 4, 15) (2, 9, 7, 14) (3, 13, 8) (5, 11, 6, 10).
One more example. I just opened my browser to an online 15 puzzle and got this.
That's this:
(1, 8) (2, 3, 15, 11, 9) (4) (5, 12, 13, 14) (6, 16) (7, 10)
which is simplified to this:
(1, 8) (2, 3, 15, 11, 9) (5, 12, 13, 14) (6, 16) (7, 10).
CHAPTER 2: KEITH CONRAD & HIS VERY PRETTY GRAPHIC
The whole reason I told you about cycle notation is that if you go to
https://kconrad.math.uconn.edu/blurbs/grouptheory/15puzzle.pdf
and turn to page 9 of 16, you get to a very pretty graphic.
It looks like this.
F = (17, 19, 24, 22)(18, 21, 23, 20)(6, 25, 43, 16)(7, 28, 42, 13)(8, 30, 41, 11)
B = (33, 35, 40, 38)(34, 37, 39, 36)(3, 9, 46, 32)(2, 12, 47, 29)(1, 14, 48, 27)
R = (25, 27, 32, 30)(26, 29, 31, 28)(3, 38, 43, 19)(5, 36, 45, 21)(8, 33, 48, 24)
L = (9, 11, 16, 14)(10, 13, 15, 12)(1, 17, 41, 40)(4, 20, 44, 37)(6, 22, 46, 35)
U = (1, 3, 8, 6)(2, 5, 7, 4)(9, 33, 25, 17)(10, 34, 26, 18)(11, 35, 27, 19)
D = (41, 43, 48, 46)(42, 45, 47, 44)(14, 22, 30, 38)(15, 23, 31, 39)(16, 24, 32, 40)
Who else is swooning?
CHAPTER 3: JAMIE, EVERYBODY
I've told you about Jamie for some time.
His favorite Rubik's cube face is blue, but I'm not a stalker.
The meat and potatoes of this post are my notes on his course:
In the intro to the course, he points out the following:
Every permutation can be restored by swapping 2 things at a time.
Every permutation is either an even permutation or an odd permutation.
Every permutation can be restored by swapping 2 things at a time.
Every permutation is either an even permutation or an odd permutation.
An even permutation takes an even number of swaps to solve.
An odd permutation takes an odd number of swaps to solve.
CHAPTER 4: SET THEORY
A set is a well defined collection of objects known as elements.
Conventionally, upper case letters are used for sets and lower case letters are used for elements.
∈ - is an element of
∉ - is not an element of
To define what’s in a set, we can use curly brackets:
A = {1, 2, 3, 4}
B = {{1, 2}, 3}
In this example, the set {1, 2} is an element of B.
C = {x | x has property P}
The vertical line is read, “such that.”
“Set of all x such that x has property P.”
Common Sets:
ℤ - integers = {…, -2, -1, 0, 1, 2, …}
ℕ - natural numbers (nonnegative integers) = {0, 1, 2, …}
ℤ+ - positive integers = {1, 2, 3, …}
ℚ - rational numbers = {a/b | a, b ∈ ℤ, b ≠ 0}
ℝ - real numbers
[n] = {1, 2, 3, …, n}, where n ∈ ℤ+
Let A and B be sets.
A set is a well defined collection of objects known as elements.
Conventionally, upper case letters are used for sets and lower case letters are used for elements.
∈ - is an element of
∉ - is not an element of
To define what’s in a set, we can use curly brackets:
A = {1, 2, 3, 4}
B = {{1, 2}, 3}
In this example, the set {1, 2} is an element of B.
C = {x | x has property P}
The vertical line is read, “such that.”
“Set of all x such that x has property P.”
Common Sets:
ℤ - integers = {…, -2, -1, 0, 1, 2, …}
ℕ - natural numbers (nonnegative integers) = {0, 1, 2, …}
ℤ+ - positive integers = {1, 2, 3, …}
ℚ - rational numbers = {a/b | a, b ∈ ℤ, b ≠ 0}
ℝ - real numbers
[n] = {1, 2, 3, …, n}, where n ∈ ℤ+
Let A and B be sets.
If every element of A is an element of B, A is a subset of B; A⊂B.
If A⊂B and B⊂A, then A = B.
The set with no elements is the empty set, denoted by ∅ or {}.
Cardinality: |A| = number of elements in A
Set operations:
Union: A∪B = {x | x∈A or x∈B}
Intersection: A∩B = {x | x∈A and x∈B}
Complement: Ac = A̅ = {x | x∉A}
Set operations:
Union: A∪B = {x | x∈A or x∈B}
Intersection: A∩B = {x | x∈A and x∈B}
Complement: Ac = A̅ = {x | x∉A}
(This requires that we think of A as a subset of some larger set called the Universe, 𝒰)
Difference: A-B = {x | x∈A and x∉B} = A∩Bc
Cartesian Product: A x B = {(x,y) | x∈A and y∈B}
Cartesian Product: A x B = {(x,y) | x∈A and y∈B}
For example, {1, 2} x {a, b, c} = {(1, a), (1, b), (1, c), (2, a), (2, b), (2, c)}
Laws of Set Theory; these are not important for this post, just fun.
Laws of Double Negation
Laws of Double Negation
(Ac)c = A
DeMorgan's Laws
(A∪B)c = Ac∩Bc
(A∩B)c = Ac∪Bc
Commutative Laws
A∪B = B∪A
A∩B = B∩A
Associative Laws
(A∪B)∪C = A∪(B∪C)
(A∩B)∩C = A∩(B∩C)
Distributive Laws
A∪(B∩C) = (A∪B)∩(A∪C)
A∩(B∪C) = (A∩B)∪(A∩C)
Idempotent Laws
A∪A = A
A∩A = A
Identity Laws
A∪∅ = A
A∩𝒰 = A
Inverse Laws
A∪Ac = 𝒰
A∩Ac = ∅
Domination Laws
A∪𝒰 = A
A∩∅ = ∅
Absorbtion Laws
A∪(A∩B) = A
A∩(A∪B) = A
CHAPTER 5: SOME THINGS ABOUT INTEGERS
a divides b, written a|b, if b = ad for some integer d
d is the greatest common divisor of a and b, written gcd (a,b) if and only if:
i. d|a and d|b and
ii. if c|a and c|b, then c ≤ d
When two integers have a gcd of 1, they are considered relatively prime.
Division Algorithm:
Let a, b ∈ ℤ, and b ≠ 0.
Then there exist unique q, r, with 0 ≤ r < |b| such that a = qb + r
q is quotient, r is remainder
Modular Arithmatic - the study of remainders
If a = bq + r, then gcd(a, b) = gcd(b, r)
Proof
Let d = gcd(a, b) and g = gcd(b, r)
d|a,b
d|(a - bq), so d|r.
but g is the greatest common divisor of b and r
so d ≤ g g|b,r
g|(bq + r), so g|a.
but d is the greatest common divisor of a and b
so g ≤ d
so g = d.
MR will move like R but one layer to the left, and
MF will move like F but one layer behind.
But what do middle slice commutators not do?
Euclidean Algorithm:
Let a, b ∈ ℤ, and b ≠ 0.
If a = qb + r, 0 ≤ r < b,
b = q1r + r1, 0 ≤ r1 < r
r = q2r1 + r2, 0 ≤ r2 < r1
...
rk = q(k+2)r(k+1) + r(k+2), 0 ≤ r(k+2) < r(k+1)
then for k large enough, say k = m,
r(m+1) = 0, and
r(m-1)= q(m+1)rm, and
gcd(a,b) = rm.
Ex.
gcd(210, 154) = gcd(154, 56) = gcd(56, 42) = gcd(42, 14) = gcd(14, 0); gcd = 14.
Extended Euclidean Algorithm:
If gcd(a,b) = d, then there exist integers u and v such that
au + bv = d.
In other words, you can always find a linear combination of any two numbers to obtain their gcd.
Ex.
Working backwards from the previous example,
14 = 56 - 42 = 3(56) - 154 = 3(210-154) - 154 = 3(210) - 4(154)
A prime is an integer > 1 with exactly two positive divisors - 1 and itself.
Therefore 1 cannot be a prime; 1 is a "unit."
There are prime numbers (2), composite numbers (15), and units (1).
If p is a prime number and a and b are integers such that p | ab, then either p | a or p | b.
Proof
Suppose p | ab but p ∤ b.
Then gcd (a, p) = 1.
By the extended Euclidean Algorithm we know that
There is a u, v such that au + pv = 1.
bau + bpv = b.
Since p | (abu + bpv), then p | b.
Euler's φ-Function
For any positive integer n, φ(n) is the number of integers in {1, 2, ..., n} which are relatively prime to n.
In other words,
φ(n) = |{m ∈ ℤ | 1 ≤ m ≤ n, gcd(m, n) = 1}|.
This is a sequel of sorts - I realized since our last correspondence that we can play around with middle slices and create patterns that push the center (or everything but the center) around.
Center tiles aren't normally thought of as permutable.
In actuality, they are six parts of one piece.
So of course, they always maintain a certain relationship.
(Remember, if red is on the right and blue is in the back, this means white is on top.)
But for the purposes of this chapter, think of it this way. The edges and corners are form something we can think of as an exoskeleton, and within this exoskeleton cage, middle slice commutators can rotate the center piece. That also reorients some of the center tiles, but this reorienting is invisible on regular Rubik's cubes. In supercubes, however, each center tile has a predefined "correct" orientation.
Assume we have an exoskeleton, which is the same thing as a solved void cube.
How many different ways could we pop in a center piece, including the different orientations?
The first of the 6 center squares can go in 24 ways - 4 orientations in one of 6 planes.
An adjacent center square could go in 16 ways - 4 orientations of 4 planes.
The remaining 4 center squares can each go in 4 ways - 4 orientations of 1 plane.
So that's (49)(6), which is a lot.
Half of those are solvable regarding position;
Middle slice moves do not alter corner parity but DO alter edge parity.
And for corners and edges to both be solved at the same time, their parities must match.
A quarter of them are solvable regarding orientation (hello supercubes).
So if you have an exoskeleton that cannot be tampered with,
and pop in a center in at random, it will be solvable one out of every eight times.
If you'll recall from my first post,
MU will move like U but one layer underneath,MR will move like R but one layer to the left, and
MF will move like F but one layer behind.
(Cubers actually follow a different notation for this, but I think it makes no sense.
As I don't talk to cubers, there is absolutely no incentive for me to not make sense.)
Now we'll write some simple (4-part) middle slice commutators.
It's important to note that middle slices do NOT have an intersection of 1 slot.
Any two different middle slices have the intersection of 2 slots, and these are center tiles.
In other words, this isn't your standard 3-cycle discussion.
All three of the central slice moves have the same relationship to one another.
So in a way, there are only four 4-part middle slice commutators to discover.
If we take any two middle slice moves, MX and MY, these are:
MX*MY*MX-1*MY-1
MX2*MY*MX2*MY-1
MX*MY2*MX-1*MY2
MX2*MY2*MX2*MY2 - this happens to be the identity element.
If you want to orient your cube first, however, there are 54 to discover.
There are 6 symmetrical sets of 9:
9 MUMR's, 9 MUMF's, 9 MRMU's, 9 MRMF's, 9 MFMU's, and 9 MFMR's.
I say 9 because each of two parts could be MX, MX2, or MX-1.
So 4 or 54. What ever shall I do?
And that, ladies and gentleman, is how you write a cliffhanger.
EPILOGUE 2: CENTER TILE COMMUTATORS
Well, I'd rather not aim for efficiency in case I'm wrong about something.
I don't mind being redundant, but within reason!
I'll cover the 16 (omitting the two identity elements) that begin with my favorite M slice, MU.
But before I do this, I have to define a notation for reorientations.
I'll do that with exponents like this:
O0 - correct orientation
O1 - 90° clockwise from correct orientation
O2 - 180° from correct orientation
O-1 - 90° counterclockwise from correct orientation
So "(R, L) → (U-1, D-1)" means:
The right central tile moves to the up central spot.
The right tile gets oriented one turn counterclockwise.
The left central tile moves to the down central spot.
The left central tile gets oriented one turn counterclockwise.
Here are the MUMR's and MUMF's in two charts.
No Positions Maintained Commutators
Two Positions Maintained Commutators
EPILOGUE 3: SOME OBSERVATIONS
Did you stare at the charts like a kid in a candy shop?
Notice that the "no positions maintained commutators" use all 90° rotations.
They're organized so that two red commutators will restore center tiles to their original faces.
The "two positions maintained commutators" use exactly one 180° rotation.
Also, the "two positions maintained commutators" only yield 3 possible outcomes.
The total number of orienting clockwise or counterclockwise rotations is always even.
If you think of the cube as having 3 axes, the first 8 commutators allow the six piece center to move to any of the positions in which no center tile stays on its original axis.
The remaining 8 commutators only have 3 results, and all of these keep all tiles on their original axes.
In these cases, two of these six pieces will be in their correct planes, and four will not.
They most certainly do not change the parity of the center tile positions.
They also most certainly do not change the parity of the center tile orientations.
(We've never thought about the parity of orientations before because we've never had 4 different orientations to choose from.)
So the first eight commutators seem to be as good as any one commutator if we're willing to reorient the cube. What about the last 8? Can our first commutators generate this state?
Let's see.
(MU*MR*MU-1*MR-1)*(MU*MF*MU-1*MF-1)
(F, B) → (F1, B-1)
(R, L) → (L0, R0)
(U, D) → (D1, U-1)
And in terms of position (not orientation), that's a "two positioned maintained" result.
Notice that all tiles are also on their original axes.
(If this was a two "positioned maintained" with the other four NOT on original axes,
that would have changed the parity of center tile positions.)
So it looks like all 16 of these can be simplified one "no positions maintained."
My favorite is the first:
MU*MR*MU-1*MR-1.
To see what it does exactly, let's condense our center piece to an imaginary edge cubie.
After all, we only need two adjacent faces to define the position of the center piece.
I'll choose Front Down, just because it seems like a grounding edge; easy to remember.
What MU*MR*MU-1*MR-1 does in terms of position is move FD to DR.
That's not the same as moving FD to RD, which is a rotation on a (north/south pole) axis.
Again, that would have been a "changing parity of center tiles" move.
No, this is more like how knights on a chessboard move - FD (through DB to) DR
Or perhaps, simply, F goes to D and D goes to R.
That's easy to remember if you just think "Franklin Derano Derano Roosevelt.
That's pretty fun - Derano, Derano, Derano, Derano.
Henceforth, MU*MR*MU-1*MR-1 shall be called Derano.
Very good. This is a good place to end a chapter.
Pinky, are you pondering what I'm pondering?
EPILOGUE 4: GENERATING REORIENTING ALGS
The time has come to combine like colors.
(MU*MR*MU-1*MR-1)*(MU-1*MF-1*MU*MF)
(F, B) → (F-1, B1)
(R, L) → (R0, L0)
(U, D) → (U-1, D1)
and similarly,
(MU-1*MF-1*MU*MF)*(MU*MR*MU-1*MR-1)
(F, B) → (F1, B-1)
(R, L) → (R0, L0)
(U, D) → (U1, D-1)
Aha! This allows us to combine clockwise and counterclockwise reorientations within a pair.
Combining the green, orange, and blue commutators with their pairs yields the same results.
But what are these two results really saying?
Orientation is maintained with one pair.
Of the other four planes, two adjacent (B&D or F&U) rotate clockwise.
The remaining two rotate counterclockwise.
So they're the same algorithm with reoriented cubes, and we only need one.
What's another thing we could do?
Let's make a new commutator with a single outer plane rotation.
We can choose any outer plane rotation we want for this.
Because we're starting with MU, I like D-1.
So let D-1 be X and our Derano be Y to create a new commutator and see what happens.
D-1*(MU*MR*MU-1*MR-1)*D*(MR*MU*MR-1*MU-1) yields
(F, B) → (F1, B0)
(R, L) → (R0, L0)
(U, D) → (U0, D-1)
Eureka! We can now alter the orientation of adjacent center tiles by just 1.
There are many equivalent ways to write this, but we only need one.
We have finally made the most powerful potion of them all!
It reorients two adjacent center tiles only.
That means it can generate the result of the first alg and we can toss that one.
EPILOGUE 5: VERY DERANO
So now, to answer the question we've all had on our minds from the beginning:
Assuming our center is locked into a solvable position within an exoskeleton, are these tools powerful enough that we can then solve the centers?But of course.
Step 1: Get each center tile onto its plane.
a. If the pairs are already in their planes,
MU*MR2*MU-1*MR2: F → B, R → L, U → U
MU2*MR*MU2*MR-1: F → B, R → R, U → D
MU2*MF*MU2*MF-1: F → F, R → L, U → D
b. If not, that's even easier. Choose the correct one of the following.
MU*MR*MU-1*MR-1: F → D, R → F, U → L
MU-1*MF-1*MU*MF: F → R, R → D, U → B
MU*MR-1*MU-1*MR: F → U, R → F, U → R
MU-1*MF*MU*MF-1: F → R, R → U, U → F
MU-1*MR*MU*MR-1: F → D, R → B, U → R
MU*MF*MU-1*MF-1: F → L, R → U, U → B
MU-1*MR-1*MU*MR: F → U, R → B, U → L
MU*MF-1*MU-1*MF: F → L, R → D, U → F
Step 2: Reorient those centers! a. If the pairs need an even number of rotations,
(MU*MR*MU-1*MR-1)*(MU-1*MF-1*MU*MF)
(F, B) → (F-1, B1)
(R, L) → (R0, L0)
(U, D) → (U-1, D1)
b. If not,
D-1*(MU*MR*MU-1*MR-1)*D*(MR*MU*MR-1*MU-1)
(F, B) → (F1, B0)
(R, L) → (R0, L0)
(U, D) → (U0, D-1)
Or to get very Derano about it,
Step 1: Get each center tile onto its plane.
a. If any center tile is on its original axis, Derano it out.
b. Find the imaginary FD that needs to get to DR.
c. Derano it.
Step 2: Reorient those centers!
a. If any center tiles are 180° off, [D-1*(Derano)*D*(Derano-1)] them first.
b. Put tiles needing to turn clockwise in F and tiles needing to turn counterclockwise in D.
c. [D-1*(Derano)*D*(Derano-1)] them, one FD pair at a time.
Solving a supercube backwards has never required less memorization.
EPILOGUE 6: HAPPY SUPERCUBING
Working backwards, now we have to figure out how to form an exoskeleton that locks our center into a solvable state. Remember when I said that if we started with an exoskeleton and popped in a center at random, we'd be able to solve it one in every eight times? Well, solving an exoskeleton in the first place brings those odds up to one in two. Let me explain.
A solvable center requires two conditions:
The first is that regarding position, (center parity) + (edge parity) + (corner parity) ≡ 0 mod 2.
The second is that regarding orientation, (sum of center tile orientations) ≡ 0 mod 4.
A solved exoskeleton guarantees the first condition and increases the chances of the second.
Regarding the first, a solved exoskeleton means that the parities of the centers and edges already match, and that the parity of the center is even. Sorting that out in the first place is the parity error of the void cube.
The most important distinction between supercube exoskeletons and void cubes is that void cubes are stupid and supercubes are not. With a void cube, if the "wrong invisible centers" are "chosen," there is a parity error between two pieces, like two edges or two corners. Because two pieces are unflippable, right? Wrong. Two pieces are unflippable relative to fixed centers.
(And that's why we're writing this entire epilogue to begin with - because we're daring to wonder about fixed centers. I looked up this term - daring to wonder - because my intention was to be dramatic, which is not the same thing as random blasphemy. To my relief, I am simultaneously making fun of three things - the phrase itself, religion, and Oreos.)
Back to the supercube - as we're forming the exoskeleton, we need to make sure the center is not in one of those odd parity states I described in "epilogue 3." If one pair of centers is on their axis, so too must the other pairs of centers be. It's also okay if none of them are.
Regarding orientation, we need the sum of the center tile orientations to be divisible by 4. Once we solve the exoskeleton, the sum of our center tile orientations will not be odd, but they could be ≡ 2 mod 4. In other words, it's possible to solve an exoskeleton in such a way that you are later stuck with one center tile upside down.
My favorite way to make an exoskeleton is to begin on one plane. So that's 8 pieces (4 corners and 4 centers), ignoring the center. I personally use George's He-Man supercube, and my favorite face is Skeletor. You know, if you've made it this far in this reading, send me an email with a theme of your choosing, and I'll design and buy you your very own supercube. I am so confident that nobody will ever read this that I am willing to put my money where my mouth is and potentially quit all my jobs and go broke, buying my public their own personalized supercubes.
At this point, with one completed face of our exoskeleton, verify that the middle slice adjacent to the completed face is rotated in such a way that there is no center & exoskeleton parity issue. In other words, avoid the void.
Now, regarding orientation, 5 of our 6 centers are set. So our next move is to calculate the correct orientation of the center that is still movable. That one is the center across the plane of our solved plane. We all know how to do this; we have not found ourselves in this paragraph with no understanding of modular arithmetic. If you would like to lock one center tile into an upside-down position for shits and giggles, and I have, this is your chance. Once that final center tile is positioned, proceed how you'd like. I like to solve that entire opposite face, leaving four connecting edge cubies of the exoskeleton last. That way, I can forget about orientations immediately.
The End.
But Lan, isn't it easier to solve around fixed centers?
Yes.
No comments:
Post a Comment