Only half of the permutations are reachable. An impossible state

[Herbert Kociemba]

Since each quarter turn is an even permutation you can achieve at most all even permutations of corners and edges. But it is not obvious at all that you can achieve all even permutations (what indeed is the case). So that you can do a single edge swap together with a single corner swap (which is an even permutation) is not trivial per se.

 

[swipymam]

Any decent computer solver checks the corner parity and edge parity in advance to look if a cube is solvable. Both parities have to be both even or both odd. Look for example in https://github.com/hkociemba/RubiksCube-TwophaseSolver/blob/master/cubie.py for the functions corner_parity (line179) and edge_parity (line188) for possible implementations.

One can also ask: if the parity of the corners and edges does not change with any rotation of the faces, then how can it become odd? When you talk about odd, do you mean some mathematical transformations?
As far as I understand, the explanation is one post above this post of mine?

 

[Herbert Kociemba]

One can also ask: if the parity of the corners and edges does not change with any rotation of the faces

It changes with each quarter turn for edges and for corners, but simultanuously which makes the overall parity always stay even.

 

[swipymam]

It changes with each quarter turn for edges and for corners, but simultanuously which makes the overall parity always stay even.

Sorry for being annoying, but if at each rotation of the face the parity of both the corners and the faces remains even (%2=0), where does the oddness come from? Or did I misunderstand you?

 

[bcube]

It is solvable of course! But the reason is because there is an even amount of swaps, there are 2 swaps, one corner swap and one edge swap as you said

I beg to differ, I claim you can not solve that state (example no. 5).

But in Swipymam's first message it was an in even amount of swaps, there is 1 edge swap, and so it's unsolvable

In my example no. 1 it looks like there is 1 edge swap, yet I claim I can solve it.

As a sidenote, in examples no. 2 and 3 there is 0 edge swap and 0 corner swap, yet I claim that one state is solvable and the other one is not. That is why I wrote this post.

 

[Renslay]

Think about it this way:
A solved cube has even parity on edges and even parity on corners. Let's call this "even-even".
After one quarter turn, this even-even turns into odd-odd (meaning: the parity of edges is odd AND the parity of corners are odd too).
Another quarter turn, and it changes back to even-even.
And so on and so forth.
Each quarter turn changes both parities simultaneously.
Even-even, odd-odd, even-even, odd-odd, even-even, odd-odd, and so on.

When you swap two edges but leave the corners, that changes the parity of edges, BUT not the corners. So, your edge-corner parity is either even-odd, or odd-even. Since every quarter turn changes BOTH parities, the sequence you have now with subsequent turns are:
even-odd
odd-even
even-odd
odd-even
And so on... No matter how you turn the cube, this mismatch will stay forever - you cannot go back to the solved state, which has a parity of even-even!

And this proves that swapping two edges only is impossible to solve.

A similar argument works for swapping two corners only.

As Kociemba mentioned, swapping both edges and corners can work; we cannot immediately show that why it can't, but it requires further proof.

 

[swipymam]

After one quarter turn, this even-even turns into odd-odd (meaning: the parity of edges is odd AND the parity of corners are odd too).
Another quarter turn, and it changes back to even-even.

This is a false statement.

With each rotation, the sum of the parities of all angles does not change - it remains even, just as the sum of the parities of all edges also remains even.
(And therefore there is no point in comparing the sum of the parities of all angles with the sum of the parities of all edges).

 

[Renslay]

This is a false statement.

With each rotation, the sum of the parities of all angles does not change - it remains even, just as the sum of the parities of all edges also remains even.
(And therefore there is no point in comparing the sum of the parities of all angles with the sum of the parities of all edges).

Please explain what do you mean by "sum of the parities of all angles" and "sum of the parities of all edges" (I actually don't know what do you mean by these). I think you do not understand what a parity of a permutation means.

And my statement is true.

Let's number all the edges from 1 to 12 in such a way that UF=1, UL=2, UB=3, UR=4, and so on.
The solved cube has the following edges in this order:
1 2 3 4 5 6 7 8 9 10 11 12
If you apply a U turn, that permutes the numbers 1, 2, 3, and 4 around:
4 1 2 3 5 6 7 8 9 10 11 12
This is an odd permutation, that can also be written with a permutation cycle (1 2 3 4)(5)(6)(7)(8)(9)(10)(11)(12).
(This means 1 went to the place of 2, 2 went to the place of 3, 3 went to 4, and 4 back to 1; the rest of the elements stayed.)
Here, you can check the parity yourself:

Permutation calculator

Edit: if you have trouble understanding what "parity of a permutation" means, maybe this help, there are a lot of good answers:

What is parity of permutation in simple words?

Answer (1 of 2): OK, let’s play a game! We have there a merry band of 5 very smart toads, each of them wearing a cute hand-knitted jersey, with a bright red number on the back: 1, 2, 3, 4 and 5. But they aren’t sorted at all! They are aligned in the unsettling following order: 5, 3, 2, 1, 4. N...

www.quora.com

 

[Narayana Das Allard]

I beg to differ, I claim you can not solve that state (example no. 5).



In my example no. 1 it looks like there is 1 edge swap, yet I claim I can solve it.

As a sidenote, in examples no. 2 and 3 there is 0 edge swap and 0 corner swap, yet I claim that one state is solvable and the other one is not. That is why I wrote this post.

Oh! In example no.5 is it because of the arrows, I did the T perm and the white center arrow was not right, is that why it's unsolvable?! But in example no.1 there IS only one swap (an edge swap), so you would have to break the cube apart to solve it right, why do you claim you can solve it? And in example no.2 and 3 I don't get why you claim only one is solvable but if the arrows make no.5 unsolvable, no.2 and 3 are both unsolvable in that case! Or maybe I got it all wrong and the arrows don't make a difference (well of course on a real 3x3 where the centers face don't matter! But if the edges are flipped and corners are in the right spot but you have to do the righty moves to solve them it matters of course)!

 

[Herbert Kociemba]

Please explain what do you mean by "sum of the parities of all angles" and "sum of the parities of all edges" (I actually don't know what do you mean by these). I think you do not understand what a parity of a permutation means.

I agree. I think Renslay gave some good explanation what parity means in relation to permutations some posts before. @swipymam: If you have still some problems understanding it please let us know which part of the explanation you do not understand.

 

[qwr]

So if I understand correctly, is the Rubik's Group a subgroup of all possible cube states allowing disassembly? And the question is asking about the quotient size?

(Group of legal cube states) < (Group of disassembled cube states) < (group of all permutations of stickers)?

 

[bcube]

Oh! In example no.5 is it because of the arrows, I did the T perm and the white center arrow was not right, is that why it's unsolvable?! But in example no.1 there IS only one swap (an edge swap), so you would have to break the cube apart to solve it right, why do you claim you can solve it? And in example no.2 and 3 I don't get why you claim only one is solvable but if the arrows make no.5 unsolvable, no.2 and 3 are both unsolvable in that case!

Glad that you ask.

Note that I won´t be explicitely explaining everything needed in my post, feel free to ask follow-up questions if necessary.

Let´s start with a center-fixed model, shall we? It is a 3x3x3 Rubik´s Cube model in which centers never move. Therefore, you are not allowed to do whole cube rotations, nor inner-layer moves. It is quite common in a computer solving, God´s number being 20 is based on this model too.

If you are allowed to execute only the outer-layer turns, is the following state solvable by using an even number of quarter turns and why?



In a center-fixed model, one is allowed to do a quarter turn or a half turn, 2 quarter turns being a half turn, so a quarter turn is really what is needed for us because we can get to any possible state using only quarter turns. Now, every quarter turn of outer layer toggles a permutation of edges and corners from being even to odd, and vice versa. In the example above, the permutation of corners is odd (a 4-cycle of corners needs 3 swaps, 3 being an odd number) and the permutation of edges is also odd (a 4-cycle of edges needs 3 swaps, 3 being an odd number). Since a single quarter turn toggles the permutation of both edges and corners, and the solved state is represented by an even permutation of both edges and corners, it is not possible to solve that state using an even number of quarter turns (otherwise the solved state would be represented by an odd permutation of both edges and corners).

Anyhow, the one who can answer the question can also tell whether these 3x3x3 cube states are possible and why:



In this example, we can not use a center-fixed model, simply because centers are not referencing where the other cubies should be. Instead, we can use a corner-fixed model - we can simply fix one corner, and solve the other pieces accordingly. However, now we can use not only the outer layer turns, but also the inner layer turns (because centers are not fixed in this case). An inner-layer quarter turn toggles the permutation of edges and centers from being odd to even, and vice versa. Nevertheless, the permutation of centers is "invisible" because centers are not distinguishable here. Therefore, we can get a state in which the permutation of edges is odd, while the permutation of corners is even.



1-8: solving the left and right layers (so that I could toggle the permutation of edges without toggling the permutation of corners) using an even number of quarter turns of innner layers
9: toggling the permutation of edges (as well as permutation of centers which is not visible)
10-13: permuting the other edges using an even number of quarter turns of innner layers
14-26: orienting the last 2 edges using an even number of quarter turns of innner layers



In this example we can immediately see that an odd number of quarter turns is needed to fix the black center piece (e.g. by a U' move). But an odd number of quarter turns of outer layers will toggle the permutation of corners and edges from being even to odd => that state is unsolvable because the solved state is represented by an even permutation of both corners and edges.



In this example, we need an odd number of quarter turns of outer layers to get the permutation of both edges and corners from being odd to even. However, an odd number of quarter turns will mess up at least 1 center piece => that state is unsolvable.



In this example, we need an even number of quarter turns of outer layers to fix the black center piece (e.g. by a U2 move), as well as 2 swaps of edges and 2 swaps of corners => there is no contradiction here, it should be solvable.



1-7: solving the first corner
8-11: solving the second corner
12-19: solving the third corner
20-23: solving the fourth corner
24-47: solving the edges one by one in a similar way as corners

Now you should be able to tell whether the following state is solvable and why:

 

[Narayana Das Allard]

Glad that you ask.

Note that I won´t be explicitely explaining everything needed in my post, feel free to ask follow-up questions if necessary.

Let´s start with a center-fixed model, shall we? It is a 3x3x3 Rubik´s Cube model in which centers never move. Therefore, you are not allowed to do whole cube rotations, nor inner-layer moves. It is quite common in a computer solving, God´s number being 20 is based on this model too.

If you are allowed to execute only the outer-layer turns, is the following state solvable by using an even number of quarter turns and why?



In a center-fixed model, one is allowed to do a quarter turn or a half turn, 2 quarter turns being a half turn, so a quarter turn is really what is needed for us because we can get to any possible state using only quarter turns. Now, every quarter turn of outer layer toggles a permutation of edges and corners from being even to odd, and vice versa. In the example above, the permutation of corners is odd (a 4-cycle of corners needs 3 swaps, 3 being an odd number) and the permutation of edges is also odd (a 4-cycle of edges needs 3 swaps, 3 being an odd number). Since a single quarter turn toggles the permutation of both edges and corners, and the solved state is represented by an even permutation of both edges and corners, it is not possible to solve that state using an even number of quarter turns (otherwise the solved state would be represented by an odd permutation of both edges and corners).

Anyhow, the one who can answer the question can also tell whether these 3x3x3 cube states are possible and why:



In this example, we can not use a center-fixed model, simply because centers are not referencing where the other cubies should be. Instead, we can use a corner-fixed model - we can simply fix one corner, and solve the other pieces accordingly. However, now we can use not only the outer layer turns, but also the inner layer turns (because centers are not fixed in this case). An inner-layer quarter turn toggles the permutation of edges and centers from being odd to even, and vice versa. Nevertheless, the permutation of centers is "invisible" because centers are not distinguishable here. Therefore, we can get a state in which the permutation of edges is odd, while the permutation of corners is even.



1-8: solving left and right layers (so that I could toggle the permutation of edges without toggling the permutation of corners) using an even number of quarter turns of innner layers
9: toggling the permutation of edges (as well as permutation of centers which is not visible)
10-13: permuting the other edges using an even number of quarter turns of innner layers
14-26: orienting the last 2 edges using an even number of quarter turns of innner layers



In this example we can immediately see that an odd number of quarter turns is needed to fix the black center piece (e.g. by a U' move). But an odd number of quarter turns of outer layers will toggle the permutation of corners and edges from being even to odd => that state is unsolvable because the solved state is represented by an even permutation of both corners and edges.



In this example, we need an odd number of quarter turns of outer layers to get the permutation of both edges and corners from being odd to even. However, an odd number of quarter turns will mess at least 1 center piece.



In this example, we need an even number of quarter turns of outer layers to fix the black center piece (e.g. by a U2 move), as well as 2 swaps of edges and 2 swaps of corners => there is no contradiction here, it should be solvable.



1-7: solving first corner
8-11: solving second corner
12-19: solving third corner
20-23: solving fourth corner
24-47: solving edges one by one in similar way as corners

Now you should be able to tell whether the following state is solvable and why:

Sorry for the ones with arrows I said the white center piece, I ment the black center piece!

 

[ichcubegerne]

An easier way is just to look how many numbers are larger left of each number and add those together:
4: 0
6: 0
2: 2 (4 and 6)
3: 2 (4 and 6)
1: 4 (4, 6, 2 and 3)
5: 1 (6)
0+0+2+2+4+1=9, so the parity is odd because 9 is odd.

I know that this is known as Lehmer's Code, do you happen to know if it is possible to apply permutations to this representation without having to transform it into a regular permutation form?

 

[eeeeeeeee]

Glad that you ask.

Note that I won´t be explicitely explaining everything needed in my post, feel free to ask follow-up questions if necessary.

Let´s start with a center-fixed model, shall we? It is a 3x3x3 Rubik´s Cube model in which centers never move. Therefore, you are not allowed to do whole cube rotations, nor inner-layer moves. It is quite common in a computer solving, God´s number being 20 is based on this model too.

If you are allowed to execute only the outer-layer turns, is the following state solvable by using an even number of quarter turns and why?



In a center-fixed model, one is allowed to do a quarter turn or a half turn, 2 quarter turns being a half turn, so a quarter turn is really what is needed for us because we can get to any possible state using only quarter turns. Now, every quarter turn of outer layer toggles a permutation of edges and corners from being even to odd, and vice versa. In the example above, the permutation of corners is odd (a 4-cycle of corners needs 3 swaps, 3 being an odd number) and the permutation of edges is also odd (a 4-cycle of edges needs 3 swaps, 3 being an odd number). Since a single quarter turn toggles the permutation of both edges and corners, and the solved state is represented by an even permutation of both edges and corners, it is not possible to solve that state using an even number of quarter turns (otherwise the solved state would be represented by an odd permutation of both edges and corners).

Anyhow, the one who can answer the question can also tell whether these 3x3x3 cube states are possible and why:



In this example, we can not use a center-fixed model, simply because centers are not referencing where the other cubies should be. Instead, we can use a corner-fixed model - we can simply fix one corner, and solve the other pieces accordingly. However, now we can use not only the outer layer turns, but also the inner layer turns (because centers are not fixed in this case). An inner-layer quarter turn toggles the permutation of edges and centers from being odd to even, and vice versa. Nevertheless, the permutation of centers is "invisible" because centers are not distinguishable here. Therefore, we can get a state in which the permutation of edges is odd, while the permutation of corners is even.



1-8: solving the left and right layers (so that I could toggle the permutation of edges without toggling the permutation of corners) using an even number of quarter turns of innner layers
9: toggling the permutation of edges (as well as permutation of centers which is not visible)
10-13: permuting the other edges using an even number of quarter turns of innner layers
14-26: orienting the last 2 edges using an even number of quarter turns of innner layers



In this example we can immediately see that an odd number of quarter turns is needed to fix the black center piece (e.g. by a U' move). But an odd number of quarter turns of outer layers will toggle the permutation of corners and edges from being even to odd => that state is unsolvable because the solved state is represented by an even permutation of both corners and edges.



In this example, we need an odd number of quarter turns of outer layers to get the permutation of both edges and corners from being odd to even. However, an odd number of quarter turns will mess up at least 1 center piece => that state is unsolvable.



In this example, we need an even number of quarter turns of outer layers to fix the black center piece (e.g. by a U2 move), as well as 2 swaps of edges and 2 swaps of corners => there is no contradiction here, it should be solvable.



1-7: solving the first corner
8-11: solving the second corner
12-19: solving the third corner
20-23: solving the fourth corner
24-47: solving the edges one by one in a similar way as corners

Now you should be able to tell whether the following state is solvable and why:

what?

 

[Filipe Teixeira]

- "hey Sir, is that an impossible rubik's cube state?"
- "to explain that we have to first understand something about quantum physics"
- "oh boyyyyyyyyyy"

 

[bcube]

Another fun/interesting challenge for the original poster might be this: we can prove that a single swap of 2 edges alone is unsolvable on the 3x3x3 6-color Rubik´s Cube. What makes the following state solvable on the 3x3x3 3-color Rubik´s Cube?



On an unrelated note, does anyone know what is meant by the "keychain parity" in this post by Kirjava?

 

[cuber314159]

Another fun/interesting challenge for the original poster might be this: we can prove that a single swap of 2 edges alone is unsolvable on the 3x3x3 6-color Rubik´s Cube. What makes the following state solvable on the 3x3x3 3-color Rubik´s Cube?



On an unrelated note, does anyone know what is meant by the "keychain parity" in this post by Kirjava?

Spoiler: solution

it's just a U perm because you are swapping one yellow edge back to the other yellow side

 

[swipymam]

I agree. I think Renslay gave some good explanation what parity means in relation to permutations some posts before. @swipymam: If you have still some problems understanding it please let us know which part of the explanation you do not understand.

Thank you very much to both you and Renslay! This discussion has clarified my thoughts in many ways and directed them in the right direction.

 

[abunickabhi]

Can this thread be closed as it is completely answered?