• Welcome to the Speedsolving.com, home of the web's largest puzzle community!
    You are currently viewing our forum as a guest which gives you limited access to join discussions and access our other features.

    Registration is fast, simple and absolutely free so please, join our community of 35,000+ people from around the world today!

    If you are already a member, simply login to hide this message and begin participating in the community!

Edge Flip and Corner twist Proof?

PalashD

Member
Joined
Apr 30, 2010
Messages
52
Location
Bhubaneswar, India, India
WCA
2009DUBE01
Does anyone know a proof for the fact that on a 3x3x3 cube always an even number of edges are flipped?[Defining flipped as the edges cannot be put to their right position in the right orientation with the <U,D,F2,B2,R,L> subgroup]

Also is there a proof for the fact that if a cw rotation of a corner is put as 1 and a ccw rotation is put as 2 and a correct orientation as 0. Then the summation of the numbers after any moves made on the 3x3x3 is always divisible by 3?
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
Does anyone know a proof for the fact that on a 3x3x3 cube always an even number of edges are flipped?[Defining flipped as the edges cannot be put to their right position in the right orientation with the <U,D,F2,B2,R,L> subgroup]

Also is there a proof for the fact that if a cw rotation of a corner is put as 1 and a ccw rotation is put as 2 and a correct orientation as 0. Then the summation of the numbers after any moves made on the 3x3x3 is always divisible by 3?
There are three different types of quarter turns considering your subgroup. Of interest we have R, F, and U. Any other turn can be considered as either a combination of one of those, reflection or cube rotation, or both, of one of the three mentioned.

U does not change the orientation of any corner or edge, based on your defined orientation scheme. R does not change the orientation of any edge, but it does rotate some corners. After the turn R has been completed, then the corner now at UBR has been rotated clockwise. The corner at DBR has been rotated counter-clockwise. The corner now at DFR has been rotated clockwise, and the corner at UFR has been rotated counter-clockwise. The sum of all clockwise twists is congruent to 0 (mod 3).

Considering the turn F it changes the orientation of all four edges on the F slice, giving 4 flipped edges based on your orientation scheme. This is congruent to 0 (mod 2). For the corners, after the F turn, UFR is rotated clockwise, DFR rotated counter-clockwise, DFL rotated clockwise, UFL rotated counter-clockwise. The sum of all clockwise twists is congruent to 0 (mod 3).

Every quarter turn either flips an even number, or no, edges. Thus it's not possible to flip an overall odd number of edges on the cube. All quarter turns that rotate corners will perform a number of clockwise twists that is congruent to 0 (mod 3). Thus it is not possible to perform an overall number of clockwise twists that is congruent to either 1 or 2 (mod 3).

Not a precise proof, but this is the basic idea.

Chris
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
Simpler proof for edges: Consider the stickers on the edges, and label each one uniquely. Now, a quarter turn of any layer on any axis does two 4-cycles of edge stickers, which is an even permutation. Every move sequence can be written in terms of quarter turns, so every move sequence performs an even permutation on the edge stickers. But flipping one edge does one 2-cycle of edge stickers, which is an ODD permutation. So no move sequence can have the effect of flipping a single edge (or an odd number of edges, since an odd number of odd permutations is odd).

Incidentally this proof works perfectly (well, with slight variations in some of the numbers I wrote) on similar puzzles, such as the Pyraminx and Megaminx.
 
Last edited:

PalashD

Member
Joined
Apr 30, 2010
Messages
52
Location
Bhubaneswar, India, India
WCA
2009DUBE01
There are three different types of quarter turns considering your subgroup. Of interest we have R, F, and U. Any other turn can be considered as either a combination of one of those, reflection or cube rotation, or both, of one of the three mentioned.

U does not change the orientation of any corner or edge, based on your defined orientation scheme. R does not change the orientation of any edge, but it does rotate some corners. After the turn R has been completed, then the corner now at UBR has been rotated clockwise. The corner at DBR has been rotated counter-clockwise. The corner now at DFR has been rotated clockwise, and the corner at UFR has been rotated counter-clockwise. The sum of all clockwise twists is congruent to 0 (mod 3).

Considering the turn F it changes the orientation of all four edges on the F slice, giving 4 flipped edges based on your orientation scheme. This is congruent to 0 (mod 2). For the corners, after the F turn, UFR is rotated clockwise, DFR rotated counter-clockwise, DFL rotated clockwise, UFL rotated counter-clockwise. The sum of all clockwise twists is congruent to 0 (mod 3).

Every quarter turn either flips an even number, or no, edges. Thus it's not possible to flip an overall odd number of edges on the cube. All quarter turns that rotate corners will perform a number of clockwise twists that is congruent to 0 (mod 3). Thus it is not possible to perform an overall number of clockwise twists that is congruent to either 1 or 2 (mod 3).

Not a precise proof, but this is the basic idea.

Chris
Nice!! Thanks!!!
 

PalashD

Member
Joined
Apr 30, 2010
Messages
52
Location
Bhubaneswar, India, India
WCA
2009DUBE01
Simpler proof for edges: Consider the stickers on the edges, and label each one uniquely. Now, a quarter turn of any layer on any axis does two 4-cycles of edge stickers, which is an even permutation. Every move sequence can be written in terms of quarter turns, so every move sequence performs an even permutation on the edge stickers. But flipping one edge does one 2-cycle of edge stickers, which is an ODD permutation. So no move sequence can have the effect of flipping a single edge (or an odd number of edges, since an odd number of odd permutations is odd).

Incidentally this proof works perfectly (well, with slight variations in some of the numbers I wrote) on similar puzzles, such as the Pyraminx and Megaminx.
nice proof!

can we extend it to corners also?
I mean a quarter turn does 3 4-cycles of edge stickers. And a corner twist can be represented as a 3-cycle of corner stickers. Now since every move sequence can be written in terms of quarter turns. It means that any permutation of the cube can be written as 3x 4-cycles of corner stickers(x being some number). And every n-cycle can be written as n-1 2-cycles. So, a quarter turn gives us 9 2-cycles of stickers(3 disjoint sets of 3 2-cycles). And a corner twist is 2 2-cycles. Can we go down that road and show something?

Also is there a proof that if there is an odd number of even-cycle of edges then there will be an odd number of even-cycle of corners also?
 
Last edited:

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
There are three different types of quarter turns considering your subgroup. Of interest we have R, F, and U.
I'd say there are just two types. Because U and R are equivalent.

U does not change the orientation of any corner or edge, based on your defined orientation scheme.
He didn't provide a scheme for corners! At least not a complete one. He only talked about cw and ccw rotations of corners but failed to consider corners moving to other places! I suggest to complete his definition by saying a corner is (mis)oriented judging by where its F or B sticker is relative to the F or B side (on it, or cw/ccw off). Don't know why you made your life hard by apparently (cause you didn't specify it either) using U/D instead.

And as always: Ryan's Theory pages are helpful.
 
Last edited:

qqwref

Member
Joined
Dec 18, 2007
Messages
7,830
Location
a <script> tag near you
WCA
2006GOTT01
YouTube
qqwref2
nice proof!

can we extend it to corners also?
Unfortunately, no. A 3-cycle of stickers is even, and if you can reach other even permutations (and other odd ones, since 3 4-cycles is odd) you can't prove that you can't reach this particular one with that technique.

I've been trying to find a good corner orientation proof that will work for many different things (cubes, megaminx, pentultimate...) but I haven't found any luck yet. The best one I know is pretty much what cmhardw said, the proof where you setup a way of measuring orientation and prove that you can't change the sum-of-twists-mod-3, but as you might imagine that is pretty cumbersome to expand to other puzzles.
 

cmhardw

Premium Member
Joined
Apr 5, 2006
Messages
4,106
Location
Atlanta, Georgia
WCA
2003HARD01
I'd say there are just two types. Because U and R are equivalent.

He didn't provide a scheme for corners! At least not a complete one. He only talked about cw and ccw rotations of corners but failed to consider corners moving to other places! I suggest to complete his definition by saying a corner is (mis)oriented judging by where its F or B sticker is relative to the F or B side (on it, or cw/ccw off). Don't know why you made your life hard by apparently (cause you didn't specify it either) using U/D instead.

And as always: Ryan's Theory pages are helpful.
Wow, Stefan I never thought of using F/B as well for corner orientation. It makes much more sense for proofs like this, and I agree it makes it easier. The reason I used U/D, and should have mentioned it yes, is that back when I used 3OP for blindfolded this is how I thought of it. I oriented edges to L/R and corners to U/D. This mental separation obviously must have become habit. I do like how oriented both corners and edges to FB makes this proof have only 2 possible turn types, we could say U and F.

Chris
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
I've been trying to find a good corner orientation proof that will work for many different things (cubes, megaminx, pentultimate...) but I haven't found any luck yet. The best one I know is pretty much what cmhardw said, the proof where you setup a way of measuring orientation and prove that you can't change the sum-of-twists-mod-3, but as you might imagine that is pretty cumbersome to expand to other puzzles.
If you temporarily switch to a nicer orientation scheme for the duration of the turn, the proof generalizes rather easily.

In the picture below, the top-right cube shows the usual reference orientations. The red arrows are the reference orientations for the places, these stay fixed. The blue circles are the reference orientations for the pieces, these get moved around when turning. The green numbers tell us how far the pieces are (mis)oriented, i.e., how far the blue circles are turned from the red arrows. That's a solved cube and we want to call a solved cube fully correctly oriented, so the arrows and circles all match, the numbers are all zero, and the orientation sum is 0. The goal of the proof is to show that it *always* is 0 (modulo 3).

But let's not use this standard orientation scheme. Let's instead use the one on the top left cube, with just UFR having a different reference orientation. Why? Cause I'm a rebel. And, more importantly, because it illustrates the whole thing better.

Then do an F turn. This moves blue circles around and the green numbers change accordingly. This step is just to get to an unsolved cube, again just to illustrate things better. But note that while the green orientation numbers change, the orientation sum modulo 3 (os%3) doesn't change.

Now... instead of doing an R turn just as quickly, let us look at it differently. For the duration of the turn, let us temporarily switch to a different orientation scheme, where the red reference orientation arrows on the right layer point to the right. This of course also changes the green numbers, as the red arrows move relative to the blue circles. And the os%3 changes accordingly (+2 here). However, and this is important, these changes in numbers only depend on how the two orientation scheme differ, how their red arrow directions differ. It is independent of the actual cube state, i.e., where the blue circles are and what the green numbers are.

In the new orientation scheme, the R turn's effect on the orientation numbers is easy to analyze. The green numbers are just moved around, they move with the pieces but don't change, they just end up at other places. What was 0122 before is 2012 now. Of course, the os%3 doesn't change either, then.

After the turn, we switch back to the main orientation scheme. As before, this changes the orientation numbers and the sum. Also as before, this does not depend on the actual state, the changes only depend on the difference of the two orientation schemes. Thus, the original os%3 of +2 is reversed, it gets -2 now.

So... overall, instead of directly analyzing the R turn, we did three substeps. The first and third each changed the os%3, but cancel. And the second doesn't change it. So overall, the os%3 didn't change. I hope it is clear that this applies not just to my slightly non-standard orientation scheme (with just an unusual URF) but also to arbitrary others. And also applies to other puzzles, e.g., megaminx. And also applies to edges, not just corners. Just think of using any arbitrary main orientation scheme to define orientations, and for each turn temporarily switching to another scheme where the red arrows all point in the same direction of the layer so that the actual turn just moves the green orientation numbers around without changing them.

 
Last edited:

PalashD

Member
Joined
Apr 30, 2010
Messages
52
Location
Bhubaneswar, India, India
WCA
2009DUBE01
So... overall, instead of directly analyzing the R turn, we did three substeps. The first and third each changed the os%3, but cancel. And the second doesn't change it. So overall, the os%3 didn't change. I hope it is clear that this applies not just to my slightly non-standard orientation scheme (with just an unusual URF) but also to arbitrary others. And also applies to other puzzles, e.g., megaminx. And also applies to edges, not just corners. Just think of using any arbitrary main orientation scheme to define orientations, and for each turn temporarily switching to another scheme where the red arrows all point in the same direction of the layer so that the actual turn just moves the green orientation numbers around without changing them.
I did not understand why you switched to a different orientation after the F turn to analyse the R turn? You could have done without it. The objective of the proof was to show that os%3 remains constant. If it is so for one orientation now if you change the orientation(reference) automatically the os%3 will change. But, now if you made a move it will remain constant as it remains constant for the normal(unchanged) reference. I mean why do you want to change the reference scheme here. Is it just because it generalizes in some way to other puzzles?

Also in a 5x5x5 why is it possible to have a single two cycle of edges?
I mean in a 4x4x4 the cube's edges and corners can be represented as

Code:
C1 E1 E2 C2
E3       E5
E4       E6
C3 E7 E8 C4
Now a quarter turn transforms this to
Code:
C3 E4 E3 C1
E7       E1
E8       E2
C4 E6 E5 C2
which is two 4-cylces of edges and a 4-cycle of corners. This is equivalent to
(E1 E5)(E1 E8)(E1 E4)
(E2 E6)(E2 E7)(E2 E3)
(C1 C2)(C1 C4)(C1 C3)

So an odd number of swaps is performed thus odd number of 2-cycles can occur

But I do not understand how this happens in a 5x5x5
There are 3 4-cycles of edges and a 4-cycle of corners.
Thus having 12 2-cycles which should not break down to a single 2-cycle but that happens in the parity case.
 

FMC

Member
Joined
Sep 29, 2010
Messages
10
But I do not understand how this happens in a 5x5x5
There are 3 4-cycles of edges and a 4-cycle of corners.
Thus having 12 2-cycles which should not break down to a single 2-cycle but that happens in the parity case.
you should also consider inner slice turns!
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
you can do a R turn(on the normal reference) and see that. No need to change the reference for that.
And then I've only shown that os%3 miraculously remains zero when doing an R turn from that particular state. I have not shown it for any other turns or for any other states, and more importantly it is not clear why it should be true for them. There'd be no explanation. But the detour through the modified orientation scheme does offer an explanation and shows why/that os%3 remains zero for all turns on all sides for all states. And it shows that it doesn't depend on the orientation scheme (e.g. UD vs FB), also explains the edges, and also explains megaminx and other puzzles. All without analyzing different cases individually (like Chris's six cases, two piece types times three turns) but by showing a single insightful idea.

Inner slice turns are the real reason for it on the 4x4x4 as well, btw. You're right that an outer layer turn is an odd permutation of edge and corner pieces, but it's an even permutation of edges. So that's not how you get the single edges swap there.
 
Last edited:

PalashD

Member
Joined
Apr 30, 2010
Messages
52
Location
Bhubaneswar, India, India
WCA
2009DUBE01
And then I've only shown that os%3 miraculously remains zero when doing an R turn from that particular state. I have not shown it for any other turns or for any other states, and more importantly it is not clear why it should be true for them. There'd be no explanation. But the detour through the modified orientation scheme does offer an explanation and shows why/that os%3 remains zero for all turns on all sides for all states.
but as chris said "Of interest we have R, F, and U. Any other turn can be considered as either a combination of one of those, reflection or cube rotation, or both, of one of the three mentioned." and as you said "U and R are equivalent." and an R or an F on a solved cube does not change os%3. Assuming n R and F moves (allowing reflections rotations in between[since they also do not change os%3]) do not change os%3. Then, if we apply another R or F then again os%3 does not change. So by Induction we can easily say os%3 is conserved. But your proof is much more elegant though it requires switching orientation.

Inner slice turns are the real reason for it on the 4x4x4 as well, btw. You're right that an outer layer turn is an odd permutation of edge and corner pieces, but it's an even permutation of edges. So that's not how you get the single edges swap there.
Since it is an even perm of edges and a odd perm of corners. Can we have 2 2-cycles of edges with the outer layers turns only[The perm parity]? I mean can I do something like (E1 E4)(E2 E3) with outer layer turns only. (E1 E2)(E3 E4) is obviously possible[Considering the pervious notation I have used].
 

Stefan

Member
Joined
May 7, 2006
Messages
7,287
WCA
2003POCH01
YouTube
StefanPochmann
as you said "U and R are equivalent."
In your original orientation scheme, properly completed. Not in mine. And again: I didn't show that F turns always preserve os%3, as I only observed the change (of green numbers and os%3) for the specific cube state. I did not, like Chris, analyze why it changed like that (how the red arrows are arranged and how any cube state is affected by an F turn). My observation of that F turn wouldn't allow any generalization, and neither would a the likewise observation of the R turn.

Since it is an even perm of edges and a odd perm of corners. Can we have 2 2-cycles of edges with the outer layers turns only[The perm parity]? I mean can I do something like (E1 E4)(E2 E3) with outer layer turns only.
No.
 
Last edited:

TMOY

Member
Joined
Jun 29, 2008
Messages
1,802
WCA
2008COUR01
you should also consider inner slice turns!
Actually, on the 5^3 an inner slice turn is an even permutation. It performs one 4-cycle of wings, two 4-cycles of x-centers and one 4-cycle of +-centers. Hence if you want to swap 2 wings you have to swap 2 +-centers as well. But since you can always apply the swap to +-centers of the same colour, ithe apparent result is just a 2-wing swap.
 

pyraminx

Member
Joined
Oct 8, 2010
Messages
3
slightly off-topic,sorry:
Is there any proof showing that a 90 degree turn of centre facelet on a 3x3x3 super cube is impossible?
can we have a general result which tells the impossible centre facelet turns an nxnxn super cube?
 

pyraminx

Member
Joined
Oct 8, 2010
Messages
3
Center orientation parity always matches corner permutation parity.
ok..if i understand well,a more general way to state this is
center orientation parity matches with corner permutation or edge permutation(correct me if i am wrong)
but how can we extend to NxNxN super cube?
first of all we should have a definition of orientation of center as the centers
also permute
 
Last edited:
Top