Online since 2002. Over 3300 puzzles, 2600 worldwide members, and 270,000 messages.

TwistyPuzzles.com Forum

It is currently Tue Apr 15, 2014 11:44 pm

All times are UTC - 5 hours



Post new topic Reply to topic  [ 34 posts ] 
Author Message
 Post subject: A question concerning parity
PostPosted: Fri Jan 24, 2014 6:13 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Dear puzzlers

lately I found an old and very intresting thread about parities.

http://twistypuzzles.com/forum/viewtopic.php?f=8&t=22201&hilit=puzzle+parities

I always wondered how a single edge-pair on a supercube can be flipped when all centers are correct.

Konrad wrote within the linked thread:
Quote:
The inner, invisible 2x2x2 is in a odd parity situation, but I would not count this.
...
When you solve a Crazy 4x4x4 you will never see this parity situation, when you have solved th inner 2x2x2.


And this is exactly the point which I struggle to understand.
"What is the "inner invisible 2x2x2" ? I thought if all centers on a 4x4x4 supercube are correctly solved that this would be identical with the correctly solved inner 2x2x2 of a Crazy 4x4x4. But obviously they are not.

Can somebody please explain the difference for me.

Best regards
Dr Twist


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Fri Jan 24, 2014 6:57 pm 
Offline

Joined: Mon Jan 26, 2009 9:00 pm
Simply put, if you do the algorithm (r, U, r') you've changed the permutation and orientation of the super centers while maintaining the inner 2x2x2.

Imagine the 4x4x4 as 64 individual cubies stacked together. The 8 center most cubies are the "invisible" 2x2x2.

_________________
Sanity is only the commonly accepted level of insanity.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Fri Jan 24, 2014 7:56 pm 
Offline
User avatar

Joined: Wed Jun 19, 2013 2:50 pm
Location: Deep in the Heart of Texas
On any even layered super cube, the entire edge group can be flipped with the centers correct, because if you only do the slice moves for the r and l moves, only one center is turned 180 degrees, which is possible to fix with the algorithm (r u r' u)x5. This means you can achieve the flipped edge with al centers correctly oriented.

_________________
For all of you that bought a KO 8x8x8: You should have bought a V8!


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Fri Jan 24, 2014 8:03 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
In short, a slice-move on a 4x4x4 performs an odd-cycle in the edge-wings which allows you to change their parity. It also performs two odd-cycles in the X-centers but two odd-cycles results in an overall even permutation. It also performs and odd-cycle in the 2x2x2 corners inside of the puzzle. Since you can't see these 2x2x2 corners it doesn't matter. If you were able to see the inner 2x2x2 corners like in the puzzles I linked to below, you wouldn't be able to make a pure permutation parity in the edge-wings.

See this post.

Also see Carl's posts here and here.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sat Jan 25, 2014 11:19 am 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Thank you very much for your explanation. I think I understand it now (at least I hope).

@ Brandon: Thank you for the links. There was really heaps of discussion about this topic. I have the feeling that you understood the concept of parity very well. That is why I want to ask/encourage you to make a youtube video about puzzle-parity. I didnt find a really good and clear one about this topic. I watched your video about commutators and you explained things so well, that this helped me a lot to develope a better general understanding of puzzles. I really like your method of teaching. You show the same concept on so many different puzzles and this helps so much to pick up the general principles behind that concept.
I could imagine that this technique would be also very good to explain the concept of parity.
I.e. some things are invisible on one puzzle and visible at another but both have effects, and so on..

So if you got time I would be happy to see a video from you about this topic. What do you think?

Best regards
Dr. Twist


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sat Jan 25, 2014 12:21 pm 
Offline
User avatar

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
Hi doctor twist, here is a more complete quote of my post:
Konrad wrote:
....As you can see on my Supercube 4x4x4, this a real parity situation. All centres are correct (I assure you, I have them correct on the other three faces, as well :) )
Image
So, all corners are correct = even number of permutations
all centres are correct = even number of permutations
edges need a single 2-cycle = odd parity

The inner, invisible 2x2x2 is in a odd parity situation, but I would not count this.
Too me, this case is an odd parity situation (I would not call it an error, though. Why should it be an error? Just a very special legal situation.)

When you solve a Crazy 4x4x4 you will never see this parity situation, when you have solved th inner 2x2x2.
I think you understand by now that the "inner 2x2x2" is a virtual construct on a normal 4x4x4 (or normal 4x4x4 Supercube). On a Crazy 4x4x4 the inner 2x2x2 becomes visible inside the circle.
If you have solved this inner 2x2x2 first - and keep it solved while you are solving the remaining piece groups - you will never see the parity of two swapped edges as in my picture above.

_________________
My collection at: http://sites.google.com/site/twistykon/home


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sat Jan 25, 2014 3:45 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
doctor twist wrote:
Thank you for the links. There was really heaps of discussion about this topic. I have the feeling that you understood the concept of parity very well. That is why I want to ask/encourage you to make a youtube video about puzzle-parity. I didnt find a really good and clear one about this topic. I watched your video about commutators and you explained things so well, that this helped me a lot to develope a better general understanding of puzzles. I really like your method of teaching. You show the same concept on so many different puzzles and this helps so much to pick up the general principles behind that concept.
I could imagine that this technique would be also very good to explain the concept of parity.
I.e. some things are invisible on one puzzle and visible at another but both have effects, and so on..

So if you got time I would be happy to see a video from you about this topic. What do you think?


There are a few video series I'd like to do but I find it really hard to present complicated subjects coherently.

There is a guy on Youtube (KevinsMath) with an 8-part video series called "Twisty Puzzle Math". The first one is here. His style of presenting with a puzzle and a pad of paper and pen is really fantastic. If you watch and fully understand the content of his 8 videos the concept of parity will come to you quite easily.

I think in order to do a really good video about a math-related twisty puzzle concept requires writing and some diagrams. My writing is so poor though it simply isn't an option. I could try typing into a textbox but I think viewers would find that tedious. Another option would be to annotate the video after the fact with Youtube's text overlays but that takes careful planning during the video creation phase. Also, the overlays don't support good markup like what I could get with TeX or even handwriting.

My next "mathy" video series will be on twisting pieces pure. I made some (re-)discoveries about a year ago than I shared with DKwan. If I die before I make them then he's on the hook for sharing them! :lol:

I would also like to make a series on how to count the total positions of various twisty puzzles. Doing that video necessarily requires the concept of parity to be covered in some depth.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sat Jan 25, 2014 7:21 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Konrad wrote:
If you have solved this inner 2x2x2 first - and keep it solved while you are solving the remaining piece groups - you will never see the parity of two swapped edges as in my picture above.


Really?!

Can someone explain why?

I really need to get my hands on one of these...


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sat Jan 25, 2014 7:24 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jared wrote:
Konrad wrote:
If you have solved this inner 2x2x2 first - and keep it solved while you are solving the remaining piece groups - you will never see the parity of two swapped edges as in my picture above.


Really?!

Can someone explain why?

The reason is encoded in this statement:
Brandon Enright wrote:
In short, a slice-move on a 4x4x4 performs an odd-cycle in the edge-wings which allows you to change their parity. It also performs two odd-cycles in the X-centers but two odd-cycles results in an overall even permutation. It also performs and odd-cycle in the 2x2x2 corners inside of the puzzle. Since you can't see these 2x2x2 corners it doesn't matter. If you were able to see the inner 2x2x2 corners like in the puzzles I linked to below, you wouldn't be able to make a pure permutation parity in the edge-wings.


If you solve the inner 2x2x2 first and then solve the outer 4x4x4, you won't run into the parity. A solved 2x2x2 is in an even permutation (zero is even) so an even number of quarter-turns have been applied to the 4x4x4 edge-wings too. You can't have a parity in the edge-wings if you've performed an even number of turns.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 4:23 am 
Offline
User avatar

Joined: Tue Feb 08, 2011 3:17 am
Location: Australia
And if you solved the inner 222, you know that `its inner 333` must have an even permutation too, because it's a fuse cube of course. :lol: Sorry, parity humour :oops:
doctor twist wrote:
lately I found an old and very interesting thread about parities.
I feel old.

_________________
1st 3x3 solve Oct 2010 (Even though I lived through the 80s).
PB 3x3 55sec Jan 2011 (When I was a kid 1:30 was speedcubing so I'm stoked).
1st 3x3 Earth (nemesis) solve Jan 2011 My You Tube (Now has ALLCrazy 3X3 Planets with Reduction)


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 10:51 am 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Burgo wrote:
And if you solved the inner 222, you know that `its inner 333` must have an even permutation too, because it's a fuse cube of course. :lol: Sorry, parity humour :oops:
doctor twist wrote:
lately I found an old and very interesting thread about parities.
I feel old.


I guess at the day when I understand this parity concept I will not only feel much older ;-) (Sorry - black humor :oops: )

Konrad wrote:
I think you understand by now that the "inner 2x2x2" is a virtual construct on a normal 4x4x4 (or normal 4x4x4 Supercube). On a Crazy 4x4x4 the inner 2x2x2 becomes visible inside the circle.
If you have solved this inner 2x2x2 first - and keep it solved while you are solving the remaining piece groups - you will never see the parity of two swapped edges as in my picture above.


Thank you very much for your explanation Konrad. I have read the concerning thread carefully but I must admit that I still struggle a little bit with the concept of hidden or virtual parts. I recognized that the small circle edges on a crazy 4x4x4 behave like the centers on a supercube, but I dont "see" or can not imagine the virtual 2x2x2 cube inside a 4x4x4 cube. And that this virtual cube is the same like the 4x4x4 center pieces on a crazy 4x4x4 cube. (I hope get this right at least). What I understand is, that the centers on a crazy 4x4x4 are behave like a 2x2x2 cube (simply 8 corners).
But I´ll keep on.. Thank so so much for your effort!

Brandon Enright wrote:
There is a guy on Youtube (KevinsMath) with an 8-part video series called "Twisty Puzzle Math". The first one is here. His style of presenting with a puzzle and a pad of paper and pen is really fantastic. If you watch and fully understand the content of his 8 videos the concept of parity will come to you quite easily.


Thank you very much for the link! I watched all 8 videos - very good and very interesting. I like his method too :-) Unfortunately he dont talks very much about parity. More about group therory. I guess this has to do a lot with he concept of parity but I am not able to transfer it on real puzzles.

BTW I found a good link which explains the concept of parity inbetween: https://www.youtube.com/watch?v=UwvhfgVDKuI
(even a child can understand this :wink: )

After that video I really understood why a puzzle like a 4x4x4 getting solved with reduction can end up in a different state like a 3x3x3 could ever be and that is why it can not be solved like a 3x3x3 from that point. But I still dont get this concept of "virtual/holographic parts"

Brandon Enright wrote:

I think in order to do a really good video about a math-related twisty puzzle concept requires writing and some diagrams. My writing is so poor though it simply isn't an option. I could try typing into a textbox but I think viewers would find that tedious. Another option would be to annotate the video after the fact with Youtube's text overlays but that takes careful planning during the video creation phase. Also, the overlays don't support good markup like what I could get with TeX or even handwriting.

My next "mathy" video series will be on twisting pieces pure. I made some (re-)discoveries about a year ago than I shared with DKwan. If I die before I make them then he's on the hook for sharing them! :lol:




I still think that your style of teaching - using gelantin brain - would help a lot to understand the concept of parity. I am not sure if writing things is really necessary - but you are the expert :-). But no matter if you doing this video or not please take care and dont die :D


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 4:26 pm 
Offline
User avatar

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
Hi doctor twist,
let's look at a Crazy 4x4x4 Type I:

Image

The pieces inside the circle represent a 2x2x2 inside the 4x4x4.
Imagine a very tricky mechanism (not existent in reality), where you can see all 64 cubies of a 4x4x4.
Let's assume transparent outer layers and a 2x2x2 cube inside. Carl would call this a "Real 4x4x4".

In a sense, the Crazy 4x4x4 I is such a Real 4x4x4 where three circle segments together represent a corner of the inner 2x2x2.
On an ordinary 4x4x4 you can see only the 64-8= 56 cubies on the surface.
Obviously, a slice turn on the Real 4x4x4, will turn four corners of the inner 2x2x2 as well.
Usually, you would solve the pieces inside the circle of the Crazy 4x4x4 first.
This means that the inner 2x2x2 is solved first.
As Brandon has explained above, a solved inner 2x2x2 means the pieces (=corners of the 2x2x2) are in an even permutation. This means that the 4x4x4 edges are in an even permutation as well and you will never see the parity as shown in my Supercube picture.

Because on an ordinary 4x4x4 there is the mechanism inside and no real 2x2x2, I talked about a virtual 2x2x2 inside the 4x4x4.

Note that you can easily get the case of two pairs of edges swapped on a Crazy 4x4x4 I, when the circles are solved.
Two edge pairs swapped mean an even permutation = two swaps within a piece group = no parity.

_________________
My collection at: http://sites.google.com/site/twistykon/home


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 4:53 pm 
Offline
User avatar

Joined: Tue Feb 08, 2011 3:17 am
Location: Australia
doctor twist wrote:
I guess at the day when I understand this parity concept..

The point of the previous thread was about understanding `what the term parity means`, when it is used to mean quite a few situations in the TP world. Some of the trick to understanding `parity`, is understanding `what it is not`.

BTW, the two most fun things about Twistypuzzling will always be: Parity and Tiny Stickers. :wink:

Konrad wrote:
In a sense, the Crazy 4x4x4 I is such a Real 4x4x4 where three circle segments together represent a corner of the inner 2x2x2.
Interesting that Carl's Real555 can be seen as an extreme way to avoid single edge flipped parity. :)

_________________
1st 3x3 solve Oct 2010 (Even though I lived through the 80s).
PB 3x3 55sec Jan 2011 (When I was a kid 1:30 was speedcubing so I'm stoked).
1st 3x3 Earth (nemesis) solve Jan 2011 My You Tube (Now has ALLCrazy 3X3 Planets with Reduction)


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 6:09 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
doctor twist wrote:
BTW I found a good link which explains the concept of parity inbetween: https://www.youtube.com/watch?v=UwvhfgVDKuI (even a child can understand this :wink: )

I watched the first portion of this video. I thought using his son was rather cute. Unfortunately when he got to the 3x3x3 he was so fast and loose with the terminology that his descriptions and explanations are not technically correct. For example, the way he treats the 4-cycle in the corners and 4-cycle in the edges would only work if they were in the same orbit.

So, I reluctantly made my own video introducing the concept of a permutation parity. I borrowed the idea of flipping glasses for the introduction.

I have a second video coming that extends the parity concept to some other puzzles like the 4x4x4.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 7:17 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
Excellent video Brandon! 100% accurate and topics introduced in exactly the right order! (would have liked an earlier introduction to permutation parities but not bad at all as is)

The comparison with the Curvy Copter is 100% accurate however it seemed a bit more confusing than it was worth especially when you used it as an indicator of the parity of the Rubik's Cube corners. This analysis requires mastery of moving the corners freely on a Curvy Copter (not difficult but possibly overwhelming for some newer solvers who cannot quite ignore the orientation of the corners or the permutation of the other pieces around them which are of course becoming thoroughly scrambled) as well as the ability to recognize global orientation of the Curvy Copter (again, not too challenging but you have to know exactly what to look for and it's easy to make mistakes, isn't it? :P ).

You mentioned that the edge and corner parity on a Rubik's Cube are linked, but I would have liked a bit more emphasis on that. This is the first non-trivial result from your parity analysis on a Rubik's Cube and I think stressing what this means is more important than trying to identify the parity of the corners in a scrambled state by using the Curvy Copter indicator trick.

i.e. You can either view this as: the edges can be in either even permutations or odd permutations but the corners must be in a permutation of the matching parity -OR- the corners can be in either even permutations or odd permutations but the edges must be in a permutation of the matching parity. You could also explain how this factors into the calculation of the number of states for a 3x3x3 AND why multiple expressions can be considered correct(accounting for edges or corners first, etc.)

One other thing I like to do when I'm explaining parity to people in person is to start with a solved Rubik's cube and say out loud the parity as I scramble it by quarter turns "odd, even, odd, even..." and then solve it in any manner, continuing to say out loud the parity "even, odd, even, odd..." and point out that upon solving the count will ALWAYS end on even. This at least gives some tangible proof that the parity is being tracked by the mathematics of the puzzle even throughout the messiness of the scramble. (Warning: remember a half turn is TWO quarter turns so the parity after a half turn is NOT changed - you wouldn't want to trip up and end on odd during a live demonstration :wink: )

The parity analysis between a Rubik's Cube and a Void Cube (and the related slice-turn analysis) was mentioned but be careful how you explain it. The math does not break down if you allow slice moves, but global orientation may need to be addressed - you should also probably introduce the concept of global orientation on puzzles where it cannot be determined from a scrambled state (ie: non-curvy Helicopter Cube: all 24 orientations are solvable)

Still an excellent video. If any twisty puzzler wants to really understand this magical thing called "parity" better, I highly recommend Brandon's video. He KNOWS what he's talking about 8-)

I look forward to watching part 2 :D

Peace,
Matt Galla


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 7:49 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Thanks you Matt for the shining endorsement :D I agree with your criticisms. I was trying to make the video casual and approachable while still being technically accurate. I did let myself get a bit hand-wavey with the Void Cube. I deliberately avoided using a Skewb because I didn't want to have to explain how it's possible to have two Skewb centers swapped (ignoring whatever position the corners are in).

Eventually I'd like to tackle some of the concepts of parity and the relationship between pieces and global orientation on other puzzles in more depth. I'd especially like to make a video series on how to compute the total number of positions of various puzzles and discuss some of the odd gotchas that you can run into.

In the mean time, I made a second video where I discuss the 4x4x4 and 5x5x5. Unfortunately even though my brain didn't get mixed up with the terminology, my mouth did a few times. This is especially obvious when I'm talking about the 5x5x5 where for some reason I just couldn't seem to use the right names for the pieces and said "cycle" instead of "permutation" several times. The relationship between the pieces, especially on the 5x5x5 get rather complicated and I think a diagram how relationships between the permutation parities would go a long way towards making things clearer.

So, while my second video isn't all that great, these are definitely topics I'd like to revisit in a lot more depth. When I do, I'll plan them out much better and actually make a script so that I use the right terms at all times and I don't forget to mention things.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 7:53 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Brandon Enright wrote:

So, I reluctantly made my own video introducing the concept of a permutation parity. I borrowed the idea of flipping glasses for the introduction.

I have a second video coming that extends the parity concept to some other puzzles like the 4x4x4.


WOW Brandon!! Your video is really awesome. I think in the last 2 days I learned more about parity than I found out by myself in the last year. I didnt know that it is possible to check the parity (odd/even) of a 3x3x3 with a curvey copter. This is so cool 8-)!
Is there a similar trick to check the parity of a 4x4x4? I am really looking forward to see the next video. Keep on... :D

@ Konrad:
After studying your example with the crazy 4x4x4 type 1, it fells like scales from my eyes! Thank you so much!If I understand you right, then it should be possible to get a single flipped edge-pair on a crazy 4x4x4 if I dont solve the inner 2x2x2 (that would be the converse argument to your explanation). This is what I tried. I solved my crazy 4x4x4 (type2) three times ignoring the inner 2x2x2 (I simply left it scrambled). So I started to solve the "triangular ring-pieces" first (which I guess are the correspondance to the center pieces of a 4x4x4 supercube), then paired the outer edges and then solved the cube like a 3x3x3. Unfortunately I never get a single edge pair flipped. I think this is just "bad luck" but it should be possible, or??


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 8:21 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
doctor twist wrote:
I didnt know that it is possible to check the parity (odd/even) of a 3x3x3 with a curvey copter. This is so cool 8-)!
Is there a similar trick to check the parity of a 4x4x4?
I'm not aware of any simple analogous puzzles or tricks that would help you with the parity of the edge-wings. You could track the parity by hand but it would be pretty painstaking to do.

Fortunately, the parity analysis still helps you. When you run into a situation where the parity of the edge-wings needs to be changed, the analysis tells you exactly how it happened and how to fix it.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 8:41 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
Brandon Enright wrote:
In the mean time, I made a second video where I discuss the 4x4x4 and 5x5x5.

So, while my second video isn't all that great, these are definitely topics I'd like to revisit in a lot more depth. When I do, I'll plan them out much better and actually make a script so that I use the right terms at all times and I don't forget to mention things.


OMG! This video is great! I really feel enlighted! Up to now I thought that "parity" is more a special case which can happen from time to time or is just relevant for special puzzles. You know, I read so many times things like "there is a parity situation on this puzzle or a parity error, or something like how one can avoid parity, etc." Now I know that the concept of parity is a sort of universal key to understand how puzzles work. Parity can not be avoided :-). A puzzle has a parity in any state - right?. The important thing is how to find out which parity situation you have (odd/even) and which are the consequences of this in a certain puzzle. You teached us how to analyze the pieces and their permutations which is great! I think if one really internalized the concept of parity than one have the capability to analyze and to understand anything whats going on on any puzzle.
Probably it will take a lot of time and energy to achieve this understanding but I have the feeling that this is the point where the real thing starts. It is so funny! I thought I understand what is going on on a 3x3x3 cube. You showed me that there are so many things on this "simple" cube which I did not understand or not even considered to observe.
Thank you so much for sharing your knowledge. I am really looking forward to see the sequel...

Cheers - Dr. Twist


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Sun Jan 26, 2014 9:05 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
doctor twist wrote:
Up to now I thought that "parity" is more a special case which can happen from time to time or is just relevant for special puzzles. You know, I read so many times things like "there is a parity situation on this puzzle or a parity error, or something like how one can avoid parity, etc." Now I know that the concept of parity is a sort of universal key to understand how puzzles work. Parity can not be avoided :-). A puzzle has a parity in any state - right?.
Yep! The pieces of a puzzle always have some parity associated with the permutation they are in. It's always either even or odd. Normally when you look at a puzzle and you make turns, you can't tell if the pieces are in an even or odd permutation and it doesn't matter.

It's only when you get down to the last few pieces where the parity becomes apparent. On the 4x4x4 when you get down to the last few edge-wings it becomes obvious what parity they have. If they have an even parity then you don't run into any issue and if they have an odd parity, you have to change their parity to even before continuing to solve. This can sometimes be a problem if changing the parity of the pieces back to even breaks pieces you've already solved. I think this is where the "error" name comes from. On a 2x2x2 cube for example, when you're solving the last layer you can have two corners swapped and nobody calls this a "parity error" because to fix it you just do a quarter-turn of the last layer and continue solving. It doesn't break any already-solved pieces so nobody notices when it happens.


doctor twist wrote:
The important thing is how to find out which parity situation you have (odd/even) and which are the consequences of this in a certain puzzle. You teached us how to analyze the pieces and their permutations which is great! I think if one really internalized the concept of parity than one have the capability to analyze and to understand anything whats going on on any puzzle.
Well I haven't covered every concept related to parity. There are some interesting tricky puzzles out there!

doctor twist wrote:
I thought I understand what is going on on a 3x3x3 cube. You showed me that there are so many things on this "simple" cube which I did not understand or not even considered to observe.
A 3x3x3 really is extraordinarily complicated. The depth of theoretical topics and math related to the puzzle is truly staggering.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 12:24 am 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Have I misunderstood the parity of the 4x4x4 all this time? I always thought that odd situations were because of the hidden middle layer of the 5x5x5 that's missing. In fact, I explained it to a friend that way... but it's really because of the internal 2x2x2?


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 12:45 am 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jared wrote:
Have I misunderstood the parity of the 4x4x4 all this time? I always thought that odd situations were because of the hidden middle layer of the 5x5x5 that's missing. In fact, I explained it to a friend that way... but it's really because of the internal 2x2x2?
Well, neither and both.

Take a Super 5x5x5 for a moment. The parity in the edge-wings is linked to the parity of the +centers. If you reduce the +centers and X-centers on the Super 5x5x5, you will have also, without realizing, restricted the edge-wings to even-permutations only. Because the parity of the two are linked, reducing the centers first allows you to avoid an odd permutation where you need to swap two edge-wings.

Now take a Crazy 4x4x4 I which has the inner 2x2x2 visible. The parity in the edge-wings is linked to the parity of the 2x2x2 corners. If you solve the inner 2x2x2 on the Crazy 4x4x4 I, you will have also, without realizing it, restricted the edge-wings to even permutations only. Because the parity of the two are linked, solving the inner 2x2x2 first allows you to avoid an odd permutation where you need to swap two edge-wings.

The parity of the 4x4x4 edge-wings is not because these are missing. It's just that none of the pieces on the puzzle give you a guide to their parity so you don't find out what permutation they are in until you've almost solved all of them.

You could actually avoid the parity issue altogether by simply counting how many quarter-slice-turns you do in the scramble and then counting how many you do in the solve. If you do an odd-number in the scramble you must do an odd-number in the solve. If you do an even number, then you solve with an even number. You wouldn't even have to count. You could just say even, odd, even, odd, etc.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 4:26 pm 
Offline
User avatar

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
Konrad wrote:
...
Note that you can easily get the case of two pairs of edges swapped on a Crazy 4x4x4 I, when the circles are solved.
Two edge pairs swapped mean an even permutation = two swaps within a piece group = no parity.


Image

Just to show a picture for the case I mentioned yesterday and that should not be called a "parity".
Everybody, who followed this thread and had a look at the very good videos made by Brandon, will agree on what puzzlers call a parity (or odd parity). (A state where an odd number of piece swaps is needed to arrive at the solved state for that piece group.)
Some people have called the state in my picture above a "parity". If you view the 4x4x4 as an reduced 3x3x3 we would have an odd parity of the 3x3x3 edges - impossible on a real 3x3x3. As the puzzle happens to be a 4x4x4, we se that two swaps of two 4x4x4 edges are necessary, an even count of swaps = even parity.
(Solving this situation on a Crazy 4x4x4 I, you need a move sequence that does not destroy the inner 2x2x2. Same sequence as on a 4x4x4 Supercube for two pairs of edges swapped.)

Here is a picture of a "parity of the edge wings":

Image

As you can see the corners of the inner 2x2x2 have made a single quarter turn L. They have made a 4-cycle = odd permutation.

_________________
My collection at: http://sites.google.com/site/twistykon/home


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 5:17 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Konrad wrote:
Konrad wrote:
...
Note that you can easily get the case of two pairs of edges swapped on a Crazy 4x4x4 I, when the circles are solved.
Two edge pairs swapped mean an even permutation = two swaps within a piece group = no parity.

[...]
Some people have called the state in my picture above a "parity". If you view the 4x4x4 as an reduced 3x3x3 we would have an odd parity of the 3x3x3 edges - impossible on a real 3x3x3. As the puzzle happens to be a 4x4x4, we see that two swaps of two 4x4x4 edges are necessary, an even count of swaps = even parity.
I usually call this situation a "parity in the reduced groups". That is, as you point out, this situation isn't a parity in the permutation of any of the pieces on the 4x4x4. In the process of reducing the puzzle to a 3x3x3 though, it does form a parity of the pseudo-3x3x3 edges.

The process of solving a 4x4x4 via reduction puts the puzzle into a state that's a subgroup of the 4x4x4 and isomorphic to the 3x3x3 group. With the appropriate caveats I think it's accurate to call the position you show a "parity" given that the use of the word "parity" for an odd-permutation of the edge-wings is on a 4x4x4 is already somewhat imprecise.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 7:15 pm 
Offline

Joined: Mon Aug 18, 2008 10:16 pm
Location: Somewhere Else
Can the word "parity" also apply to situations where instead of having two sets of states (even/odd), there are three? (3k/3k+1/3k+2)

Though I can't think of any puzzles that have this sort of restriction off the top of my head...


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Mon Jan 27, 2014 7:27 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
Jared wrote:
Can the word "parity" also apply to situations where instead of having two sets of states (even/odd), there are three? (3k/3k+1/3k+2)

Though I can't think of any puzzles that have this sort of restriction off the top of my head...

Uhh well yes and no. The term "parity" only applies to even-odd situations. It can't be extended to restrictions where there are more than two states.

Warning: I'm about to use terms like "overall twist" and "twist state" that I've mostly made up.

However, if you're asking "Do puzzles have situations where restrictions or states come in three or more values?" then the answer is yes! "Twist" is one of them. For example, on the Rubik's cube, the sum of the twist of all corners is constant at all times (usually defined to be zero). This is usually described casually as "you can't twist a single corner". If you take apart the puzzle though, there are two additional states you can put the twist of the corners into though. That is, no legal move on the Rubik's cube can alter the twist of the corners so of all of the states you'd think they could reach, they can actually only reach 1/3rd of them.

The same is true of edges only it's 1/2 so you could conceivable us the term "parity of the edge twist states" or something similar.

The same is NOT true of the centers. Centers can be in 4 twist states. However (and this is quite interesting!), the overall twist state of the centers is restricted by the parity of the edges and corners. That is, on the Rubik's cube, the permutation parity of the edges and the corners are linked and they're both also linked to which twist states the centers can be in. When the edges are corners are in an even-permutation, the overall center twist can only be 0 or 2 and when the edges and corners are in an odd permutation the overall center twist can only be either 1 or 3. This is usually described as "you can't twist a single center 90 degrees".

For puzzle like the Megaminx and Pentulmitate, there isn't any restriction on center twist. For puzzles like the Multidodecahedron though, the overall twist of the Megaminx centers is linked to the overall twist of the Master Pentultimate centers. The overall twist of these centers can take on 5 twist states.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 6:10 am 
Offline
User avatar

Joined: Thu Sep 17, 2009 6:07 am
Location: Germany, Bavaria
Brandon Enright wrote:
Konrad wrote:
...
Note that you can easily get the case of two pairs of edges swapped on a Crazy 4x4x4 I, when the circles are solved.
Two edge pairs swapped mean an even permutation = two swaps within a piece group = no parity.
[...]
Some people have called the state in my picture above a "parity". If you view the 4x4x4 as an reduced 3x3x3 we would have an odd parity of the 3x3x3 edges - impossible on a real 3x3x3. As the puzzle happens to be a 4x4x4, we see that two swaps of two 4x4x4 edges are necessary, an even count of swaps = even parity.
I usually call this situation a "parity in the reduced groups". That is, as you point out, this situation isn't a parity in the permutation of any of the pieces on the 4x4x4. ....
I agree with your wording. Still, I find it crucial to add "in the reduced group".
I find it confusing just to talk about "parity" - without giving more context, why the term is used - in the case of a 2-2 swap of 4x4x4 edges.
Such usage may lead straight to calling any strange situation a parity - and I do not like this. :roll:
(E.g. a 3-cycle of identically looking pieces is often perceived as seeing a single swap of these pieces and called a parity. I wouldn't)


I assume that nobody would call the following situation a "parity":

Image

It just never happens in the usual course of a reduction solve, so, it is not recognized as strange.
Still, it can be called a "parity of reduced 3x3x3 centres". :wink:

_________________
My collection at: http://sites.google.com/site/twistykon/home


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 1:04 pm 
Offline
User avatar

Joined: Mon Feb 27, 2012 10:57 am
Location: In my study drooling over my puzzle hoard - Precioussssss!
I do find this a fascinating discussion which mostly goes way over my head.
Obviously much of what we say is parity needs to be defined properly.
Ultimately it comes about because it is impossible in most, if not all, twisty puzzles to end up in a position which requires a simple swap of just 2 pieces. If it appears that this is required then the reality is that there are more moves to be done than just those 2. Brandon's video using beakers is particularly good at illustrating these impossible to reach scenarios.

BUT I personally don't think in terms like this, as by and large, I do not find it useful in my solving.
I tend to call something a parity in 2 possible situations:

  1. The commonest occurs when we approach a bigger/more complex puzzle by reducing it to a smaller and simpler one. The classic being solving the 4x4 by reduction to a 3x3. In carrying out this reduction (i.e. reconstituting the double edges into a large single edge) it becomes possible to create a 3x3 with piece positions that are absolutely impossible in a normal 3x3. In order to resolve this "parity" any approach/algorithm needs to dismantle one (or more) of the double edges and recreate them the other way around. In general the single flipped edge problem on the 4x4 is caused when 1 double edge needs to be dismantled and reformed and the other parity which can manifest as 2 swapped edges or 2 swapped corners requires 2 double edges to be reformed.
    This can be completely prevented by performing a corners first solution process or even more fun as I suggested on Facebook to a group of friends, by reducing a 4x4 to a 2x2 and hence avoiding matching edges incorrectly in the first place.

  2. My other parity situations occur again when the puzzle appears to be in an impossible situation for the 'base puzzle' to be in. This scenario can occur when there are pieces of the puzzle that look identical and hence can be swapped (e.g. void cube centres or mastermorphinx centre pieces) - these, I refer to using the original term I got from SuperAntonioVivaldi as a "Parity of false equivocation" Occasionally this is less obvious there are odd occurrences which appear to be a parity because a hidden internal part is incorrectly placed e.g. the hidden inner 3x3 part of a cross cube or the new Moyu Evil eye puzzles. This is not truly a parity but appears to be one (i.e. require a single swap of 2 pieces)

_________________
Kevin
Hopelessly addicted to puzzles!! :oops:
Visit my blog: Puzzlemad


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 1:28 pm 
Offline
User avatar

Joined: Thu Dec 02, 2004 12:09 pm
Location: Missouri
Great discussion and great first video Brandon. I still need to watch the second one :( but I'm sure its great too. Not being a great solver, I've never looked this close at the subject of parity and this is proving very interesting. This discussion remind me of the Checkerboad and Domino problem. It's talked about here:

http://www.theproblemsite.com/slickmath/checkerboard_domino.asp

Would it be fair to say this is an application of parity? Or is this something else? I comes in handy in several polyomino packing problems. I've always considered this parity related but I'm not so sure any more.

Can parity be applied to produce anything interesting on a Pyraminx? Starting from a solved Pyraminx I see how one can return to the solved state with either an even or an odd number of turns. Does that property kill the usefullness of parity for this particular puzzle?

Curious,
Carl

_________________
-
Image

Image


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 2:30 pm 
Offline
User avatar

Joined: Thu Dec 31, 2009 8:54 pm
Location: Bay Area, California
wwwmwww wrote:
This discussion remind me of the Checkerboad and Domino problem. It's talked about here:

http://www.theproblemsite.com/slickmath/checkerboard_domino.asp

Would it be fair to say this is an application of parity? Or is this something else?

That is really slick! I do think it's related to a concept of parity. Allow me to explain using the parity as the central concept:

First, a checkerboard can be defined in terms of parity. Layout a two-dimensional grid of squares. Assign squares a monotonically increasing integer index for both their x coordinate and their y coordinate. Color squares where the parity of their x coord matches the parity of their y coord white. Color all other squares black.

For the proof that removing opposite corners from a square is the same color, define the opposite corner as x + n, y + n. Then if x + n is a different parity than x, then so will y + n. Therefor the relationship in the parity of the new coordinates stays the same and so will also stay the same color per the definition of the checkerboard.

For the proof of impossibility in the solution, define the parity of the white squares to parity of the number of white squares occupied by a domino. Do the same for the black squares. Then it's trivial to show that adding 1 domino changes both the parity of the white squares and black squares and that the parity of the whites and blacks remains linked when adding or removing dominos. Now, with 31 instead of 32 dominos the parity of the black and white must change but the removal of two squares from opposite corners doesn't change the parity of either the whites or the blacks.

_________________
Prior to using my real name I posted under the account named bmenrigh.


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 3:08 pm 
Offline
User avatar

Joined: Wed May 13, 2009 4:58 pm
Location: Vancouver, Washington
wwwmwww wrote:
This discussion remind me of the Checkerboad and Domino problem. It's talked about here:

http://www.theproblemsite.com/slickmath/checkerboard_domino.asp

Would it be fair to say this is an application of parity? Or is this something else?
Your domino problem reminds me of another problem that uses a similar logic.

Imagine you have a set of the 7 tetrominos (the tetris pieces). Can you arrange then into a block of 4x7 squares?

The answer is no. If you'll color the 4x7 area in a checkerboard pattern and put pieces on it, you'll notice that all the pieces except the T shape will cover 2 white and 2 black squares. The T shape will instead cover 3 of white and 1 black or vice versa. Because of this imbalance you can never cover a 4x7 area which will have 14 white and 14 black squares.

_________________
Real name: Landon Kryger


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Tue Jan 28, 2014 5:26 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
wwwmwww wrote:
This discussion remind me of the Checkerboad and Domino problem. It's talked about here:

http://www.theproblemsite.com/slickmath/checkerboard_domino.asp

Would it be fair to say this is an application of parity? Or is this something else? I comes in handy in several polyomino packing problems. I've always considered this parity related but I'm not so sure any more.

Curious,
Carl


I think the concept of parity is a very useful tool for not only classical chessboard problems but for all nxn checkerboards (or puzzles).
I had the idea to use parity to proof that the number of white and black squares on a nxn checkerboard are the same or if they differ from each other.

I.e.: Lets assume any nxn checkerboard and let n be an odd Integer.

Then you could say: As n is a odd number I can also write it as n=2m+1. So far so true :-)
(m must be any Integer or 0).

To describe my checkerboard I can write:

n^2 = (2m+1)^2 = 4m^2 + 4m + 1 = 2(2m^2 + 2m) + 1

That proofs, that also the number of squares on my checkerboard are odd.
So I know that on a nxn checkerboard with n is a odd number, the number of white and black squares differ always in 1.

This knowledge helps to solve many problems of that kind.

But you can not solve any related problem only using parity properties I guess.
What for example if I want to know if I can tesselate a 10x10 checkerboard with 1x4 Dominos?? I think with the parity concept alone I could not answer this question, or? But maybe if I combine it with the technique of coloration (if I use 4 colors and not 2 like in a regular checkerboard it could work. But that is cheating, or? :-) )
But that goes beyond of scope of this forum :-).

I just want to add this small example, because I am really fascinated how useful the concept of parity is for solving (and understanding) complicated problems.

@ Brandon: Your videos are really really really good. I will check your channel now frequently

Happy puzzling
Dr. Twist


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Fri Feb 07, 2014 7:58 pm 
Offline

Joined: Tue Jun 11, 2013 12:48 pm
BTW: Does anybody know a supercube safe single dedge swap algorithm for a 4x4x4 puzzle?


Top
 Profile  
 
 Post subject: Re: A question concerning parity
PostPosted: Fri Feb 07, 2014 10:32 pm 
Offline

Joined: Sun Oct 08, 2006 1:47 pm
Location: Houston/San Antonio, Texas
doctor twist wrote:
What for example if I want to know if I can tesselate a 10x10 checkerboard with 1x4 Dominos?? I think with the parity concept alone I could not answer this question, or? But maybe if I combine it with the technique of coloration (if I use 4 colors and not 2 like in a regular checkerboard it could work. But that is cheating, or? :-) )
But that goes beyond of scope of this forum :-).


Did you pick this setup on purpose? :wink: You can indeed prove that it is impossible to cover a 10x10 board with 1x4 "dominoes". If you color the board with 4 colors in this way, you'll see that every 1x4 piece covers exactly one square of each color regardless of where it is positioned on the board or whether it is horizontal or vertical.
Attachment:
10x10 Board 4 Colors.png
10x10 Board 4 Colors.png [ 3.97 KiB | Viewed 822 times ]

However, there are not the same number of every color. There are 24 Blues, 25 Reds, 25 Yellows, and 26 Greens. Guess what colors will be left in the best case scenario after placing 24 1x4 dominoes?

There is not always an argument like this for every problem, and I do not know of any officially named mathematical concept of a more than 2 "parity", but that doesn't mean no such argument can be made for certain problems with a property that can take on more than two states. Some topics of math introduce "sign functions" or "indicator functions" for particular problems. These are defined on the spot for the specific problem, and then it is proven that some property of the function is unchanged for some object under some operations pertinent to the problem. Thus by recursion, applying the operation(s) multiple times on the object will never change the property of the function. If the "goal" state of the object does not result in the same property when passed through the sign function, then by contradiction it is possible to prove such a goal state can never be reached with the operations. Proofs of this form are very dependent on the exact sign function, and it is usually difficult to define a general function that adapts to every problem, though it seems parity of a permutation comes up often enough that has a recognized name.

Jaap has also used 3 colors to analyze many things about Peg Solitaire for some amazing results. His first example also demonstrates how things can get messy. Starting with a red square empty he shows that the last peg must end in a red square. However it cannot end in ANY red square. He explains you can also mirror the coloring to get the exact same analysis with a different result. Using the same starting hole, you reach a different set of potentially ending pegs. Nothing is wrong with either analysis - they both prove that the peg cannot end in the other squares, but neither proves that it is possible to end with the peg in any of the remaining squares. By combining both, you can narrow your results down further and show that there are very few places where the final peg can end up, but it still doesn't prove that all of these endings are possible. In general these types of proofs don't reveal a lot about what is possible, but they are VERY good at proving what is impossible. This is also true for many applications of parity. Ok that was fun, but this is getting dangerously close to off-topic. I'll stop :D

Peace,
Matt Galla


Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 34 posts ] 

All times are UTC - 5 hours


Who is online

Users browsing this forum: No registered users and 3 guests


You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum

Search for:
Jump to:  

Forum powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group