From hirsh@cs.rutgers.edu Sat Nov 10 18:50:06 1990
Return-Path:
Received: from pei.rutgers.edu by life.ai.mit.edu (4.1/AI-4.10) id AA11436; Sat, 10 Nov 90 18:50:06 EST
Received: by pei.rutgers.edu (5.59/SMI4.0/RU1.2/3.05)
id AA16007; Sat, 10 Nov 90 18:49:51 EST
Sender: Haym Hirsh
Date: Sat, 10 Nov 90 18:49:48 EST
From: Haym Hirsh
Reply-To: Haym Hirsh
To: Hoey@aic.nrl.navy.mil (Dan Hoey), Cube-Lovers@life.ai.mit.edu
Subject: Re: Rubik's Cube reassembly problem and solution
In-Reply-To: Your message of Fri, 9 Nov 90 15:02:48 EST
Cc: Haym Hirsh
Message-Id:
> 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
> Hoey@AIC.NRL.Navy.Mil
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
54!
= 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,
is
98760760257294265888495040331277846607560704000000000
------------------------------------------------------------------------
230843697339241380472092742683027581083278564571807941132288000000000000
= 9.9*10^52/2.3*10^71 = 4.3*10^-19