[bushindo]

Let's consider the following 4x4x4 Rubik's Cube,

The above cube is in the solved state (each of the 6 faces has identical color). I now take some paint and paint over two squares so that the resulting cube now looks the image below,

Notice that essentially we swapped the position of a red with that of a blue square. The top face and the three faces hidden from view are unchanged. Show that, using the normal pivoting and rotating operations of Rubik's cube, it is not possible to return the cube to the solved state like that of the first image.

Edited February 11, 2011 by bushindo

[moonthirsty]

Everyone knows that the Rubk's Cube is unsolvable through pivoting or rotation of the cube planes. The only way to solve it is to remove and reapply the stickers, or modify an image in paint as you have done above.

[Molly Mae]

Everyone knows that the Rubk's Cube is unsolvable through pivoting or rotation of the cube planes. The only way to solve it is to remove and reapply the stickers, or modify an image in paint as you have done above.

Good solve, moon. You beat me to it.

[bushindo]

Everyone knows that the Rubk's Cube is unsolvable through pivoting or rotation of the cube planes. The only way to solve it is to remove and reapply the stickers, or modify an image in paint as you have done above.

The bolding in the quote is mine. I assume by Rubik's cube you mean the specially-modified cube in my OP. The question in the OP is not whether such a cube is solvable, but rather why is it not solvable. In other words, I'm asking for a proof that no sequence of rotations or pivots will return the cube to the traditional solved state.

Edited February 11, 2011 by bushindo

[curr3nt]

Is it because the squares changed are in different positions?

- - - -  - - - -

- x - -  - - x -

- - - -  - - - -

- - - -  - - - -

If either x was moved to match the other one it would be solvable?

Any pivot or rotation keeps the sqaures in the same relative position.

[araver]

Is it because the squares changed are in different positions?

- - - -  - - - -

- x - -  - - x -

- - - -  - - - -

- - - -  - - - -

If either x was moved to match the other one it would be solvable?

Any pivot or rotation keeps the sqaures in the same relative position.

No,

I thought so too, but it does not work like that. You can move the blue X a little to the right in 3 moves:

- move the second column on the red face upward (moving the blue painted X toward the yellow).

- move the third yellow row (the one that now contains the blue painted X) down toward the almost blue face

- now move the third blue row (the one with our special blue painted X) left toward the initial red face

Now it's switched from it's initial position.

So, they can move around. Obviously the 4 central squares need to remain central (as they are small cubes painted on only one face).

I do feel the solution is somewhere along these lines. There is a constant equation/property/state that the central squares have (as a whole set, not separately). Said property is preserved through rotations. The proposed painted cube and the solved cube are not "in the same state".

I can't seem to find the invariant though.

Oddly, enough, I think the trick is the same on 3x3x3 Rubik's.

[araver]

Oddly, enough, I think the trick is the same on 3x3x3 Rubik's.

Scratched that, just showed the inside of a 4x4x4 and it is way different on the inside than I expected (from disassembling a 3x3x3 cube where centers don't budge).

So, easiest way to prove is to find a global invariant, specific for Rubik cubes with more than 1 center.

[curr3nt]

No,

I thought so too, but it does not work like that. You can move the blue X a little to the right in 3 moves:

- move the second column on the red face upward (moving the blue painted X toward the yellow).

- move the third yellow row (the one that now contains the blue painted X) down toward the almost blue face

- now move the third blue row (the one with our special blue painted X) left toward the initial red face

Now it's switched from it's initial position.

So, they can move around. Obviously the 4 central squares need to remain central (as they are small cubes painted on only one face).

I do feel the solution is somewhere along these lines. There is a constant equation/property/state that the central squares have (as a whole set, not separately). Said property is preserved through rotations. The proposed painted cube and the solved cube are not "in the same state".

I can't seem to find the invariant though.

Oddly, enough, I think the trick is the same on 3x3x3 Rubik's.

Could also change the position by just rotating the red face.

I think there is something to those three turns over the three axis netting the same position as the single rotation of the face.

[Molly Mae]

It hinges on the fact that (at least with a 3x3x3), relative movements happen in threes. That is to say, you cannot move just one piece, nor can you only move two. Relatively, you must move three or more (after such a pattern is executed and only three have changed position [but note that others may have changed their orientation]).

I hope that's as confusing for you as it was for me.

[araver]

Every Rubik cube's state is basically a permutation of the initial state. And each pivot/rotation is multiplying the state with a permutation.

Any sequence of moves can be written as a series of basic permutations (rotation a certain row to one side or the other). Which generate the group of permutations that are possible states.

Now, for the 4x4x4 variant, the painting in the problems means another permutation (actually a transposition). Denoting by S the initial state (identity permutation), C the current (painted) state and by t the transposition the painting inflicted we get:

S*t = C

Note that since t is a single transposition (painting=switching the two labels) and S is even, C's signature must be odd. Now, to get back from C to S you need to use Rubik-moves. Rubik moves are of two types: (Type 1) moving center rows/columns (i.e. not involving the cube's corners) which is basically a permutation that can be described as a product of 4 disjoint cycles. So, from the intial position

 |   1   2   3   4  |  5   6   7   8  |  9  10  11  12  |  13  14  15  16 |

to this position:

 |  13  14  15  16  |  1   2   3   4  |  5   6   7   8  |   9  10  11  12 |

you get the product of 4 4-cycles:

(1,5,9,13)(2,6,10,14)(3,7,11,15)(4,8,12,16)

(Type 2) moving a top/bottom row (i.e. which also rotate a face 90 degrees) The latteral effect is like a type 1 permutation (4 disjoint 4-cycles) The effect on the face looks weirder, from

 

 +-----------------+

 |  1   2   3   4  |  

 |  5   6   7   8  |   

 |  9  10  11  12  |

 | 13  14  15  16  | 

 +-----------------+

to

 

 +-----------------+

 | 13   9   5   1  |  

 | 14  10   6   2  |   

 | 15  11   7   3  |

 | 16  12   8   4  | 

 +-----------------+

But actually is still a product of 4 4-cycles:

(1) corners switch around (1,4,16,13)

(2) middles switch around (6,7,11,10)

(3) left middles (2,8,15,9)

(4) right middles (3,12,14,5)

So, 8 disjoint 4-cycles in a type II move.

Now, each 4-cycle is odd, yet there is an even number of odd permutations in every Rubik move, so signature parity is preserved under Rubik moves.

Therefore you can't get from C (odd) back to S (even) using Rubik moves (even)

But to complicate things further: For the 3x3x3 variant, you cannot obtain a perfect outside, except in one state.

For the 4x4x4, since centers move, there *might* be different internal permutations (if you number the exact pieces) that seem solved if looking through the outside. *might* = I don't really know for sure 'cause it depends on how the Rubik's group looks like for 4x4x4. So you might not get to S, but to another parallel state that on the outside still looks as solved (but has the center 4 pieces on one or more faces rotated for example).

I would have to make sure that all permutations that look solved on the outside are still even. And I have yet found a simple way to prove this.

EDIT: formatting and some typos.

Edited February 11, 2011 by araver

[Guest]

I don't think it's impossible.

I have a 4x4 Rubik's cube like the one in the OP, and awhile ago I looked up instructions on how to solve it. The cheats are not mine, but they do address the question. And there IS a set of moves to flip flop those two pieces.

All you have to do is turn the cube on its side, so the blue face is facing you, and the red face is facing up. In the attached image, straight arrows represent turning the designated horizontal layer (from the front perspective), and curved arrows represent turning the designated layer in depth.

If you want to test it out on a real cube, do the set of moves in the attachment, just omit the first 2 and do them at the end instead. This will get the cube to look like the OP. Then simply do the whole move, and the 2 wrongly-colored squares will change positions.

[araver]

I don't think it's impossible.

I have a 4x4 Rubik's cube like the one in the OP, and awhile ago I looked up instructions on how to solve it. The cheats are not mine, but they do address the question. And there IS a set of moves to flip flop those two pieces.

All you have to do is turn the cube on its side, so the blue face is facing you, and the red face is facing up. In the attached image, straight arrows represent turning the designated horizontal layer (from the front perspective), and curved arrows represent turning the designated layer in depth.

If you want to test it out on a real cube, do the set of moves in the attachment, just omit the first 2 and do them at the end instead. This will get the cube to look like the OP. Then simply do the whole move, and the 2 wrongly-colored squares will change positions.

Agree,

Tried a 4x4x4

simulatorthat lets me paint it that way.

The computer managed to solve it, but the demo moved too fast for me ... so I still think it can't get to the original position, but it can get to another position where on the outside it still looks solved, yet it permutes some other elements in the centers as well. (which was mentioned with red in my odd/even signature attempt at proving it can't be done).

Guess I need a real (and numbered) 4x4x4 to test the moves and see if this is the case *shrug*

Edited February 12, 2011 by araver

[bushindo]

I don't think it's impossible.

I have a 4x4 Rubik's cube like the one in the OP, and awhile ago I looked up instructions on how to solve it. The cheats are not mine, but they do address the question. And there IS a set of moves to flip flop those two pieces.

All you have to do is turn the cube on its side, so the blue face is facing you, and the red face is facing up. In the attached image, straight arrows represent turning the designated horizontal layer (from the front perspective), and curved arrows represent turning the designated layer in depth.

If you want to test it out on a real cube, do the set of moves in the attachment, just omit the first 2 and do them at the end instead. This will get the cube to look like the OP. Then simply do the whole move, and the 2 wrongly-colored squares will change positions.

Mea culpa. The puzzle is flawed and wasn't completely thought through. I apologize. Congratulations to hettieann for the counter example.

I developed this puzzle along the lines of araver's previous post, namely that the rotations of the 4x4x4 cube will preserve the odd/even signature of the permutation, while a transposition will actually change the parity. Jumped the gun, I suppose =)