Math Is Fun Forum
  Discussion about math, puzzles, games and fun.   Useful symbols: ÷ × ½ √ ∞ ≠ ≤ ≥ ≈ ⇒ ± ∈ Δ θ ∴ ∑ ∫ • π ƒ -¹ ² ³ °

You are not logged in.

#1 2012-05-29 01:13:27

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Rubik's cube algorithm with period 5?

Can you design a Rubik's Cube algorithm that gives you back the cube you started from when repeated 5 times,if it exists? If it doesn't exist-can you prove it?

Examples of algorithms with periods 1,2,3,4 and 6:

1: U4
2: U2
3: F2 U L R' F2 L' R U F2
4: U
6: R' D' R D


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#2 2012-05-29 06:09:15

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

How about?


Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#3 2012-05-29 07:04:04

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

Nice one,Bob! How did you find it?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#4 2012-05-29 08:12:57

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

I have a book I would strongly recommend called 'Handbook of Cubik Math' by Frey and Singmaster.

5 cycles are rare even in this book but after a long search I found R^2 D gives a 2 cycle, a 6 cycle and a 5 cycle.  That's what I needed.  By raising to the sixth power the 2 cycles and 6 cycles go, leaving just the 5 cycle.  I changed the D to U, checked it out and there you have it.  I am going to predict your next question (in my head) and the answer is "no, you can't."

Do you have a question for me?

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#5 2012-05-29 08:21:41

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

I think I get why it can produce those periods. I think it can produce any period that is a divisor of 30 i.e. 1,2,3,5,6,10,15 and 30.

I think you predicted my question correctly,and it was wheter I can have a period 7 algorithm,but I would like to know why not. smile


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#6 2012-05-29 08:27:05

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

Btw,I have found that (R' U)**9 has period 7. dizzy


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#7 2012-05-29 08:36:16

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

hi Stefy,

I thought you would ask "Can any size cycle be found?" which is slightly more general but the explanation is the same.

The total number of different positions of cublets in the 3 x 3 x 3 cube is

So this is the number of distinct 'moves' that can be found.  These form a 'group' with order N.

The order of the only possible sub groups must divide N so, for example, no cycle of order 41 can be found.

But 7 divides N so I suspect that means a 7 cycle can be found.  unfortunately, knowing that does not help you to find one.  I'll have a look through the book and see if any are given. (I seem to remember I did have one years ago, because I tried to make a cube with no colours, just days, dates, and months so you could use it as a calendar.  Each day you would advance to the next date by doing the right cycles on the cublets.  The tricky bit was to find a way to hide the unneeded dates around the back and sides so the front showed just the right things.

I'll post again when / if I find a 7 cycle.

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#8 2012-05-29 08:47:22

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

Arha.  You got one before I had typed my long post.  Well done!

smile

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#9 2012-05-29 09:12:54

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

Change the 9 to 7 and you get a 9-period. But which question did you predict?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#10 2012-05-29 18:52:20

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

The move R'U has a 9 cycle and a 7 cycle.  So the number of repeats can be used to 'eliminate' one cycle.

When you set the 5 cycle challenge you gave the impression you thought it might be impossible.  So when I gave you a move for it, I thought you would jump to wondering if all cycles could be done.  That was the question I was expecting and my answer was "No you can't."

But what you asked was more modest; can you find a 7 cycle?  Then you found one yourself so I've stopped looking.

The underlying group theory means that n-cycles are only possible if n divides N, the order of the group of all possible moves.  But that group theory doesn't find them for you, but it does, as the example above shows, allow you to construct them once you have analysed a move.


Example.  Try

Look at the cublets and work out where each one moves.  You should be able to find some 3-cycles and 2-cycles.  By repeating the move three times you are left with a simple pair of 2-cycles.

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#11 2012-05-29 23:18:59

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

I just saw the long post. I missed it when I posted my reply.

Wouldn't making a date cube be impossible because it would have to be a 365 cycle?

I know the R**2 U**2. It gives a nice fish pattern after a few iterations.

Another question about the cube-how can I come up with my own algorithms for doing a certain things on a cube?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#12 2012-05-30 00:06:22

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

The date cube was going to have a 12-cycle of months; a 7-cycle of days of the week; a 10-cycle of unit digits; and a 4-cycle of blank, 1, 2, 3.  These last two would come together to make days in the month such as 28 or 7 or 31.  We've got one of those mantlepiece ones where you have to advance the cards manually.  I wasn't planning this would cycle through the whole year automatically; as you observe that would not be possible.  But my version would take more skill because you'd have to know all the cycles and when to apply them.

Shown below as it is in my head.  That one won't work for several reasons.

To find your own moves you have to try a sequence and look at the cycles.  Then use these constructively.  I don't think anyone has come up with a simple way.

Bob

View Image: rubik.gif

You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#13 2012-05-30 00:08:52

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

What about leap years?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#14 2012-05-30 00:11:19

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

You just rotate to make the 8 into a 9 as any other month.  Then you have to go twice for 9 into 0 onto 1 and move the 2 onto 3 onto blank.

That's where the skill comes in.

Bear in mind I never actually made this cube.

I edited the last to answer your question.

B


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#15 2012-05-30 00:18:31

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

So you have center pieces 1,2,3 and 3 blanks,what do you have on the edges and corners?

Here is a similar concept:http://www.geeksugar.com/Rubiks-Cube-Pe … sy-3035723

Last edited by anonimnystefy (2012-05-30 00:24:49)


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#16 2012-05-30 06:36:43

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

Hi Bob

I have two questions:

1) Is there an algorithm which goes through all possible cube states?

2) What is the period of the algorithm R L' U?


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#17 2012-05-30 08:57:51

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

hi Stefy

1) Is there an algorithm which goes through all possible cube states?

You must be joking!!  You'll get repetitive strain injury.

2) What is the period of the algorithm R L' U?

I'll check it out and post again later.

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#18 2012-05-30 09:01:07

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

I hope you didn't think I would actually do the algorithm. dizzy


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#19 2012-05-30 09:59:18

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

RL'U

This consists of

ufr - ruf This corner stays in place but is twisted 1/3 turn so returns to its start in a 3-cycle.

ufl - rub - rbd - rdf = flu   These corners cycle in four but twisted so this is a 3x4 = 12-cycle.

ubl - bdl - dfl - lub  These corners cycle in three but twisted so this is a 3x3 =  9-cycle.

uf - ul - bl - dl - fl - ub - ur - br - dr - fr - uf  This is a 10-cycle.

df and db stay in place.

The LCM of 3, 12, 9 and 10 is 180.

So all cublets return to their start positions after 180 repeats.

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#20 2012-05-30 10:06:42

anonimnystefy
Real Member
From: The Foundation
Registered: 2011-05-23
Posts: 15,598

Re: Rubik's cube algorithm with period 5?

Now that is some nice analysing! I must have done a move wrong because I repeated the algorithm 200 times and the cubelets didn't go back to their place.


“Here lies the reader who will never open this book. He is forever dead.

“Taking a new step, uttering a new word, is what people fear most.” ― Fyodor Dostoyevsky, Crime and Punishment

Offline

#21 2012-06-15 05:07:18

cmowla
Member
Registered: 2012-06-14
Posts: 57

Re: Rubik's cube algorithm with period 5?

Hi everyone, this is my first post on this forum!  I tend to spend time on writing up my posts, so they are often times lengthy if I have enough to say on the subject!

I have been studying Rubik's Cubes of all sizes for several years, and I have been a part speedsolving.com forum for almost three years.  Thus I have some things to say about some of the questions and the responses to those questions.

I'm annoyed to see that I cannot post links since I'm a new member.  However, I will mention the key phrase to search for in google, and the web-page I'm referring to is the first result.

bob bundy wrote:

To find your own moves you have to try a sequence and look at the cycles.  Then use these constructively.  I don't think anyone has come up with a simple way.

Actually, there is a simple way, but it can be tedious.  Before I explain this, I need to provide a little background information.

The 3x3x3 Rubik's Cube Pieces
It has:
12 Edges
8 Corners
6 fixed centers (they only rotate on the xyz axis core:  they don't ever move with respect to each other)

Just because the order of the Rubik's Cube Group (the diameter) is approximately 43 billion billion, there is no possible way that it can have a cycle greater than 12, because the most abundant piece type is the edges, and there are only 12 of them.

To see a powerpoint presentation I made for my university which shows how to come up with the formula for the number of possible configurations on the nxnxn Rubik's Cube, >>Link:  Look up "Christopher Mowla UNO" in Google.  It should be the first result, which is a 4.3mb powerpoint presentation.

On the Rubik's Cube, we can have more than one disjoint cycle of the same piece type of which can be different size cycles or multiples of the same cycle type.

Here is a list of all of the possible cycle types there can be for the edges of the 3x3x3 Rubik's Cube.  The cycle type is in curly braces.

But before I show the list, I want to introduce some "cubing" terminology.
Permutation - Describes when two or more pieces are cycled with each other.
Orientation - Describes when two or more pieces are cycled with themselves.  This occurs when a corner or an edge is in its solved location slot, but is twisted (common talk is a corner is twisted, and an edge is flipped).  If a corner or an edge is in some other slot (the edge can be in 11 other slots other than its own, since there are 12 edges and the corner can be in 7 other slots than its own, since there are 8 corners) and is twisted (or flipped if it's an edge), then it is NOT cycled with itself anymore:  it's only cycled with the corner (or edge) whose slot it's currently in (and there might be more corners and/or edges involved in the cycle).

So, according to the format of the list of all possible cycles below, a one-cycle is "{1}".  A 1-cycle represents either the orientation of a piece or that that piece was not affected by an algorithm, not the permutation.

It turns out that you can only have an even number of edges flipped and, if you define a frame of reference for the direction which a corner is twisted, then the sum of the orientation of the corners must be divisible by 3.

>>Link:  See "Laws of the Cube" (Ryan Heise)

>>Also, in my Powerpoint presentation, slide 74 has a great illustration for the corner law.  It will help those who don't understand to know what I am talking about.




Now, here's the list.
The Number of Possible Cycle Types for the Edges of the 3x3x3 Rubik's Cube

Notes:
*Since I mentioned a 1-cycle is not considered a "Permutation" in "cubing" terminology, I will disregard the 1-cycles.
*In order to list all possible cycles for n pieces, one must also list all cycle types for 2 to n-1 pieces as well (note that I started with 2 since I'm avoiding the mathematical "1-cycle" and separating it to be an "orientation" and not a "permutation").
*Examples:  {2} means "one 2-cycle", {4,2,2} means "one 4-cycle, and two 2-cycles", etc.
*For the corners' cycle types (classes), you can just look at the first 7 results, but all 11 are for the edges' cycle types.


2 Pieces
{2}

3 Pieces
{3}

4 Pieces
{4}, {2,2}

5 Pieces
{5}, {3,2}

6 Pieces
{6}, {4,2}, {3,3}, {2,2,2}

7 Pieces
{7}, {5,2}, {4,3}, {3,2,2}

8 Pieces
{8}, {6,2}, {5,3}, {4,4}, {4,2,2}, {3,3,2}, {2,2,2,2}

9 Pieces
{9}, {7,2}, {6,3}, {5,4}, {5,2,2}, {4,3,2}, {3,3,3}, {3,2,2,2}

10 Pieces
{10}, {8,2}, {7,3}, {6,4}, {6,2,2}, {5,5}, {5,3,2}, {4,4,2}, {4,3,3}, {4,2,2,2}, {3,3,2,2}, {2,2,2,2,2}

11 Pieces
{11}, {9,2}, {8,3}, {7,4}, {7,2,2}, {6,5}, {6,3,2}, {5,4,2}, {5,3,3}, {5,2,2,2}, {4,4,3}, {4,3,2,2}, {3,3,3,2}, {3,2,2,2,2}

12 Pieces
{12},{10,2},{9,3},{8,4},{8,2,2},{7,5},{7,3,2},{6,6},{6,4,2},{6,3,3},{6,2,2,2},{5,5,2},{5,4,3},{5,3,2,2},{4,4,4},{4,4,2,2},{4,3,3,2},{4,2,2,2,2},{3,3,3,3},{3,3,2,2,2},{2,2,2,2,2,2}

As you can see, the total number of cycle types for n pieces is the sum of the number of cycle types for n-1 pieces, and for each piece, it is the number of combinations in which integers less than or equal to itself which add up to itself.

You can compute these with Mathematica (I don't know the code for WolframAlpha) by "IntegerPartitions[n, All, {2, 3, 4, ..., n-1, n}]"

In addition, you can compute the number of each cycle type by using the formula found below.  The sum of all of the different possible cycle types adds up to n! for n objects (for this, we do consider all of the 1-cycles/pieces which are untouched).
>>Link:  Look up "Cycle classes of permutations" in Google.  It's the first result.






Now, as to why, bob bundy, I mentioned that there is an easy but tedious way to construct an algorithm which can generate any cycle type.  First of course, is to mention that there can be even permutations or odd permutations (the term "permutations" here is interchangeable with cubing terminology and mathematics).  If a cycle type (recall that in the list above, a cycle type was {#, another #,...}.  That is, the cycle type includes everything in the curly braces) has an overall odd permutation, then the algorithm we use to construct it must have an odd number of outer layer quarter turns.  If the cycle type is an overall even permutation, then the algorithm we construct must have an EVEN number of outer layer quarter turns.  When I say "outer layer quarter turns," I mean that if you turn the middle slice one quarter turn, it's actually 2 quarter turns (an even permutation).  But a quarter turn, say, R, gives an odd permutation.

Examples:
Even Permutations {3}, {3,3},{2,2}, {2,3,6}
Odd Permutations {2},{4},{6},{8},{2,3}

CUBE LAW
On slide 83 of my power-point presentation, I basically say that if there is an odd permutation in the edges, there is an odd permutation in the corners, and vice versa (an if and only if statement).

If your desired/goal cycle class type to create is an odd permutation, you need to do an odd permutation algorithm an odd number of times to the cube.  It's probably best to do a 2-cycle PLL algorithm which only affects two edges and two corners.
>>Link:  Look up "PLL speedsolving wiki" in Google and see the algorithms (they have links to an online java applet) F, J, N, R, T, V, and Y permutations.

You need to look up video tutorials on commutators and conjugates.
I made a "Derivation Video" on a 4x4x4 "Parity Algorithm" I made (which wasn't made before in the 30+ years the 4x4x4 cube was out), and in the first part, I talk a little about commutators and conjugates (conjugates are commonly called "setup moves" in cubing terminology:  where you do some moves before hand and you undo after some known algorithm).

You can watch the video starting at 4:02 to 12:00.
>>Link:  Look up "derivation of HG algorithm part 1" in Google.  It will be a You-Tube video (it's the first result).
In that video when I mention "slots" around 11:40, see slide 65 of my power-point presentation to see a good visual of what the difference is between a "slot" and a "piece".

(You can watch all 4 parts if you wish, but I think that portion of the first video and maybe the middle portion of the second video is more than enough (a lot of that material is for doing more advanced tasks).  And of course, you can watch any videos or read any guides that will help you.).
(If you like the cube software I used in the video, just see my cubetwister video for supercube stickers to get all of the information on installation).

The commutator in my video swaps only 3 pieces on the cube.  We can apply it to edges (e.g. M' U R U' M U R' U' = [M', U R U']) or to corners (R U' L' U R' U' L U = [R, U' L' U]) and just affect those pieces separately.

Now, we can make a 5-cycle, for example, by doing two applications of a 3-cycle commutator (like the one above).
Using 2 line permutation notation with the convention that the following is the identity (a subset of a solved orbit of either corners or edges):

1) Apply a 3-cycle commutator to a solved cube which affects slots A, B, and C.


2) Apply the same commutator to, for example, slots C, D, and E, so that they overlap.

, we generate a 5-cycle of either edges or corners (which ever version of the commutator we chose).

You probably will need to apply setup moves (conjugates) before the 3-cycle commutator to affect different pieces than what the commutator affects by itself.  You may also do a cyclic shift of the 3-cycle commutator you have to affect different positions.

A cyclic shift of the corner commutator I gave, for example, is:   R U' L' U R' U' L U (original) => U' L' U R' U' L U R, where you conjugate with the inverse of the first move (or the inverse of the last move) to not add more moves to the original commutator, but you affect different pieces (yay!)

A more useful commutator to generate more corner positions might be:   R' F' R U R2 U' R' F R U R2 U'  = [R' F' R U, R2].

Also, you can overlap two pieces from the previous 3-cycle commutator as well.  (You are not just limited to overlapping one piece of two 3-cycle commutators).
Just make sure that the very last 3-cycle you do also involves the first piece you affected (which is you have left alone after the first application of the 3-cycle to the solved cube) to "close" the cycle.

So once you have a commutator which swaps only three corners or only three edges, you can overlap each 3-cycle to obtain a higher order cycle.
If you have an even permutation, this is all you will need to do.
If you have an odd permutation (remember that both the corners and the edges cycle types will be odd permutations if one is), you need to do a 2-cycle PLL first, and then overlap that 2-cycle with a 3-cycle commutator (and overlap that 4-cycle "marriage" with more 3-cycle commutators).

And actually, I have modeled all of the 2-cycle PLL algorithms in the speedsolving wiki as commutators and conjugates.  A commutator, if you haven't caught on, is A B A' B' = [A,B] and a conjugate C of some algorithm X is C X C' = [C:X].  So you can see the decompositions of the 2-cycle PLL algorithms as commutators and conjugates (just so that you won't feel that these PLL algorithms are gibberish) if you look up the following:

Link>>Look up "Entire Set of Speedsolving Wiki 2-Cycle PLL Algorithms Decomposed" in Google.  It's the first result.

So that's all you really need to make any cycle class type with edges and with corners.  Now, you can actually shorten (optimize) the length of your products of commutators by inputting the entire sequence into an optimal 3x3x3 solver.  I recommend the following:

>>Link:  Look up "cube explorer 5.0" in Google.  It should be the first result.

**A way that might be easier is to make a high order cycle by just repeating the 2-cycle PLL over and over, sharing just one piece from the previous application of the algorithm at a time.  Of course, set up moves (and/or you can do a cyclic shift of the algorithm) in between each application.  This of course will scramble the edges if you do the corners first, or scramble the corners if you do the edges--unless you do what you ought to do if you choose to just use a 2-cycle PLL:  make sure you have the 2-cycle PLL affect the same two corners (or same two edges if you are permuting the corners first) every application by proper application of setup moves.


Just keep in mind that whether you use the 2-cycle PLLs once for an odd permutation purpose only OR if you use it as your only base algorithm, you take note of which two edges it affects (if you choose to do corners first) or viceversa.


bob bundy wrote:

RL'U

This consists of

ufr - ruf This corner stays in place but is twisted 1/3 turn so returns to its start in a 3-cycle.

ufl - rub - rbd - rdf - flu   These corners cycle in four but twisted so this is a 3x4 = 12-cycle.

ubl - bdl - dfl - lub  These corners cycle in three but twisted so this is a 3x3 =  9-cycle.

uf - ul - bl - dl - fl - ub - ur - br - dr - fr - uf  This is a 10-cycle.

df and db stay in place.

The LCM of 3, 12, 9 and 10 is 180.

So all cublets return to their start positions after 180 repeats.

Bob

This is incorrect.  We must represent the sequence R L' U as:  (urf)(ufl,rub,rbd,rdf)(dbl,fdl,ulb)(ur,br,dr,fr,uf,ul,bl,dl,fl,ub)

Which is:
[1] A 1-cycle of corners (a twist/orientation only)
[2] A 4-cycle of corners (of which some are twisted apart from their own cycle because of the Law of the cube which states that the sum of all twists must be mod 3)
[3] A 3-cycle of corners (of which ..."...")
[4] A 10-cycle of edges (permutation only)
, where [1] can have a shared orientation with [2] or with [3] AND [2] and [3] have a shared orientation.

*The cube law says that it's impossible to just have one corner twisted.  So for our case of R L' U, the urf corner's misorientation is dependent on some other corner's misorientation.


"PROOF"
Suppose that with the move sequence R L' U, ufl - rub - rbd - rdf are in a 12-cycle, since it takes 12 times of repetition to restore these corners.  Also suppose that the number of corner objects is

, because when an algorithm does a 1-cycle of a corner (twists it in its location), that algorithm must be repeated three times to restore the orientation of that corner.  (We count the number of stickers instead of the number of actual cubies).

Now, in order to compute the order of the Rubik's Cube Group, which is 43 252 003 274 489 856 000, the number of permutations which corners contribute is "only"

.

From the formula at a link I previously mentioned for calculating the number of different cycle types (first search result in Google for "Cycle classes of permutations"), we see that the number of possible 12-cycles with 24 objects (stickers) is

Note that the sum of all of the number of possible cycle classes must add up to the total number of permutations which that object contributes to the diameter of its group, and clearly only the total of one cycle class is more than

,  which is a contradiction to the order of the Rubik's Cube Group.

Q.E.D.

I could also argue (without mathematics) that your notion is false by the following example

Consider the 3-cycle corner commutator R U' L' U R' U' L U = [R, U' L' U].  [R, U' L' U]3 = the identity.
Also consider the 3-cycle corner commutator L' D R D' L D R' D' = [L', D R D'].  [L', D R D']3 = the identity.

[R, U' L' U] [L', D R D'] = [L', D R D'] [R, U' L' U], and therefore, by the results above, ([R, U' L' U] [L', D R D'])3 = ([L', D R D'] [R, U' L' U])3 = the identity.

Now what if we were to consider your argument.  Then we would assume that [R, U' L' U] is a 3-cycle because it takes 3 times of repeating it to achieve the identity.
If we twist two of the three corners it affects (with two more commutators following it):

[R, U' L' U]
(F' U' B' U F U' B U) (U R' D' R U' R' D R)  //2-corner twist

But when we repeat this 3 times, it shouldn't be solved because it's a 9-cycle now.  But ([R, U' L' U] (F' U' B' U F U' B U) (U R' D' R U' R' D R) )3 = the identity?
(we can do the same for the commutator [L', D R D'] and achieve the same result).

From this, we at least have to conclude that a disjoint 3-cycle which doesn't share an orientation with any piece outside of that cycle will stay a 3-cycle.

To verify this, let's let the two original 3-cycle corner commutators share an orientation (let's twist one corner which is in [R, U' L' U] and one that is in [L', D R D'].  It shouldn't matter which corner from each we choose.

[R, U' L' U] [L', D R D']
(D R U R' D' R U' R') (R' F L F' R F L' F')   //2-corner twist of the two front right corners.

([R, U' L' U] [L', D R D'] (D R U R' D' R U' R') (R' F L F' R F L' F')  )3

the identity, but ([R, U' L' U] [L', D R D'] (D R U R' D' R U' R') (R' F L F' R F L' F')  )9 is.


But by my "proof", that algorithm, even though it takes 9 times to achieve the identity, it is two disjoint 3-cycles which share orientation with each other, not a 9-cycle.


anonimnystefy wrote:

1) Is there an algorithm which goes through all possible cube states?

Actually there is.  Bruce Norskog found what is commonly called "The Devil's Algorithm", which is what you are asking about, earlier this year for the entire 2x2x2 cube group and the entire 3x3x3 cube group.

For The Devil's Algorithm for the 2x2x2 cube group (which might be better to look at first to understand how Bruce formats his algorithm)
>>Link:  Look up "Hamiltonian circuit for the entire 2x2x2 cube group" in Google.  It is the first result.

For The Devil's Algorithm for the 3x3x3 cube group
>>Link:  Look up "A Hamiltonian circuit for Rubik's Cube!" in Google.  It is the first result.

Last edited by cmowla (2012-06-15 08:10:50)

Offline

#22 2012-06-15 06:32:58

bob bundy
Moderator
Registered: 2010-06-20
Posts: 6,465

Re: Rubik's cube algorithm with period 5?

hi cmowla

Welcome to the forum!

You will get full membership after 10 posts.  This restriction can be annoying, but it is a precaution against spam.  I see you have easily found ways around this.

There is a lot to digest in your post and links, which will take a while to get through, but, many thanks for such a full analysis.

I was a little hurt that you described my analysis of RL'U as incorrect and then proceeded to describe exactly the same moves!

We only differ in that you don't seem to be counting a change of orientation as a necessary part of a cycle.  I am taking an n-cycle to mean that n repetitions lead back to where you started.  This is consistent with the Wolfram definition at

http://mathworld.wolfram.com/GroupCycle.html

I did this because the question was "What is the period of the algorithm R L' U?" and this can only be answered by considering orientation changes as well as permutations.

And I know the answer, 180, is correct because, after I had posted that result,  I actually carried out the 180 repetitions!

I was aware that not all divisors of N would yield cycles.  I only said it was necessary for n to divide N (Thus a 43-cycle is impossible, for example).

Thanks for posting.  smile

Bob


You cannot teach a man anything;  you can only help him find it within himself..........Galileo Galilei

Offline

#23 2012-06-15 08:07:38

cmowla
Member
Registered: 2012-06-14
Posts: 57

Re: Rubik's cube algorithm with period 5?

Thanks for the warm welcome!

Yeah, I wasn't saying that your answer was wrong.  I for some reason forgot to show that the calculation should look like:

instead of
, where we acknowledge the shared orientation between disjoint cycles by multiplying our entire result by 3, instead of saying we have cycles which don't exist on the cube.

So yes, we only differ a little.  I can see why you thought what you did, by that definition.  In fact, the movement of the "wing edges" (as well as the movable inner center pieces) of the 4x4x4 cube and larger cubes are strictly permutations and so they match that definition perfectly with no exception (too bad the 4x4x4 cube and larger cubes as a whole do not resemble groups though):  they are much easier to track than the corners and (central) edges of the 3x3x3.

Last edited by cmowla (2012-06-15 08:14:32)

Offline

Board footer

Powered by FluxBB