chris2@garfield.MUN.EDU (Chris Paulse) (12/19/89)
I don't claim to know anything about graph theory, but here's an interesting problem (I don't even know how to solve the Rubik's cube): If I had a solved Rubik's cube, and the colors on each face were just stickers on the black plastic surface, if I exchanged some of the stickers, would the cube still be solvable in the normal way? If not, I have a friend who plans to distribute them widely. Any pointers to a readable book on graph theory would be nice too. The quantum chemists use it for spin algebras.
rp@XN.LL.MIT.EDU (Richard Pavelle) (12/19/89)
In article <5310@garfield.MUN.EDU>, chris2@garfield.MUN.EDU (Chris Paulse) writes: > If I had a solved Rubik's cube, and the colors on each face were > just stickers on the black plastic surface, if I exchanged some > of the stickers, would the cube still be solvable in the normal way? Nope. For example you could change two edge cubie colors and it could not be solved from that position. -- Richard Pavelle UUCP: ...ll-xn!rp ARPANET: rp@XN.LL.MIT.EDU
rshelby@ms.uky.edu (Richard Shelby) (12/19/89)
In article <5310@garfield.MUN.EDU>, chris2@garfield.MUN.EDU (Chris Paulse) writes: > > If I had a solved Rubik's cube, and the colors on each face were > just stickers on the black plastic surface, if I exchanged some > of the stickers, would the cube still be solvable in the normal way? > Some switching of the colored stickers on cube faces makes solution impossible. Rubik's cube has been used in lots of popular math columns, it shouldn't be difficult to find articles. It's also not difficult to treat Rubik's cube as a set of n-tuples and then do proofs after determining the possible moves/ transformations. Play around with it; I've used a subset of the trans- formations to help teach logic. -- Richard L. Shelby rshelby@ms.uky.edu Department of Health Services rshelby@ukma.BITNET University of Kentucky {rutgers,uunet}!ukma!rshelby
mikes@rtech.UUCP (Mike Schilling) (12/20/89)
From article <5310@garfield.MUN.EDU>, by chris2@garfield.MUN.EDU (Chris Paulse): > > If I had a solved Rubik's cube, and the colors on each face were > just stickers on the black plastic surface, if I exchanged some > of the stickers, would the cube still be solvable in the normal way? > No, there's three kinds of *parity* preserved by any legal move: 1. The positions of the cubes fall into two sets; a legal move can't move between sets. This is much like Sam Loyd's 15-16 puzzle. 2. The orientations of the edge cubes fall into two sets. Reversing a single edge cube moves from one set to another, but a legal move reverses an even number. 3. The orientations of the corner cubes fall into three sets. Turning a corner cube clockwise or counter-clockwise moves into another set. A ninety-degree legal move turns two clockwise and two counter-clockwise. So if you randomly rearrange the stickers, you only get a solvable position one twelfth of the time.
rice@ernie.Berkeley.EDU (Daniel S. Rice) (12/20/89)
> == Mike Schilling >> == Chris Paulse >> If I had a solved Rubik's cube, and the colors on each face were >> just stickers on the black plastic surface, if I exchanged some >> of the stickers, would the cube still be solvable in the normal way? >> >No, there's three kinds of *parity* preserved by any legal move: [ Argues correctly that cube positions fall into 12 orbits] Mike's response correctly notes that *switching positions of cubies* can result in 11 families of unsolvable cubes. The original post asked about moving *stickers*. Clearly, there must be one side cubie that is blue and red, one that is blue and green, etc., etc., for the puzzle to even make sense. A corner cubie that is, say, all orange can never be part of a solved cube. So, strictly speaking, there are many more than 11 unsolvable cube families if replacement of stickers is allowed. I suppose this is a nitpick but it seemed as if others were answering the wrong (but mathematically much more interesting) question. Dan
ag@amix.commodore.com (Keith Gabryelski) (12/20/89)
In article <5310@garfield.MUN.EDU> chris2@garfield.MUN.EDU (Chris Paulse) writes: >If I had a solved Rubik's cube, and the colors on each face were just >stickers on the black plastic surface, if I exchanged some of the >stickers, would the cube still be solvable in the normal way? Negative. There are certain arangment of squares that are not ``reachable'' from the solved Rubik's form. For instance, there will never be a Rubik's cube, that started from the solved form and was made by normal turns of the cube, in the a form were all cubes are in their correct place and only one edge piece is flipped: OOO OOO OOO BBB RRR GGG YYY BBB RRR GGG YYY BWB RRR GGG YYY WBW WWW WWW *------------------------------* As I remember, this is also ``illegal''. OOO OOO OOO BBB RRR GGG YYY BBB WRR GGG YYY BBB RRR GGG YYY WRW WWW WWW One corner pieces flips are ``illegal'', also: OOO OOO OOB BBR ORR GGG YYY BBB RRR GGG YYY BBB RRR GGG YYY WWW WWW WWW This is all from ~10 year old memory, but I am pretty sure of my assertions. Pax, Keith Ps, follow-ups to sci math in hopes someone has a proof. -- ag@amix.commodore.com Keith Gabryelski ...!cbmvax!amix!ag
verma@mahimahi.cs.ucla.edu (Rodent of Darkness) (12/20/89)
In article <4330@rtech.rtech.com> mikes@rtech.UUCP (Mike Schilling) writes: >No, there's three kinds of *parity* preserved by any legal move: > >1. The positions of the cubes fall into two sets; a legal move > can't move between sets. This is much like Sam Loyd's 15-16 puzzle. >2. The orientations of the edge cubes fall into two sets. Reversing > a single edge cube moves from one set to another, but a legal > move reverses an even number. >3. The orientations of the corner cubes fall into three sets. Turning > a corner cube clockwise or counter-clockwise moves into another set. > A ninety-degree legal move turns two clockwise and two > counter-clockwise. >So if you randomly rearrange the stickers, you only get a solvable position >one twelfth of the time. Not exactly. What you say is true for rearrangement of the cubbies not the stickers. (i.e. if you take a rubik's cube apart, scramble the pieces then put it back together, you have one chance in twelve that the resultant cube is solvable. Random rearrangement of the stickers could, for example, make every center square red, or a corner could have three white stickers. In eacher case the resultant cube is not solvable, but neither case is treated in your above analysis. Note that you talk about sets that the cubes (I use the coined term cubbies for clarity) fall into; if you want to analyze the random sticker problem, you need to discuss the sets that stickers fall into and parity about stickers etc. --- TS
hoey@ai.etl.army.mil (Dan Hoey) (12/21/89)
From article <5310@garfield.MUN.EDU>, by chris2@garfield.MUN.EDU (Chris Paulse): > If I had a solved Rubik's cube, and the colors on each face were > just stickers on the black plastic surface, if I exchanged some > of the stickers, would the cube still be solvable in the normal way? The probability, given an arrangement of the 54 stickers chosen uniformly from the 54! possible permutations, is 6 8 12 9! 6! 3 8! 2 12! 40,122,452,017,152 -------------------- = --------------------------------------- 54! 12 130,253,249,618,151,492,335,575,683,325 -16 = approx 3.08 10 The way this works is that there are 9!^6 6! ways of putting the stickers on so that the cube is already solved, and 3^8 8! 2^12 12!/12 - 1 unsolved cubes corresponding to each solved cube. Previous posters answering ``1/12'' are responding to the question, ``if I put the twelve edge pieces and eight corner pieces of a Rubik's cube together at random, would it then be solvable in the normal way? Dan