6
$\begingroup$

If you turn only two adjacent faces of the Rubik's cube, is it possible to reach a state where only three corner pieces are out of place (and all other pieces are in the original places)?

This was a question I thought of many years ago. At that time I was able to prove it by writing a computer program to count for me. But now I am in fact curious to find out what elegant solutions there are.

Firstly, this webpage gives two different proofs that the answer is "no", and that there are exactly $120$ possible permutations of the corner pieces.

Secondly, I give a proof below that my brother and I found. My question is whether there are other ways to prove this that are fundamentally different, and hopefully more elegant than these proofs. We are also curious if there is any deeper reason our proof works at all, because intuitively it has no reason to work since the final parity argument only excludes some 3-cycles.

$\endgroup$
2
$\begingroup$

First we view the six corner pieces as laid out in a rectangular grid with slots labelled from 1 to 6:

1——4——5
|  |  |
2——3——6

Then the permitted moves are simply the two 4-cycles $A = (1,2,3,4)$ and $B = (3,4,5,6)$. From now we shall talk about only permutations generated by $A,B$. And for convenience, given any permutation $X$, let $X'$ denote its inverse.

Note that we can easily move any pieces $p,q,r$ into slots 1,2,3 respectively. (First move $p$ to slot 1. If $q$ is not in slot 2 then move $q$ to slot 3 and perform $AB'A'$. Finally move $r$ to slot 3.) This gives at least $6 \cdot 5 \cdot 4 = 120$ different permutations.

The above also shows that any 3-cycle $C$ on slots $x,y,z$ can be transformed (by a conjugate) into a 3-cycle on slots 1,2,4. Namely, there is a permutation $P$ that moves the pieces in $x,y,z$ to slots 1,2,4 and so $P'CP$ would be a 3-cycle on slots 1,2,4.

Thus we only need to prove that there is no 3-cycle on slots 1,2,4 (and not affecting other slots). It suffices to show that $(4,2,1)$ is impossible, because $(1,2,4) = (4,2,1)^2$.

Consider the locations of pieces that are an odd number of edges from the original slot (along the grid). At the start there are none. We list all the possible configurations where "1" denotes the locations of such pieces (up to symmetry, since symmetry does not affect the distance from slots):

Group 0:

000  001  010  100  011
000  111  010  100  110

Group 1:

011  101  000  001  111
011  101  110  100  111

It can be checked that each of $A,B$ will always take a configuration from one group to the other group. Since $A,B$ are odd permutations, any 3-cycle would require an even number of moves, and hence we would remain in group 0, but $(4,2,1)$ corresponds to:

110
000

which is in group 1 and hence is impossible.

$\endgroup$
  • $\begingroup$ The strange thing is that the final group parity does not even prove the impossibility of $(1,2,4)$, nor the impossibility of $(1,3,5)$ or $(5,3,1)$. Of course, the whole proof is done under the false assumption that some 3-cycle is possible, so proof-theoretically anything is provable, but it still feels odd to us, as if we are missing some deeper invariant. $\endgroup$ – user21820 Apr 17 '17 at 15:25
  • $\begingroup$ As an alternative to this, the group of valid even moves (generated by $A^2, B^2, AB$) acts on the set of 3-element subsets of $\{1,2,3,4,5,6\}$, with exactly two orbits. It looks like each possible 3-cycle will take at least one of the 3-element subsets out of its orbit. But I can't figure out a nice way to describe the orbits, other than by explicitly listing them. $\endgroup$ – Henning Makholm Apr 21 '17 at 12:03
  • $\begingroup$ @HenningMakholm: If you find a way, I'll be glad to see it! We're seriously puzzled by how our proof works, and any other proof might illuminate it better. =) $\endgroup$ – user21820 Apr 21 '17 at 12:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.