A little parity technique...

[qqwref]

If the number of cycles (not counting 1-cycles) and the number of solved pieces (that is, pieces that are correctly permuted) on an orbit are either both even or both odd, you don't have any parity on that orbit. Otherwise, you do have parity.

Example: imagine a 3x3 BLD solve with three edge cycles and one solved edge. Instead of counting the number of elements of each cycle, you can just see that 3 and 1 are both odd, so you know you have no parity.


Note that this only works when you have an even number of things in the orbit, but this is pretty much always true where twisty puzzles are concerned, so don't worry about the other case.

 

[hawkmp4]

Do you mean 'even number of things in the orbit' in your last sentence?

 

[cmhardw]

Wow, Michael that's a neat result! How did you go about proving this? Did you do this via induction somehow, or by contradiction? This would be a very quick and easy way to determine parity in the wing orbit of a larger cube, assuming that you do not break into new cycles when you memorize.

--edit--
O_O

If I'm not mistaken, would this easier parity check possibly be a way to determine the parity of the wing orbit for speedsolving the 4x4x4? You could perhaps merge this with my "pair wings up correctly oriented as on 3x3x3" method rather than tracing all 24 pieces. This way you only have to trace at most a 12 cycle of pieces.If you could reasonably accurately determine the parity of the wing orbit during inspection, then you could always solve the centers such that the wing parity is even, and thus never have OLL parity. What do you think?

Michael, I will try this when I get home and see if it works in practice when combined with my method. If this does, then this method of always avoiding OLL parity on every solve could finally become a reality.

Chris

 

[qqwref]

Do you mean 'even number of things in the orbit' in your last sentence?

Yes. Fixed.

Wow, Michael that's a neat result! How did you go about proving this? Did you do this via induction somehow, or by contradiction? This would be a very quick and easy way to determine parity in the wing orbit of a larger cube, assuming that you do not break into new cycles when you memorize.

I found it by observation of a pattern. But it can be basically proved like this:
parity == sum over all cycles of (cycle size + 1) (mod 2)
parity == number of cycles + sum over all cycles of (cycle size) (mod 2)
parity == number of cycles + (orbit size - solved pieces) (mod 2)
parity == number of cycles + solved pieces (mod 2) (if orbit size is even)

If I'm not mistaken, would this easier parity check possibly be a way to determine the parity of the wing orbit for speedsolving the 4x4x4? You could perhaps merge this with my "pair wings up correctly oriented as on 3x3x3" method rather than tracing all 24 pieces. This way you only have to trace at most a 12 cycle of pieces.If you could reasonably accurately determine the parity of the wing orbit during inspection, then you could always solve the centers such that the wing parity is even, and thus never have OLL parity. What do you think?

Hm. I'm not really sure what you mean by pairing wings up like on 3x3, but it would be pretty amazing if this lead to a feasable way of checking parity in inspection.

 

[cmhardw]

Hm. I'm not really sure what you mean by pairing wings up like on 3x3, but it would be pretty amazing if this lead to a feasable way of checking parity in inspection.

I wrote up a post about it a few years back on the yahoo group, but I don't remember when. I think it was around December 2005. I'll write up an example solve once I get home and have a 4x4x4 in hand. I'm wondering if we can combine my old approach with your insight (theorem?) to make a human manageable way to pull this off. It would effectively change the reduction method such that there would only be "PLL parity" or "no parity" on a solve!

Chris

 

[TMOY]

Wow, Michael that's a neat result! How did you go about proving this? Did you do this via induction somehow, or by contradiction? This would be a very quick and easy way to determine parity in the wing orbit of a larger cube, assuming that you do not break into new cycles when you memorize.

This is a very well-known and basic result about permutations. I already use it all the time for determining parities at BLD.

In fact it can be easily proved the other way round. Use the parity of the number of cycles as the definition of permutation parity and look at the effect of an elementary transposition: if both pieces are in the same cycle, the transposition breaks it in two, if they belong to different cycles it merges them. In both cases the parity of the permutation changes.

 

[cmhardw]

For tl;dr people skip to the section: "Potential Human possible method for averaging under inspection time for this method"
------------------------------------------------------

Ok, here is my original method to always avoid OLL parity. I would like to stress that this method is unreasonable for trying to average less than the allotted inspection time. Nevertheless, I think perhaps mixing the best parts of my method, as well as your theorem, we may be able to improve on my method. I am wondering if it would be possible to somehow create a method that is possible to execute during inspection.

Method to always avoid OLL parity

For the ease of everyone being able to follow along please scramble in an orientation that you normally consider "solved." For example, scramble in your normal blindfolded orientation.

Scramble: U2 L2 Rw B' F2 L2 R D2 L Rw2 F Uw2 U' L D2 Uw' B2 Fw F2 L D' Uw' U2 Fw L' Uw2 U' Rw2 Fw Rw2 Fw2 Uw U' R' Fw R Uw2 L' U2 L

Our goal is to determine the parity of the wing orbit. First let's trace all of the cycles in regular BLD fashion. Please bear with me on the notation, but for sake or brevity I will use my blindfolded lettering to do this:

(Q BX TV LE PA HW)(M CU NS KI)(F DO R)(IG)

This accounts for all 24 pieces, and clearly the parity of the wing permutation is even.

Now on how to use the parity detection method. First off, for there to be any reasonable chance of doing this method in under the inspection time we certainly do not want to trace the cycle of all 24 pieces. Instead I will define a 3x3x3 orientating scheme based around the following allowed turns:
{U, D, R, L, F2, B2}

We will start our cycle from the piece in the UBl location. The piece currently in UBl belongs in RBu. However, we do not care to send this piece to where it is supposed to go, we only want to pair it with it's neighbor edge, and also make sure that it is correctly oriented in our 3x3x3 allowed turn scheme. The piece in UBl should be paired with the piece in DFl. If DFl were a 3x3x3 edge, it would be correctly oriented. This means that we will "shoot" UBl to DFr and pair up this edge group. This would require one transposition of pieces to achieve this. We do not care how many transpositions will be required to pair up all edge groups, only whether that number is even or odd. Since we have performed our first transposition this means we have done an odd number of them. In order to mark that the total number is odd I clench my teeth together.

Clenched teeth = odd
Unclenched teeth = even

Ok, so now that we have shot UBl to DFr, we need to know where to shoot the piece currently in DFr. We are continuing the cycle basically. DFr should shoot to UBl, creating a true transposition. Notice that UBr is correctly oriented, so we can allow this cycle to finish with the transposition we applied knowing that both edge groups created would be correctly oriented. We now consider this cycle done, and look for a new cycle. Remember that teeth are still clenched, and so the total number of transpositions performed at this point is still odd.

Now start at ULf. ULf pairs with the piece in BLu. BLu is correctly oriented so we shoot ULf to BLd. This is another transposition so unclench your teeth to indicate an overall even number.

- BLd pairs with UFl. UFl is correctly oriented so shoot to UFr. Clench.
- UFr pairs with FRu. FRu is correctly oriented so shoot to FRd. Unclench
- FRd pairs with BRd. BRd is not correctly oriented so shoot to BRd then to BRu, performing a 3 cycle. This would cause you to clench and then unclench, but basically when you see an unoriented piece you do not change your teeth state.
- BRu pairs with URf. URf is not correctly oriented. Shoot to URf then to URb. Basically you saw an unoriented piece so do not change your teeth state.
- URb pairs with BDl. BDl is not correctly oriented so do the 3 cycle and do not change your teeth state.
- BDr pairs with FLd. FLd is correctly oriented so change your teeth state to clenched (shoot to FLu).
- FLu pairs with DRb. DRb is not correctly oriented. Shoot the 3 cycle and do not change teeth state.
- DRf is the piece that pairs with ULb (where we started). ULb is correctly oriented so leave teeth state unchanged.

This accounts for 11 "edges" on the cube. I would know this via the counting method described below. The 12th edge is at DL and is unoriented. This would take one transposition to flip this edge correctly, so unclench your teeth. You have now accounted for all 12 edges, your teeth are unclenched which tells you that the wings currently are in an even permutation. When solving the centers you would pay attention to single quarter turns, and use a similar approach of clenching and unclenching your teeth. You would leave your teeth unchanged when performing double turns or conjugate maneuvers such as r U r' and the like. The solving part while keeping track of parity is really not very hard, and just takes a bit of practice to get used to.

As for how I would have known that I had only counted 11 edges above when the second cycle ended here is where the method gets pretty intense. I was counting the edge groups on my feet using a base 5 system.

Ones place
Right foot relaxed = 0
From relaxed pivot foot left, keeping heel fixed = 1
From relaxed pivot foot right, keeping heel fixed = 2
From relaxed pivot foot left, keeping ball of foot fixed = 3
From relaxed pivot foot right, keeping ball of foot fixed = 4

Tens place
Left foot relaxed = 0
From relaxed pivot foot left, keeping heel fixed = 1
From relaxed pivot foot right, keeping heel fixed = 2

Using this in practice
This may sound much more intense than it is. Here is exactly how my thought process would go when tracing this method out. Keep in mind that I never was able to average under 15 seconds for this method, but I was sometimes able to do this method in under 15 seconds. These always led to solves where I was guaranteed to avoid OLL parity, and I would know this fact going into the LL.

Starting from the same scrambled state, here would be my exact thought process.

- Look at UBl, noting which piece is in UBr. Move right foot to count "1". Shoot to DFr to pair up correctly oriented. Clench teeth, move right foot to count "2"
- DFr pairs with UBr correctly oriented. Find a new buffer.
- Start at UFl. Move right foot to count "3". Shoot to BLd. Move right foot to count "4", unclench.
- Shoot to UFr. Move left foot to "1", move right foot to "0". Clench.
- Shoot to FRd. Move right foot to "1". Unclench.
- Pairs with BRd. Since BRd is unoriented move right foot to "2". Take note of the piece in BRu, as it shoots next.
- Pairs with URf. Since URf is unoriented move right foot to "3" and take note of URb.
- Pairs with DBl. Since DBl is unoriented move right foot to "4", take note of DBr.
- Shoot to FLu. Move left foot to "2", move right foot to "0". Clench.
- Pairs with DRb. DRb unoriented so move right foot to "1", take note of DRf.
- DRf belongs paired with ULb (next to our buffer). ULb is correctly oriented, so ULf would have ended up next to it correctly during our last transposition.
- My feet show a count of 11 ("2" in the tens place, "1" in the ones place. Keep in mind we are counting in base 5).
- Find that the 12th edge is at DL. This edge is not correctly oriented. 1 transposition will orient it, so unclench your teeth.

All 12 edges accounted for, teeth unclenched. This tells me that the parity of the wing permutation is even.

-------------------------------------------------------------------------------------------------------------------

Potential Human possible method for averaging under inspection time for this method

I would have traced the cycles the same way as described above. However I would completely do away with the teeth clenching and unclenching part. The feet part I would keep to count edge groups, to know whether or not I have accounted for all possible groups.

So here is the thought process I would use combining your and my methods:

- UBl pairs with DFl. DFr pairs with UBr. Count "2". I don't care whether the pieces are oriented correctly or not since I don't care about the length of each cycle, only how many cycles there are. This is using your theorem. I don't care whether each step is a transposition or 3 cycle, I simply care whether the pieces pair.

1 cycle has been completed.

Start a new cycle at UFl. Count "3"
- UFl Pairs with BLu. Count "4"
- BLd pairs with UFl. Count "5"
- UFr pairs with FRu. Count "6"
- FRd pairs with BRd. Count "7"
- BRu pairs with URf. Count "8"
- URb pairs with DBl. Count "9"
- DBr pairs with FLd. Count "10"
- FLu pairs with DRb. Count "11"
- DRf shoots back to pair with ULb where we started.

2nd cycle completes, not all edge groups accounted for as we've only counted 11.

Edge group at DL is flipped incorrectly. This would require a transposition, which is another cycle.

Thus we have 3 cycles and 0 solved edge groups. Using your theorem, since the number of cycles and the number of solved pieces are not either both even or both odd, then we do have parity in this orbit. I am interpreting the converse of your result as "If you do have parity in an orbit, then the number of cycles and the number of solved pieces are not both odd and not both even."

Clearly this does not correctly predict the result. What are the restrictions on your theorem? The reason my original method works is that I am not cycling such as to solve the pieces, but such as to reduce them to a state solvable using only outer turns. How could we somehow combine your result, and my original method, to make them work together? Is this even possible?

Chris

 

[Stefan]

Lurk moar :

You can determine during the permutation if the permutation of the edges is odd or even by counting the number of cycles of the edge permutation (an edge at its place counts as one cycle). Even number of cycles = even permutation.

 

[qqwref]

Chris: Interesting idea of wing pairing. I think the second way does not work as you write because, basically, you are defining a new solved state (which has paired edges and overall correct EO). So your problem is that you are ignoring the count of solved edges; whenever you shoot an edge to the next edge pair, if the other one is already oriented, you have to increment your count of wings in place. So in practice it would be something like this:
- Every time you start a new cycle, add one to your count for a new cycle.
- Every time you go to pair a wing, and the 2nd wing of that color-pair is correctly oriented, add one to your count for a new solved piece.
- If you see two paired wings, and they are unoriented, add one to your count for a new cycle.
So it's similar to the first method, but perhaps easier.

As for the first method you posted, no need to actually count for the number of unpaired edge pairs. Just look around the cube for them, it should be easy to notice the already-paired edges.


Stefan: I'm not at all surprised that I'm not the first person to notice this method. Indeed you'll notice that the first post doesn't call the method mine anywhere But now more people know it, which was my goal with the topic.