[next] [prev] [up] Date: Sat, 10 Nov 90 18:49:48 -0500 (EST)
[next] [prev] [up] From: Haym Hirsh <hirsh@cs.rutgers.edu >
[next] [prev] [up] Subject: Re: Rubik's Cube reassembly problem and solution

Now suppose you peeled off the 54 colored stickers and stuck them back
on at random (carefully keeping them out of the reach of children, as
there are rumors the paint contains lead, especially on the cheap
Taiwanese knockoffs), what is the probability of getting a solvable
cube? This question was posed years ago (in Singmaster?) but I
believe it is still open.

Dan Hoey

This seems easy, so I've probably messed up on something.
Can anyone catch a mistake?

Assume each of the stickers is given a number from 1 to 54. Then
there are 54! different labelings, ignoring rotation of stickers
(we'll ignore this throughout, so we'll never need to consider it).
Thus there are

= 230843697339241380472092742683027581083278564571807941132288000000000000
= 2.3*10^71

ways to randomly resticker the cube. We want to know what proportion
of these are legal (i.e., the cube can be solved).

There are 8!*12!*8^3*2^12/12 = 43252003274489856000 = 4.3*10^19 legal
cube states.  Thus there are this many legal stickerings, if each
sticker must go back to where it was.  Since they need not (just the
color must match), there are really an additional (9!)^6 for each of
these, or 98760760257294265888495040331277846607560704000000000 =
9.9*10^52 legal stickerings.

Thus the proportion of randomly restickered cubes that can be solved,
and hence the probability that a randomly restickered cube can be solved,


= 9.9*10^52/2.3*10^71 = 4.3*10^-19

[next] [prev] [up] [top] [help]