Puzzle of the Week for 10 May 1999: Solution

The most scrambled Rubik's cube will have S = 4. Although we might find a pair of faces with no more than 3 squares of any one color, it's not possible for this to occur on all possible pairs of faces simultaneously.

To see why, consider how the 9 blue squares can be divided among the six faces of the cube. If 4 or more of them are on a single face, then S must be 4 or more. If 3 are on a single face (let's turn the cube so that this face is on the top), the other six must be distributed among the remaining five faces. Four of those five faces are adjacent to the top face; if there is a blue square on any of them, S must be at least 4. If none of these four faces has a blue square, then all 6 of the remaining blue squares must be on the bottom face, so S = 6.

This leaves one possibility: that there are no more than two blue squares on any face. Since there are six faces, this can happen only if there are two blue squares on each of three faces, and one blue square on each of the other three faces. Now consider the three faces with two blue squares each. These faces must be adjacent, so there must be a pair of adjacent faces with a total of 4 blue squares, and S = 4.

This reasoning shows only that S cannot be as small as 3; to prove that it's actually possible to get a cube with S = 4, it's easiest to experiment with a real cube.

Links