Given that there are 54 tiles in this net–9 of each of the 6 colors–we can say that there are $\frac{54!}{9!^6}$ unique ways to arrange the tiles in this net. Now, consider the 6 3×3 squares, each of which have 9 of the same colored tiles. What is the probability that our rearrangement will contain two same-color tiles that are touching (meaning that they share a side)? We do not need to worry about tiles in one 3×3 face touching adjacent tiles that below to another 3×3 face, but simply tiles touching within their respective faces. Thank you in advance.
Rearranging the tiles in a Rubik’s cube net
combinatoricsrubiks-cube
Related Solutions
Disclaimer: This is an old incomplete answer, now aged multiple years. I started this before I had any formal math education and I never came back to finish this.
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.
There are many ways you could describe such a Rubik's cube in group theory. One of the easiest ways is to divide each centre piece into four equal squares. Then clearly rotating the centre piece is simply a 4-cycle on those squares. The other pieces of the cube (edges and corners) are divided as usual into 2 and 3 faces respectively, which is sufficient all unique description of any state, because the position and orientation (flip or twirl) of each of those pieces already fully determines the state of each of its faces (unlike for the centre pieces).
Now as to the more interesting question of which states (of the centre pieces) are possible, it turns out that there are $\frac12 \cdot 4^6 = 2048$ states, namely all the states where the sum of the parities of the quarter turns on each centre piece is even. This is easy to prove. First note that each quarter turn moves exactly four corner pieces in a $4$-cycle (ignoring orientation), and thus by basic group theory you need an even number of quarter turns to perform any even permutation of the corners, which includes going from a solved state to a solved state (ignoring centre pieces). Thus the sum of the parities of the centre pieces' rotations (in quarter turns) must be even. Also, it is easy to check that we can achieve any such state by first performing the necessary quarter turns to set the centre pieces in the correct orientation (which performs an even permutation on the edges and an even permutation on the corners) and then use only commutators (as described here) to solve all the edges and corners. (If one is clever enough, one can alternatively use commutators to directly turn the centre pieces!)
Best Answer
With a little help from our electronic friends, this is actually not as difficult to compute as it might seem. The computation can be organized using generating functions. As is often the case, they serve here merely as a bookkeeping device, and the computation could be formulated without them – I just find it easier to think of convolutions of counts of complicated configurations as products of generating functions.
Associate the monomial $\prod_kx_k^{n_k}$ with a configuration with $n_k$ tiles of colour $k$ . Then a polynomial that is a linear combination with integer coefficients of such monomials represents counts of different configurations. Let $P(x_1,\ldots,x_6)$ denote the polynomial that represents all admissible configurations of one $3\times3$ square, i.e. it counts the ways in which the square can be coloured such that no two adjacent tiles have the same colour. Then the count of admissible configurations of the entire net of $54$ tiles is the coefficient of $x_1^9\cdots x_6^9$ in $P(x_1,\ldots,x_6)^6$.
Here’s Java code that performs this computation. By making use of the high symmetry of the problem and dropping terms with exponents above $9$, it never needs to retain more than $227$ terms at a time, so the computation doesn’t take long. The result is that there are $779371552365370814877373251723600$ admissible configurations. Thus the probability that no two adjacent tiles have the same colour is
$$ \frac{9!^6\cdot779371552365370814877373251723600}{54!}=\frac{240814346917986285649911399}{31237598017434328973915592130000}\approx7.71\cdot10^{-6}\;. $$
To check this for plausibility, note that there are $72$ pairs of adjacent tiles and each has a probability of $\frac{9-1}{54-1}=\frac8{53}$ of being monochromatic. If we pretend that these events are all independent, we can estimate the probability of none of them occurring by $\left(\frac{45}{53}\right)^{72}\approx7.65\cdot10^{-6}$, in good agreement with the computation. That the exact probability is slightly higher is plausible, since one might expect positive correlation among the monochromatic pairs – both because a monochromatic $2\times2$ square produces $4$ monochromatic pairs with a probability of roughly $6^{-3}$ instead of $6^{-4}$, and because lots of other pairs being monochromatic makes the distribution of the remaining colours slightly more unbalanced.
Here’s Java code that performs a simulation to check the result. In a sample of one billion configurations, it found 7728 without monochromatic pairs, for an estimated probability of $7.73\cdot10^{-6}$, again in good agreement with the computation.
To answer your question, which asks for the complementary probability of at least one pair of adjacent tiles having the same colour: The probability for this is about $0.99999229$.