Very nice.
And Group Theory is Good Stuff, though I still haven't quite understand Lie Groups ("continuous groups of transformations (generally linear ones)")
This week, 14-year-old Lucas Etter set a new world record for solving the classic Rubik’s cube in Clarksville, Maryland, in the US, solving the scrambled cube in an astonishing 4.904 seconds. The maximum number of face turns needed to solve the classic Rubik’s cube, one that is segmented into squares laid out 3x3 on each face …
Lie groups are essentially just the same thing as all n x n invertible matrices, i.e., GL_n(k), where k is any field. If the field has a nice topology, say R or C, then you pull this topology back through the determinant map to get a topology on GL_n. All other Lie groups more or less look like this, in that they form a closed subgroup (i.e., inverse image of a closed subset of the reals under the determinant map) of GL_n(R) or GL_n(C). (This can be taken as a definition of a Lie group, but shouldn't if you are doing things properly. Which we aren't, since this is a comment thread on a news website.)
Something like this: a group is a collection of symmetries of an object. Any object will do, as long as it has constituent parts that possess symmetry. An example of a group is the group of Rubik's cube: the symmetries here are all moves, which might not look like symmetries because we swap the colours around, but if we ignore the colours then they are symmetries, and the colours are simply there to show you that you are doing a symmetry. Solving Rubik's cube is equivalent to the following: given a symmetry of Rubik's cube, write it as a sequence of "easy" symmetries, i.e., quarter turns of the slices.
This is an example of a finite group, where there are finitely many symmetries. Of course, there are objects with infinitely many symmetries, such as a disk. This has a rotation of any angle, and a reflection through any line passing through the centre. Another example of an infinite group is the real numbers, with addition being the way of combining objects. Here there is also a notion of closeness, in that two numbers are 'close' if their difference is 'small'. Of course, close and small are relative terms, and the appropriate mathematical concept to encapsulate this is a topology. A topology on a set, such as the real numbers, is a collection of subsets of it, called 'open sets', and they have to satisfy three basic properties: the empty set, the set with nothing in it, is open; the intersection of two open sets, so everything in both of them, is also open; the union of any number of open sets, so everything that's in any of them, is open.
For the real numbers, the open sets are collections of open intervals (a,b), which means all numbers between a and b, but not a and b themselves. Two numbers are 'close' if they are in lots of open sets together, in some sense.
If we have pairs of real numbers then we can put a topology on this, the 'product topology', which says that a set is open if it is the product of open sets in each variable, and then throwing in more open sets for this to be a topology. (Notice that, given any set of open sets, this can be a topology by including unions and intersections, so we can do this.)
There was no reason to choose just pairs of real numbers, we could have chosen n^2 real numbers: then we can arrange these numbers as n by n arrays, and this gives us a topology on all matrices. The determinant map is 'continuous', meaning that if we take an open subset of the real numbers, U, then all matrices with determinant in U form an open subset of the set of matrices.
With this topology, we can talk about matrices being close to one another, more or less their co-ordinates are close in the real numbers. If X is a group of invertible matrices, then it is closed if all other matrices form an open set, and closed groups of matrices are Lie groups.
That's some more words, but it might not be any better.
I did that, but I didn't think it would be very believable if I completed the whole thing so I only switched around one face.
Of course, the downside of this was I made it impossible to solve the cube after that. Wasn't until my cubemaster cousin tried and failed for some time that anybody realised my deceit...
I went one better: I typed up my own version of how to solve the cube, got my uncle to photocopy off a load of them, then would sit in the nearby shopping centre and wait for someone to come along and watch me solve it.
They'd say "I wish I could do that" or some such, at which point I'd flog them a copy of my solution for a quid (this was back in the days when a pound was actually real money, rather than small change!)
Made a tidy sum (which I'd then blow on video games in the local arcade, but that's another story!)
real money as in a little green note? Ahh the days when a 5p mixture paid was paid by a shilling coin or maybe 2 shilling coin and 10 half pennies in change....
Later on in life I worked in a call center at Christmas breaks. Rubiks cubes were great to while away the hours, we too had a "cheat sheet" for doing cubes (it was fairly long winded but worked every time). cant remember it now, might get one at Christmas and teach the kids.
My dad and I did the same, selling our A4 solution sheet for a quid. I also offered a cube-solving service at the school fête for 50p, I could deal with one customer per minute (without referring to the sheet). Some customers came back 3 or 4 times during the fête because they kept messing their cubes up again... they should have coughed up the extra for a sheet.
"I prefer Gordian Knot theory. Gives a far simpler solution"
Ah, the branch cut. Not a very complex solution.
(A Polish mathematician was on a flight when the pilot fell ill, and nobody else could fly. The crew asked him if he knew how to fly the aircraft: he said "alas no, I am but a simple Pole on a complex plane.")
That's pretty amazing. I thought a banjo player's fingers on a fret board were quick. I wonder how long it would take to arrange the each side of the cube in every possible combination, one after the other, using only the human hand and mind. Don't desert me boffins!
I wonder how long it would take to arrange the each side of the cube in every possible combination, one after the other, using only the human hand and mind.
Well, that's easier than arranging a cube in every possible combination simultaneously.
Anyhoo...
Let's assume Etter can in general iterate overy 27 configurations in 5 seconds. That's the starting configuration, plus 26 quarter-turn moves at worst to reach the solved configuration. Etter presumably uses half-turns as well as quarter-turns, but half-turns pass momentarily through their intermediate quarter-turn configuration, so we can assume quarter-turns with no loss of generality.
We can assume those 27 configurations are distinct, because if he reached the same configuration twice then he has a loop and he's not using an optimal path.
There are roughly 4.3e19 configurations. (4.3e19 / 27) * 5 gives us ~ 8.0e18 seconds to complete, or somewhere around a quarter of a million million years, plus some time for pee breaks.
If anyone's curious, a little back-of-the-envelope shows a Rubic's Cube has about 65 bits of entropy, assuming all configurations are equally probable. (They are, mechanically, but since RCs are sold in solved form, and many people manage to solve them and then leave them that way, at any given time the solved configuration probably appears disproportionately often across the entire state of extant RCs. So don't use the solved configuration as your Rubic's Passcube.)
In competition you get 15 seconds to inspect the cube before starting the solve. That is not long enough to plan the whole solve. Therefore an important part of solving is being able to quickly recognise which algorithm you are going to need next, after the one you are doing.
Recognition and look-ahead are what makes the difference between a quick solver and a fast solver.
Ouch, my lack of clarity bites again.
Quick = under 30 seconds
Fast = under 15 seconds
Very Fast = under 12 seconds
Contender = under 10 seconds
Amazing = under 8 seconds
The best cubers I have seen average 6 to 8 seconds. That's over 5 solves, discarding the fastest and slowest solve, averaging the middle 3.
World records usually happen when an Amazing solver gets a skip on the last layer (the last layer just happens to be solved by luck when the first two layers are solved).
That's why competitions use the average rather than a single solve.
...it takes a certain view of the world to do this.
I never solved a Rubik cube, but then neither did I ever pick one up to try.
And had I done so would have run out of patience after about three turns.
But then I do have the attention span of goldfish.
I do know people who would persevere with one of these infernal devices. None of them have much conversation, though.
I still use the same algorithm I used in 1983, and have had many cubes that have become destroyed by constant solving. I sometimes use a completed cube to make nice patterns and leave it on my desk for people to see (wow, how did he do that / smug git), or just therapy when talking to my IT department. I'm usually 2 - 4 minutes in slow mode, but then 'the real McCoy' official cube is not very good for speed cubing as it is actually quite stiff. Inferior models / copies actually tend to break!
I used to be able to do it in under 30 seconds (I remember using silicone grease to lube the thing to make it rotate easir - ha!), but again that was 35 odd years ago too, and I have forgotten how.
One think I always wondered about though - if you mix the cube in say, 10 turns, then surely the fastest solve is 10 turns?
"One think I always wondered about though - if you mix the cube in say, 10 turns, then surely the fastest solve is 10 turns?"
Definitely not. All it shows is that there is a way to solve it in ten turns. Suppose that you scramble it five times and unscramble five times, for example. You have a solved cube at the end, so the solution is 0 turns.
To see another reason why such thinking has to be wrong, mix the cube for, instead of ten turns, a million. It is never going to need a million turns to solve it then.
"I used to be able to solve the cube in about a minute. Forgotten how to now - it was 35 years ago."
Not quite as long on both counts: closer to 32 years ago, give or take, and I had it down to about 40 seconds.
The last time I picked one up, several years ago, I could only solve it some of the time. And much, much more slowly!
"Isn't it a bit like a race "to the nearest pub?" Depends very much on where you start."
TBH it depends on what shit the nearest pub serves. Reminds me of the film "the worlds end" and the pub crawl they do from one pub to the next cookie cutter pub. I even think the bandits were the same....
When I finally got round to buying a Rubik's Cube it came with a 'cheat sheet' which explained the sequence of twists required to move pieces around. I did eventually solve a jumbled cube but had no desire to memorise the algorithms nor perfect executing them at speed.
Despite having such little interest in Rubik's Cubes I do however enjoy wasting my time untangling topological puzzles. Each to their own I guess.
43,252,003,274,489,856,000 possible combinations. Add game theory to that, RPG with a dash of FPS for good measure.
You have 9 x 6 rooms to create, and where the player goes defines the setup of the next room. Equate player moves to rotations, jumble the initial settings at start, and you've got a really infinite game (for practical values of infinite, of course).