10
$\begingroup$

This is a combinatorial question related to Rubik's cube $3\times3\times3$ (and, in the end, its generalizations $n\times n\times n$). I assume that the readers are familiar with this puzzle. Let's recall some basic terminology and conventions to rule out possible ambiguities. In the following, we use the words state and configuration interchangeably, as exact synonyms.

We are only interested in configurations of Rubik's cube where it has the shape of a cube (so, we consider rotations of its layers by an angle of $90^\circ$ as atomic transformations, and no incomplete rotations are allowed). Also, we consider configurations that can be obtained from one another by solid rotations of the cube as a whole (without any relative movements of its parts) as identical.

The cube has $6$ faces, each one of them is a $3\times3$ grid of squares — $9$ squares per face, and $54$ squares in total. Each square is of a solid color. Orientation of every single square is irrelevant (in fact, this rule has significance only for central squares). There are $6$ different colors, and there are $9$ squares of each color. There is a single selected state where each face consists of all squares of the same color — this state is called the solved state. A state that can be reached from the solved state by a sequence of valid rotations of layers is called a valid state (the solved state, of course, is a valid state too).

As a side note, if we allowed disassembling the cube into its parts and reassemling them, then we would get the number of possible states $12$ times larger than the set of valid states (this larger set would be a disjoint union of $12$ equivalence classes under valid rotations, each of the classes called an orbit). We are only interested in valid states in the following.

Usually, it is assumed that colors of all squares on the cube are visible. Let's consider a possibility that some squares may be obscured (e.g. completely covered by an opaque colorless sticker), so that their colors are not visible.

In general, obscuring some squares can result in some states becoming visually indistinguishable. As trivial examples, obscuring all $54$ squares makes all states indistinguishable, but obscuring only $1$ square (no matter which one) does not make any states indistinguishable.

  1. What maximal number of squares in Rubik's cube $3\times3\times3$ can be obscured without making any states indistinguishable?

  2. What maximal number of squares in Rubik's cube $2\times 2\times 2$ can be obscured without making any states indistinguishable?

  3. What maximal number of squares in Rubik's cube $n\times n\times n$ can be obscured without making any states indistinguishable? Can we find a general formula, recurrence relation, etc. to compute it for every $n\in\mathbb N$?

$\endgroup$
  • $\begingroup$ To establish a simple lower bound we can reason as follows. Suppose we obscured $9$ squares, all of the same color (say, red). By inspection, we can see that $9$ red squares are not visible anywhere, but there are $9$ obscured squared. So, we can deduce that all obscured squares are red. Hence, no information is lost, and no states were made indistinguishable. We can furthermore obscure a non-red square on a corner cubie with a red square. By inspection of other corner cubies, we can find what color has been obscured, and the last visible square is enough to infer the orientation of the cubie. $\endgroup$ – Vladimir Reshetnikov Mar 14 '16 at 4:22
  • $\begingroup$ I started working on this but then wondered, are you considering that the color scheme is known before peeling/obscuring off the stickers/squares? Because this will affect how many you can peel off since it gives some extra information. $\endgroup$ – Vepir Mar 16 '16 at 11:12
  • $\begingroup$ @Matta Yes, we can assume the color scheme is known. $\endgroup$ – Vladimir Reshetnikov Mar 16 '16 at 17:21
  • 2
    $\begingroup$ This question reminds me a lot of trying to find the minimum number of clues necessary in a game of Sudoku, except instead of numbers you filly the squares with colors (which could be labelled arbitrarily as $1$ to $6$, making it even more like Sudoku) $\endgroup$ – Rob Bland Mar 21 '16 at 16:49
1
+100
$\begingroup$

To make our lives easier, we can separate the pieces by 3 types:

Edges (3 stickers)
Sides (2 stickers)
Centers (1 sticker)

Also note that im observing a cube with Yellow and Black( I call it White later on) colors for the top and bottom sides as my default color scheme.
(Other pieces follow Red, Blue, Orange, Green)


For the $3\times3\times3$ Rubik's cube, first we can solve for the middle parts.

We can conclude that if the color scheme is known, that all obscured centers can be determined if we have at least 2 neighbour ones.
This means we can peel off 4 centers if we keep 2 neighbour ones. This can be checked by playing with its own cube or simply by following the laws of legal positions and using something like a solver help you out. (This is because centers can't be really switched, but the pieces around them can so that it looks that way)

Then lets see how many stickers from the edge pieces can be obscured or peeled off, since any configuration of $n\times n\times n$ always has exactly 8 edges.

We can list them by the colors they contain:
(Red, Blue, Green, Orange, Yellow, White) $$ R,G,Y $$ $$ R,G,W $$ $$ R,B,Y $$ $$ R,B,W $$ $$ O,G,Y $$ $$ O,G,W $$ $$ O,B,Y $$ $$ O,B,W $$

If you want to know how many stickers can be peeled off and still be able to identify each corner, you can ask yourself; How many stickers you can take so that when putting them back, you have only one possible way to do so?

I have found out the maximum number of 12 out of 24 stickers; by taking all R or O, then all B or G and finally all Y or W.
Here is an example:

$$ -,-,- $$ $$ -,-,W $$ $$ -,B,- $$ $$ -,B,W $$ $$ O,-,- $$ $$ O,-,W $$ $$ O,B,- $$ $$ O,B,W $$

Now by shuflling the order and rotation of all 8 edges in every way possible, there will be only one way to stick the removed stickers, thus you still can identify the pieces.

Now the Side pieces, which might be a bit tricky.
On the $3\times3\times3$ Rubik's cube, there are 12 Edge pieces:

$$ G,R $$ $$ R,B $$ $$ B,O $$ $$ O,G $$ $$ Y,G $$ $$ G,W $$ $$ W,B $$ $$ B,Y $$ $$ R,W $$ $$ W,O $$ $$ O,Y $$ $$ Y,R $$

Now you can try to do the same thing.
Firstly I tried to remove all White stickers, then it allows me to take one color from $Y,?$ pieces other than yellow, and after that nothing more can be taken without providing multiple solutions for the edges; so that was 5 stickers.
Then after other failed attempts, I found you can remove 6 stickers; one of each color so that there aren't multiple stickers of the same color standing without their second color, and I'm kinda sure it can't be done with more than 6 here.
If someone can do better here, please let me know.


So if I haven't made a mistake, for the $3\times3\times3$ Rubik's cube you can remove total of $12+6+4 = 22$ out of 54 stickers top (following the things I pointed out) without losing any information about the cube's states.

The $2\times2\times2$ Rubik's cube is made of only 8 edge pieces, so 12 out of 24 stickers can be removed here.


We can now try to generalize this to other $n\times n\times n$ cubes.

We now know that we can for;
$n=2$ take 12 out of 24
$n=3$ take 22 out of 54

For any $n\times n\times n$ cube, we always have 8 edges, so thats $+12$ obscured stickers.

For the side pieces, we have $n$ of each piece (sorted set of pieces):

$$ W,R $$ $$ W,B $$ $$ W,G $$ $$ W,O $$ $$ Y,R $$ $$ Y,B $$ $$ Y,G $$ $$ Y,O $$ $$ R,B $$ $$ R,G $$ $$ O,B $$ $$ O,G $$

There is nothing more to do here than apply the same thing I did in $3\times 3\times 3$ cube;
Remove 6 stickers, one of each color so that there aren't multiple stickers of the same color standing without their second color and do that for each new set of the side pieces.
This provides us with $6\times(n-2)$ pieces more to obscure.
Again, if you can do better with the sorted set I provided, please let me know.


So far then, the number of stickers we can obscure is: $$12+6\times(n-2)+C$$

Where $C$ is the number of "mobile" and "immobile" centers we can obscure, that appear after $n>3$ and have yet to be figured out.
(when $n=3$ then $c=4$ )



So now, the center pieces at $4\times 4\times 4$ cube and every other with $2k$ sides ($k>1$) are different than every $2k+1$ sided cubes;

The $2k+1$ like our standart $3\times3\times3$ cube have 6 "real centers" which are immobile and $4$ out of $6$ can be obscured, the rest one-sticker centers here are "mobile" and behave differently when being rotated.
Same goes for all of centers which are all "mobile" in $2k$ cubes.

How many of these mobile centers can be obscured? I would say for a starting bound, all of one color which is then:
$C = (n-2)^2$ for $n>3$
And gives us finally:

$$12+6\times(n-2)+(n-2)^2$$

Pieces we can surely obscure.

I haven't yet started checked if more can be obscured on these centers, but thats because its now end of the day and I don't have any more time, and now decided to post my progress so far.

I think you could take it from here to finish up the generalization and try to see if it is possible to obscure more than $(n-2)^2$ stickers using the color scheme and legal permutations, so maybe separate formulas for $2k$ and $2k+1$ can be found.

Update

Actually I don't think the mobile centers should provide us with any additional problems, thus we can take for $C$ that it is: $ = (n-2)^2 \times 4$ Since we need only 2 full center colors that will tell us the rest, most easily after solving the cube to its solved state.

Then we have: $$12+6\times(n-2)+4\times(n-2)^2$$

I have classes to be on early tomorrow morning now, so good night.

Edit: This should be computed and checked to make sure I haven't made a mistake somewhere.

$\endgroup$
  • $\begingroup$ Any corner piece's identity and orientation can be determined by just two stickers; two corners with one sticker removed from each, and two remaining stickers of the same two colors, are mirror images of each other. So you can remove at least 13 corner stickers. $\endgroup$ – David K Mar 21 '16 at 13:26
  • $\begingroup$ @DavidK I'm not sure what you are saying, but does this still imply when the corners and all other pieces are scrambled? How would you then decide which corner is a mirror image of which? Could you show a example for your 13 out of 24 of the corner stickers? (and explain why the corners in your example can have only one solution which then means you know for sure the identity of each piece) By using something like my 12 out of 24 example? That would make your statement very much more clear. $\endgroup$ – Vepir Mar 22 '16 at 13:33
  • 1
    $\begingroup$ I'm assuming the color scheme is known, as you stated. So just pull the W sticker off the OBW corner piece. Compare it to the other OB piece. You can still tell which is which and deduce which one originally had a W sticker. Alternatively, without taking the stickers off, try to put the OBY corner in the place where the OBW corner should be, oriented so the O and B stickers are on the same faces as the O and B center stickers. It can't be done, because the O and B stickers are placed differently on that corner. $\endgroup$ – David K Mar 22 '16 at 13:39
  • $\begingroup$ I see it now, haven't seen that by myself. I guess this could too be applied to the side pieces too in a similar way. This increases the total number of stickers that can be peeled off. I'll update my answer considering mirrored pieces for both side and corner pieces when I find some free time for this. Meanwhile you could also post an answer yourself if you want, considering the mirrored pieces as you pointed out. $\endgroup$ – Vepir Mar 22 '16 at 15:37
  • $\begingroup$ The side pieces are a little trickier since any of the B side pieces with the other sticker removed actually appear identical. But I think there might be a way to have two pieces with on the B sticker remaining and know which is which due to the fact that 11 of 12 configurations of the small cubes are not reachable from the solved state. $\endgroup$ – David K Mar 22 '16 at 17:54

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.