New year challenges

Oliver Knill, 1/1/2014



Quicktime,Webm,Ogg Over the winter break 2013, while spending some days at the cape with the family, we visited the Province town puzzle shop on New Years Eve. I bought there the Meffert's great challenge as well as Smooth operator, a maze puzzle. More about the second later. The Meffert challence consists of a cube in which the corners stay stationary but turn. Four of the vertices correspond gears with 8 teeth attached, while the other four vertices have 5 teeth attached. There are two modes. In the closed mode, everything is linked. In the open mode, two halfs can move independently. Let G denote the group of one side, then G x G is the group when the cube is open. It is easy to see that the group G is Abelian and cyclic and equal to C15. So, in both cases, it appears to be a very simple puzzle, because the group just consists of two loops. But wait. Being confident and arrogant, I started to pay more attention to the food channel competitions while playing with it a bit more. Surprise: if the closing and separating of the cube halfs were allowed in more general situation, the group became bigger and appears now to have (84 * 54)/2 = 1280000 elements. Still nothing comparable with the Rubik cube but still challenging. Quicktime,Webm,Ogg


The main idea for any Rubik cube type puzzle is to look at the stabilizer of the group. For example, fix one side then look for moves which fix this side. Every kid naturally figures this out also without mathematical training. Mathematicians associate it with the name Schreier. In High school, it took me 3 weeks to figure out the Rubik cube myself in high school and I had no group theory exposure yet. In a computer science course at ETH, we assigned to the students the problem to program an algorithm to find the solution of the Rubik cube. Not to feed in a given solution but have the computer figure out one. The topic came up again in a mathematical and quite theoretical software course given by Erwin Engeler, and a Nachdiplom Vorlesung course by Gilbert Baumslag, which really had pulled me in again into group theory even so I had been hooked with dynamical systems already.

The Meffert grear puzzle is for me solved in the sense that I can bring it back to the original position with enough time, but it is not yet finished: I do not have a deterministic path to arrange the last two cubes. Since there are only 40 possibilities at the end, I solve it at the moment in a random way: scramble it completely, then solve and see. This needs still an hour.


Fortune cookie in Mews.
Apropos randomness: while waiting for the food on the brink of New year in the restaurant "Muws" in Province town, we had fortune cookies on the plates which included little toys. One was a classic metal puzzle in the form of a bent nail which must be thousands of years old at least.

These puzzles are not groups but group theory is involved also if $G$ is the group generated by affine translations and rotations in space and the puzzle has $d$ pieces, then all the possible configurations form a maze bound by a hypersurface of situations, where the two objects touch. For two pieces, this is a 11 dimensional surface in a 12 dimensional space. While mazes are trivial in two dimensions (just have your hand on the left wall and walk), in higher dimensions, puzzles are difficult. By the way, I could not resist also to buy an other such toy at the toy shop the Smooth operator. It is labeled to be difficult and I can not yet solve it yet. P.S. In this paper an other story is told

Smooth operator




Back to the simple maze with two simple loops: in the restaurant we started to wonder how long it would take to solve this Monte Carlo type. Just shake the connected puzzle long enough until it falls apart. To our surprise it was possible. It worked twice with a couple of dozen shakes. If you make the experiment, the puzzle must be small so that you can shake it in the hand. Also, the solution path should not be too tight. If you have to slide along, it is too tight. What happens when shaking is that we do a random walk in an open subset of the group $G \times G$ intersected with a large sphere. If two points are connected, the random walker will reach from one point to the other, but it might take a long time. This depends on the geometry and on the smallness of the connection path. Shaking it and getting the nails hooked together did never work. It is obvious that the probability of achieving this is much smaller because the volume of the 12 dimensional region which needs to be transversed by the random walk is much smaller. A wild guess would be that one could put the two separate nails in a shaking box, wait a few years until it is solved. Thats how the first improbably combinations of complicated organic molecules could have occurred on a time scale of billion of years. Quicktime,Webm,Ogg
Footnote: story told in this preprint, see project:

As a graduate student, I had participated in a contest in the Swiss town of Bern. A "Rubik cube" type puzzle, the "master ball" had to be solved competitively in front of a larger audience. The task had been to race doing a specific transposition in that group. Having been trained at ETH in algebra and theoretical computer science also been a course assistant in a course using computer algebra, I had used the computer algebra system Cayley (now Magma) to find a solution and assigned a Sun workstation to tackle the problem. After a few hours, it came up with a solution which consisted of several dozen moves. I brought this solution to the competition: after all the contestants had been introduced, we went on to race who would solve the puzzle first. The fastest solver was a farmer and cheese-maker from Emmental. Without computers and without any knowledge in group theory, he had the best understanding to walk around in that non-Abelian group. This event happened before the movie "Good Will Hunting" appeared and is no fiction.