How many stickers need to be cycled on a Rubik's cube before the chance it's unsolvable drops below 11/12?

Question

This is a question I'm actually looking for the answer to.

It's known that when you swap individual pieces on a Rubik's Cube, the probability that afterwards it will be possible to solve is 1/12.

Say that you take all the possible combinations of cycling N stickers simultaneously. By the amount of cycled stickers, I mean the minimum amount of stickers you need to cycle to make that combination.

What is the largest N that the probability of this cube being impossible to solve is greater than 11/12? Is there a way to do this without brute forcing it? Is there no limit?

Answer 1

The probability that it will be impossible if you swap stickers will never drop below $11/12$. The reason for this is actually rather mathematically simple.

First, an interchange of $N$ stickers is equivalent to some sequence of interchanges of two stickers. Thus, the problem you're asking about is exactly the same as asking if an equivalent sequence of 2-sticker swaps puts the cube in a solvable state. By solving the 2-sticker-swap problem, we'll solve the problem for any number of sticker swaps.

Suppose the cube, after some number of sticker swaps, is in a state $P$, and suppose $P$ is not solvable cube. Therefore, there must be at least two stickers out of place. In order to reach any solvable state $S$, a sequence of moves must be executed such that, at some point, exactly two stickers must be swapped to reach an $S$.

This is an important fact. At the point where $P\mapsto S$ requires only one swap ($n=1$), the probability of making the correct swap is exactly equal to the probability of selecting the two correct stickers. As there are 54 stickers on the cube, the probability of selecting the first correct stickers is $1/54$. The probability of the second is $1/45$, because selecting a sticker of the same color wouldn't change the cube state. Therefore, the probability for $n=1$ is: $$p_{n=1}=\frac 1 {54*45}$$

There's one edge case where this doesn't hold true. When both needed stickers are on different edges, there are actually two ways to swap pieces into a solved state. This is because swapping two edges on a Rubik's cube is legal. However, this is the only such situation, since the same symmetry doesn't apply to corners or centers. Thus, in this case: $$p_{n=1,edge}=\frac 2{54*45}$$

If $P\mapsto S$ requires more than one swap ($n>1$), then there is no single swap that will put the cube in a solvable state, so the probability of entering a solvable state is $$p_{n>1}=0$$

By basic probability, the probability that the cube will enter an unsolvable state is $1-p$, which is:

$$\begin{align} 1-p_{n=1}&=1-\frac{1}{54*53}&=\frac{2429}{2430}\\ 1-p_{n=1,edge}&=1-\frac{2}{54*53}&=\frac{2428}{2430}\\ 1-p_{n>1}&=1-0&=1 \end{align}$$

In other words, if you need more than one swap to put the cube in a solvable state, then no matter what you do, a single swap won't make the cube solvable. If you need only one swap to make the cube solvable, then there's a good chance you won't pick the right one. Because we know that: $$1>\frac{2429}{2430}>\frac{2428}{2430}>\frac{11}{12}$$

the probability that the cube will be solvable after swapping two stickers will never fall below $11/12$.

Answer 2

Here is a partial answer. If there is a largest N, then it is

greater than 2

Handwaving proof:

The notion of 12 solvability sets refers only to states in R, the set of states reachable by sequences of 'nice' swaps, defined as swaps of stickers between faces of cubies of the same type (edge, corner, centre) (a notion that may for most purposes be less than optimally conceived of in terms of sticker swaps); whereas this question allows any kind of sticker swaps - for example leading to states with all centre cubies red. If it is true that a single swap of two stickers suffices to get to a state in any of the solvability sets, then 1 in 12 of those swaps will lead to solvable states. How many non-nice swaps are there? There are p of two stickers of the same colour, all of which will lead to solvable states; and q of two stickers of different colours, all of which will lead to states outside R and therefore unsolvable. WLOG, consider only swaps that involve a red sticker. p is half of the sum of 20 (corner to non-corner), 8 (centre to non-centre) and 20 (edge to non-edge), which is 24. The 'half' is because we have counted each swap twice. When we count swaps between red and non-red stickers, we don't multiply by a half, so q is 5 times the same sum, because we've got 5 other faces with similar distributions of stickers on edges, corners and centres, so q is 240. $\frac{p}{q}>\frac{1}{12}$, so $N\not= 2$.

I suspect this can be combined with some of the thinking in @Emrakul's proof (which is not yet solid) to show that there is no N.

Correction:

I've gone wrong with the nice and non-nice swaps here. A swap of a red sticker from one edge cubie to another isn't nice if it yields an edge cubie with two red stickers, and the same applies if we replace 'edge' with 'corner'. The good news is that I'm still going to assume that after one nice swap the proportion of states that are solvable is $\frac{1}{12}$. (Waves hands.) We've just got more non-nice swaps now and we've got to distribute them between p and q. Of these, 12 are of red edge stickers to edge cubies which have already got a red edge sticker on them, giving a double-red edge cubie and therefore unsolvability. We get another 24 when we replace 'edge' with 'corner'. So we need to increase q by 36, so $q=276$. $\frac{p}{q}$ is now $\frac{24}{276}=\frac{1}{11.5}$, which is still greater than $\frac{1}{12}$, so the proved-by-handwaving result still stands.