Tanya Khovanova's Math Blog

Sid Dhawan was one of our RSI 2011 math students. He was studying interlocking polyominoes under the mentorship of Zachary Abel.

A set of polyominoes is interlocked if no subset can be moved far away from the rest. It was known that polyominoes that are built from four or fewer squares do not interlock. The project of Dhawan and his mentor was to investigate the interlockedness of larger polyominoes. And they totally delivered.

They quickly proved that you can interlock polyominoes with eight or more squares. Then they proved that pentominoes can’t interlock. This left them with a gray area: what happens with polyominoes with six or seven squares? After drawing many beautiful pictures, they finally found the structure presented in our accompanying image. The system consists of 12 hexominoes and 5 pentominoes, and it is rigid. You cannot move a thing. That means that hexominoes can be interlocked and thus the gray area was resolved.

You can find the proofs and the details in their paper “Complexity of Interlocking Polyominoes”. As you can guess by the title, the paper also discusses complexity. The authors proved that determining interlockedness of a a system that includes hexominoes or larger polyominoes is PSPACE hard.

The Fomenko drawing on the left is from the original Russian edition of Homotopic Topology by Fuks, Fomenko and Gutenmacher. Dmitry Fuchs signed this book for me after my success in the USSR Math Olympiad when I was in the 9th grade. For many years I didn’t know what the picture meant and was mystified by it. Now the book has been republished with explanations and is available in English at a non-affordable price. You can find this picture and many other Fomenko drawings in his book called Mathematical Impressions, which is affordable, although the comments accompanying the illustrations are confusing. So I have my own explanation for the meaning of this illustration.

The bracelet is made out of shells. Each shell is a hollow cone whose vertex is glued to a point on the rim of the cone’s opening, thus giving each hollow cone its own handle. In a part of another drawing (at left), Fomenko shows how the bracelet is built by an army of tiny slaves. First they build the shells and then they connect them together.

How do they connect the shells to each other? The rim of the next shell is glued to the handle of the previous shell. Let me remind you that a straight line connecting a point on the rim to the vertex of a cone is called a generatrix. Imagine a generatrix that connects a vertex of a cone to the point on the rim to which this vertex is glued. This generatrix becomes a circle in a shell, which I call the handle circle. So the rim of the next shell is glued to the handle circle of the previous shell.

Now consider the fundamental group of a shell. The rim can be contracted to the handle circle. Moreover, the cone itself can be contracted to the handle circle. If we glue several shells together, the result is contractible to the handle circle of the last shell.

Now let’s go back to the bracelet. The shells become smaller in both directions and end in two points. The front end point is more interesting topologically than the one in back. Every point other than the front end has a contractible neighborhood, while the front end point does not. Or in scientific terms: The bracelet gives an example of a space with a point at which the space is “1-lc” but with no open neighborhoods on which every (Cech) 1-cycle bounds.

My son Sergei invented the following game a couple of years ago. Two people, Alice and Bob, agree on a number, say, four. Alice takes a clean Rubik’s cube and secretly makes four moves. Bob gets the resulting cube and has to rotate it to the initial state in not more than four moves. Bob doesn’t need to retrace Alice’s moves. He just needs to find a short path back, preferably the shortest one. If he is successful, he gets a point and then it is Alice’s turn.

If they are experienced at solving Rubik’s cube, they can increase the difficulty and play this game with five or six moves.

By the way, how many moves do you need to solve any position on a Rubik’s cube if you know the optimal way? The cube is so complicated that people can’t always know the optimal way. They think that God can, so they called the diameter of the set of all possible Rubik’s cube positions, God’s Number. It was recently proven that God’s Number is 20. If Alice and Bob can increase the difficulty level to 20, that would mean that they can find the shortest path back to the initial state from any position of the cube, or, in short, that they would master God’s algorithm.

One hundred people play the following game. Their names are written on pieces of paper and put into 100 labeled boxes at random. Each box is labeled with a number from 1 to 100 and one name has been placed inside each box. The boxes are placed on a table in a separate room. The players go into the room one by one and each has to open 99 boxes one after another. After each player finishes and leaves the room, the boxes are closed again. The players are not allowed to communicate with each other in any way, although they have been given one day before the event to discuss their strategies. They only win if every one of the one hundred players avoids opening the box with his or her own name. What is the optimal strategy?

Let me first discuss a simpler version of the game. Each player has to open exactly one box and they win if each one of them finds their name. After each player finishes and leaves the room, the boxes are closed again and the room is re-set.

If all of them decide to open box number 42, they are guaranteed to lose. They can try to open random boxes, then they win with probability (1/100)¹⁰⁰. Can they use a joint strategy that is better than random?

Yes, they can. Clearly, two people shouldn’t open the same box. So on the day before, if each agrees to open a box with a different assigned number, their probability to win is one over 100!. I leave it to my readers to prove that this is the best strategy.

What is the difference between this problem and the original problem? Isn’t choosing the last box the same as choosing the first? Aha! When they open 99 boxes they see the names, so they can use this information as part of their strategy.

I hope that this new version is so intriguing that you will start solving this puzzle right away.