Only half of the permutations are reachable. An impossible state

[swipymam]

Every cube state reachable by legal moves can always be represented by an even number of swaps, and at the same time cannot be represented by an odd number of swaps (the two are mutually exclusive). Since the right cube (located on the right in the image) has an odd number of swaps ("one" swap), this state cannot be reached.

Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

 

[bcube]

how to prove that the state on the cube on the right is impossible (without assembling the cube)?

Not sure whether it is a rethorical question or you genuinely want to know. Anyhow, the one who can answer the question can also tell whether these 3x3x3 cube states are possible and why:

 

[Renslay]

Every cube state reachable by legal moves can always be represented by an even number of swaps, and at the same time cannot be represented by an odd number of swaps (the two are mutually exclusive). Since the right cube (located on the right in the image) has an odd number of swaps ("one" swap), this state cannot be reached.


Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

If someone gives me a randomly assembled cube, I can tell if it is solvable or not in a few seconds (less than a minute). I would simply inspect it as a scramble for BLD. If you are not familiar with BLD (aka blindfolded solving): essentially you track individual pieces (and memorize them), by inspecitng how you can solve them with individual swaps. In that way, you can check if the parity (number of swaps) of the edges are the same as the parity of the corners. They must be the same for a solvable cube. If the parities are not the same, it is guaranteed that the cube is unsolvable.
(Note: I can also check the orientation of the edges and the corners with a BLD memorization inspection).

Or are you asking how can you prove that mismatching parities leads to an unsolvable state? In that case the proof lies in the parity of permutations. A 90 degree turn results a change in the parity of both the edges and the corners (4 cycle of pieces is equivalent to 5 transpositions). That means that no matter how many turns you apply, their parities must match.
As for why does this happen to permutations: see parity of permutations:

Parity of a permutation - Wikipedia

en.wikipedia.org

There are proofs that shows that a transposition (a single swap) changes the parity of the permutation.

I can give you further details on any of these topics if you are interested.

 

[swipymam]

The question is not rhetorical. If in a nearly assembled state it is clear that the permutation of two edges cannot be even, then how can this be found out in a regular scramble?
Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

 

[Renslay]

The question is not rhetorical. If in a nearly assembled state it is clear that the permutation of two edges cannot be even, then how can this be found out in a regular scramble?
Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

Then I'm afraid I do not understand the question(s).
What do you mean assembled? Do you mean solved? (Assembly as a cubing term usually means taking-apart-and-putting-back-together.)
What do you mean by "permutation of two edges cannot be even"?

But I can clearly answer the last question: how to prove that the state on the cube on the right is impossible.

In that state the corners are clearly solved. Therefore, their permutation parity is even.
The edges, regardless of their orientation, are all in their correct positions, except for the yellow-orange and the yellow-green edges. Since 1 swap (1 transposition) would bring them to a state that has an even permutation (namely, the solved state, at least in term of permutations), that means that without the swap, they are in a permutation with odd parity.
The corners and the edges have mismatching parities. Therefore, unsolvable.

 

[swipymam]

Then I'm afraid I do not understand the question(s).

How can we know in advance the correct position of the edges? Or, to rephrase the question: how do we know which cube is correct without solving it?

 

[OtaMota]

how do we know which cube is correct without solving it?

In that case, as Renslay has mentioned, you could do BLD tracing. If the number of swaps for each the edges and corners are either both odd or both even, then the cube is solvable. If there is an even number of corner swaps, but an odd number of edge swaps, (or vice versa) the cube is not solvable.

 

[swipymam]

In that case, as Renslay has mentioned, you could do BLD tracing. If the number of swaps for each the edges and corners are either both odd or both even, then the cube is solvable. If there is an even number of corner swaps, but an odd number of edge swaps, (or vice versa) the cube is not solvable.

Ok. But couldn't the other pair of edges be positioned incorrectly?

 

[Herbert Kociemba]

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.

 

[Renslay]

Ok. But couldn't the other pair of edges be positioned incorrectly?

Any edge can be at any position, it doesn't matter. With BLD tracing, you can determine the number of swaps it requires to solve them. The actual number doesn't matter here, only its parity.

Let's see an example:
Assume you have a sequence of 6 numbers. When they are solved, it looks like this:
1 2 3 4 5 6

Let's say someone mixed them up:
4 6 2 3 1 5

Can you tell me, without trying to solve this, whenever they require an even or an odd number of swaps? One method is to start from position 1, and see what is there: 4.
Then go to position 4, and see what is there: 3.
Now go to position 3, and see what is there: 2.
Now go to position 2, and see what is there: 6.
Now go to position 6, and see what is there: 5.
Now go to position 3, and see what is there: 1.

So, your "sequence" is actually this: 1->4->3->2->6->5->1.
This means you can solve this case with five swaps, and you can do it even blindfolded!
Swap the 1st and 4th element. (This solves number 4, and brings 3 to the first position.)
Swap the 1st and 3th element. (This solves number 3, and brings 2 to the first position.)
Swap the 1st and 2th element. (This solves number 2, and brings 6 to the first position.)
Swap the 1st and 6th element. (This solves number 6, and brings 5 to the first position.)
Swap the 1st and 5th element. (This solves number 5, and brings 1 to the first position.)
Number 1 will be automatically solved.

This is (almost) exactly how blindsolving works. Also, in this example, the parity is odd: we needed five swaps to solve this mix. And we were able to determine that without touching or swapping anything.

 

[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.

So, parity checks are necessary. Thanks for the comprehensive answer!

 

[bcube]

in a nearly assembled state it is clear that the permutation of two edges cannot be even

If you say it like that, a reader could think that the first example I gave you in my previous message is unsolvable, and the other two examples are solvable - which is not the case (the examples are interactive, you could try solving them if you want).

 

[Jorian Meeuse]

If you say it like that, a reader could think that the first example I gave you in my previous message is unsolvable, and the other two examples are solvable - which is not the case (the examples are interactive, you could try solving them if you want).

Spoiler: Spoiler

Well the additional degree of freedom of not having center caps allows for 'rotating' only the (imaginary) core, which is equivalent to an even (twice odd) permutation of corners and an odd (thrice odd) permutation of edges

Any solution to the second needs a number of quarter turns of the black face which is congruent to 3 modulo 4 (and 0 on all other faces) and hence must change corner and edge parity. Impossible.

The third can be done with 2 J perms, I believe (standard alg)

 

[Herbert Kociemba]

Let's see an example:
Assume you have a sequence of 6 numbers. When they are solved, it looks like this:
1 2 3 4 5 6

Let's say someone mixed them up:
4 6 2 3 1 5

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.

 

[Narayana Das Allard]

Every cube state reachable by legal moves can always be represented by an even number of swaps, and at the same time cannot be represented by an odd number of swaps (the two are mutually exclusive). Since the right cube (located on the right in the image) has an odd number of swaps ("one" swap), this state cannot be reached.
View attachment 40124

Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

Which state is unreachable, in other words: which state would you have to break the cube apart to get to it?

 

[Narayana Das Allard]

Which state is unreachable, in other words: which state would you have to break the cube apart to get to it?

Is it the state on the right?

 

[Renslay]

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.

Indeed. Alternatively (or equivalently) one can count the number of inversions, where an inversion is just a pair of elements where the element that comes later is smaller.

In the example above, inversions are the following pair of elements:
(4,2), (4,3), (4,1), (6,2), (6,3), (6,1), (6,5), (2,1), (3,1).
There are 9 inversions in total, which is odd. In the Wikipedia page I showed above, there are multiple proofs showing the parity of the number of inversions is the same as the parity of the number of transpositions (swaps) of a permutation.

 

[bcube]

Spoiler: Spoiler

Well the additional degree of freedom of not having center caps allows for 'rotating' only the (imaginary) core, which is equivalent to an even (twice odd) permutation of corners and an odd (thrice odd) permutation of edges

Any solution to the second needs a number of quarter turns of the black face which is congruent to 3 modulo 4 (and 0 on all other faces) and hence must change corner and edge parity. Impossible.

The third can be done with 2 J perms, I believe (standard alg)

I know you can answer the following 2 questions as well, but it might be interesting for original poster as an exercise (or for you as an amusement):

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 cubing jargon, a T-permutation represents a state in which a 1 pair of edges and 1 pair of corners need to be swapped. In the following example only a 1 pair of edges and 1 pair of corners need to be swapped. Is that state solvable and why?

 

[Christopher Mowla]

Question for theorists: how to prove that the state on the cube on the right is impossible (without assembling the cube)?

I'm aware that there have been several replies to this thread already, but because it was a highly liked answer, maybe see my post on rcubers explaining why we can't swap just 2 corners (or just 2 edges) on a 3x3x3.

And if you like how I explain things, perhaps you would like An Unabridged Explanation of WHY (Odd) Parity Exists on Big Cubes and Why You CAN Swap Just 2 Edges on a 4x4x4 (and more), which was a follow-up post/explanation to the above.

 

[Narayana Das Allard]

I know you can answer the following 2 questions as well, but it might be interesting for original poster as an exercise (or for you as an amusement):

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 cubing jargon, a T-permutation represents a state in which a 1 pair of edges and 1 pair of corners need to be swapped. In the following example only a 1 pair of edges and 1 pair of corners need to be swapped. Is that state solvable and why?

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! But in Swipymam's first message it was an in even amount of swaps, there is 1 edge swap, and so it's unsolvable, but since bcube's message was an even amount of swaps (2 swaps, 1 edge swap and 1 corner swap!) it is solvable and that's why!