# 3x3x3 Permutation Theory Puzzle



## cmhardw (Jul 28, 2009)

I have an interesting (?) puzzle, and I don't know the solution to it.

For this puzzle the following rules apply for how turns must be done:
1) Only quarter turns of outer layers can be done.
2) Every turn must turn an adjacent side to the previous turn.

Following the above rules find two distinct, shortest length sequences of turns which produce equivalent permutations when applied to the same starting state, have the same number of turns, and are not inverses of each other.

In essence create two distinct sequences that have the same number of turns, start from solved and end up at the same state, yet when both sequences are concatenated in either order you do not create an identity permutation.

Have Fun!
Chris

--edit--
Here is a somewhat trivial soluton following the rules above. I don't know if this is the shortest length for the two sequences, but I doubt it.


Spoiler



This solution uses a loose definition of the term "distinct" for the two sequences in that I rotate the alg 90 degrees. I suppose to the way I wrote the puzzle that this counts though.

Sequence 1: R U R' U' R' F R F' R' F' U F U F' U' F R
Sequence 2: F U F' U' F' L F L' F' L' U L U L' U' L F


----------



## Lucas Garron (Jul 28, 2009)

Spoiler



You can make that out of any sufficiently nice QT identity.
I like R' F R F' U' R U R' F' U F U'

Makes R' F R F' U' R and (U R' F' U F U')':

Sequence 1: R' F R F' U' R
Sequence 2: U F' U' F R U'


----------



## AvGalen (Jul 28, 2009)

I state that there is no way to beat Lucas' solution!

How did you come up with this challenge Chris?


----------



## blah (Jul 28, 2009)

Lucas Garron said:


> Whatever Lucas said.


Second thing that came to my mind. (Don't worry about the first, it was a silly idea ) But I couldn't think of any identity sequence  Does using Cube Explorer count?


----------



## DavidWoner (Jul 28, 2009)

blah said:


> Lucas Garron said:
> 
> 
> > Whatever Lucas said.
> ...



You'd have better luck with ACube. Remember you can only use quarter turns, CE doesn't really have a way to sort that out.


----------



## blah (Jul 28, 2009)

Vault312 said:


> blah said:
> 
> 
> > Lucas Garron said:
> ...


I've already used CE and it did give me what I wanted so I'm good  As for ACube, I didn't use it because I suspected it wouldn't be able to give me a solution at all if I fed it a solved cube, no?


----------



## mrCage (Jul 29, 2009)

AvGalen said:


> I state that there is no way to beat Lucas' solution!
> 
> How did you come up with this challenge Chris?


 
There is shorter identity sequences, like R' D' R F D2 L D L' F' D2 but it contains half turns :fp Lucas identity sequence is fairly well known, it contains 3 easy y-commutators. A number of solutions can be based on this sequence, different splits.

However i do believe shorter is possible A proof can only be constructive

Per


----------



## LNZ (Jul 29, 2009)

You can argue the idea that a half turn is the same as two quarter turns just the fact it adds an additional quarter turn to thecount.

For example D2 = D' D' or D D, etc

So R' D' R F D2 L D L' F' D2 would be R' D' R F D D L D L' F' D D and still not have any half turns.


----------



## mrCage (Jul 29, 2009)

LNZ said:


> You can argue the idea that a half turn is the same as two quarter turns just the fact it adds an additional quarter turn to thecount.
> 
> For example D2 = D' D' or D D, etc
> 
> So R' D' R F D2 L D L' F' D2 would be R' D' R F D D L D L' F' D D and still not have any half turns.


 
Please respect the intention of the challenge, not only the wording!!
Well, D and D are not adjacent faces are they!!!??

Per


----------



## TMOY (Jul 29, 2009)

Note that your identity actually gives another 6-move solution to the challenge: D R' D' R F D and D' F L D' L' D'.


----------



## Herbert Kociemba (Jul 29, 2009)

There is no solution shorter than 6 moves for each sequence.
All nontrivial identity sequences of lenght 8 and 9 contain eight and seven square moves like R2 etc. There are no identity sequences of length 10 without square moves.
But if there would be two distict sequences a and b of length 5 each with a = b, we would have a*b^-1 = identity and a*b^-1 would have 10 moves without sqare moves or 9 moves with 1 square move or <=8 moves (depending on the last move of a and b).

EDIT: Grey out the colours of one edge cubie of a clean cube and press the "Add and Solve" button in Cube Explorer to get all identity solutions.


----------



## cmhardw (Jul 30, 2009)

AvGalen said:


> How did you come up with this challenge Chris?



I was thinking of the graph where every vertex was a possible Rubik's cube permutation and an edge between vertices means that the positions are one move away from each other on a cube.

We know some things about this graph. If you only allow quarter turns then this graph is bipartite and has 43,252,003,274,489,856,000 vertices. Also every vertex connects to 12 other vertices, so every degree is 12.

-edited for stupidity-- ^^^

Anyway, the puzzle came from trying to think of taking paths from a certain vertex, let's choose the solved state for simplicity. I was curious to find two distinct paths starting from one vertex and ending at some other distant vertex. Not only that, but I was curious of the shortest length path that did this. I thought of the quarter turn and turning adjacent faces only restriction just to make it fun.

I suppose we could reformulate the challenge to have no restrictions. We want simply two distinct sequences that are equivalent permutations, have the same number of turns, and are not inverses of each other.

--edit--
I found a solution to the new reformulation.


Spoiler



Sequence 1: R L
Sequence 2: L R



Chris


----------



## Tim Reynolds (Jul 30, 2009)

cmhardw said:


> We know some things about this graph, such that it is bipartite and has 43,252,003,274,489,856,000 vertices. Also every vertex connects to 18 other vertices, so every degree is 18.



Careful...

If every vertex has degree 18, that means you're including half turns. It's not bipartite anymore, since U2 links an even permutation to an even permutation. If you're only counting quarter turns, then it would be bipartite.


----------



## cmhardw (Jul 30, 2009)

Tim Reynolds said:


> Careful...
> 
> If every vertex has degree 18, that means you're including half turns. It's not bipartite anymore, since U2 links an even permutation to an even permutation. If you're only counting quarter turns, then it would be bipartite.



Darn, I'm upset with myself that I would make such a careless error. Edited my original post.

Chris


----------

