Rubik's Cube
Source: Asked to me by Piyush Goyal (CSE IITD Senior Undergraduate, To be Goldman Sachs Quant)
Problem:
Given a Rubik's Cube, find a path from centre of face to centre of cube going via each cell of cube only once.
Problem:
Given a Rubik's Cube, find a path from centre of face to centre of cube going via each cell of cube only once.
Hint:
Its not possible. Try to prove it. Cheers!
Update (Dec 11, 2011):
Solution:
Posted in comments by: Ankush Agarwal (Senior Undergraduate, CSE, IITB), Prasham (Senior Undergraduate, Aero, IITB & To be Morgan Stanley Quant), Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student), Siddhartha, Rudradev Basak (Senior Undergraduate, CSE, IITD), Yashoteja (CSE IITB Alumnus, Microsoft Research RA), Kashyap (IITM), Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service). Thanks!
Update (Dec 11, 2011):
Solution:
Posted in comments by: Ankush Agarwal (Senior Undergraduate, CSE, IITB), Prasham (Senior Undergraduate, Aero, IITB & To be Morgan Stanley Quant), Piyush Sao (EE IITM Alumnus, Georgia Tech Grad Student), Siddhartha, Rudradev Basak (Senior Undergraduate, CSE, IITD), Yashoteja (CSE IITB Alumnus, Microsoft Research RA), Kashyap (IITM), Gaurav Sinha (chera, IITK 1996 Graduate, Indian Revenue Service). Thanks!
Colour the 27 cubes red and blue such that no two adjacent cubes are of the same colour.
ReplyDeleteThe top and bottom face would be :
RBR
BRB
RBR
and the centre would be :
BRB
RBR
BRB
Total B cubes : 13 and R cubes : 14. At any point of time, you can only move to a cube of different color. So when you start at the centre B cube, you will have to end at a B cube as your 27th cube. But that would not be possible as there are only 13 B cubes and 14 R cubes.
Cheers !
Ankush Agarwal
A Rubik's cube is nothing but a three-dimensional (3*3*3) array of tiny cube-units (henceforth, referred to as cubelets). There are 27 cubelets in all.
ReplyDeleteNow, colour each cubelet as white or black as follows:
Colour a cubelet at the vertex white. Colour each cubelet in such a way that neighbouring cubelets are of the opposite colour.
This will give rise to the following colouring pattern:-
1st layer:
W B W
B W B
W B W
2nd layer:
B W B
W B W
B W B
3rd layer:
W B W
B W B
W B W
If a possible path with the required property existed, it would require exactly 26 steps (as there are 27 of them).
Because neighbouring cubelets have opposite colours, after an even number of steps, we shall be at a cubelet of the same colour.
However, note that our intended path begins from a white cubelets and ends at a black one.
This proves the impossibility of such a path.
won't coloring it black and white do it?
ReplyDelete27 cells=>path length 26=>starting and ending cell same color but
face center and cube center are adjacent so they are of different color! Contradiction
Not Possible, to prove this, colour the rubik's cube in black and white, just like a chess board. Without loss of generality, let the colour of the centre of the face be black. So the colour of centre of cube is white.
ReplyDeleteThe colour of the face looks like
B W B
W B W
B W B
Similarly colour the whole cube.
(The layer behind would look like
W B W
B W B
W B W
and the third layer would be same as first layer.)
Note that only white minicubes are adjacent to black minicubes and vice versa.
Also note that there are odd number(27) of minicubes.
So starting from any black minicube, if you wish to cover even number (26 other) minicubes, you would end up at a black minicube. But the centre minicube is white, so you cannot reach there in the end after covering all the other minicubes.
Colour cube in a 3D checkerboard fashion. If the center of the cube is black, then there are 13 black cubes, and 14 white cubes. A continuous path alternates between white and black. So it is not possible to start from a white square, cover 14 white and 13 black squares, and end up in a black square.
ReplyDeleteAssuming we can only move to immediately adjacent cubes (no diagonal movements).
ReplyDeleteColour the cubes in black and white such that adjacent cubes are differently coloured.
Then colour of face-center cube and center cube are different.
Number of steps required to start at face center and end up at center is 26,which means starting and ending cube colours must be the same.
Hence there can be no such path from face-center to center of the cube.
Consider the cells to be lattice points (0,0,0) to (2,2,2). If we start at a face point (say (1,1,0)). The sum of the coordinates alternates from even to odd and should be even after covering 27 points. However sum of coordinates of (1,1,1) is odd. Hence the contradiction.
ReplyDeletethere are a 27 cubes. if co-ordinate of a cube is (a,b,c), then a+b+c changes by 1 or -1 in one step. So ,after 26 steps, a+b+c will cumulatively change by an even integer.
ReplyDeletetherefore not possible as a+b+c for center of face and center of cube differ by 1 or -1, i.e. odd integer.
All answers are the same and all are correct! Thank You very much!
ReplyDelete