Archive for August 2008

Why are Manhole Covers Square?

One of Microsoft’s biggest contributions to humanity is the popularization of manhole covers. The most famous question that Microsoft asks during job interviews of geeks is probably, “Why are manhole covers round?” Supposedly the right answer is that if a manhole cover is round it can’t be dropped into the hole. See, for example, How Would You Move Mount Fuji? Microsoft’s Cult of the Puzzle - How the World’s Smartest Company Selects the Most Creative Thinkers. This book by William Poundstone is dedicated exclusively to Microsoft’s interview puzzles.

All we need, actually, is for the cover not to fit into the hole. For example, if the hole is small, the cover could be almost any shape, as long as the diameter of the cover is bigger than any straight segment that fits into the hole.

Microsoft makes an implicit assumption that the cover is about the same shape and size as the hole; otherwise we would waste a lot of extra cover material.

Even with this assumption, there is a good deal of flexibility in possible shapes if our only concern is that the cover shouldn’t fit into the hole. It is sufficient for the cover to be any shape with a constant width.

Here are some additional answers to why the cover should be round. Microsoft accepts the answer that a round cover is easier to roll. I’m not sure why a cover would ever have to be moved away from its hole. But I agree that if kids try to steal a cover, it would be much easier to escape with a round one.

Another answer that Microsoft supposedly accepts is that you do not need to rotate a round cover to align it with the opening when you are putting it back. This way if there is a lane divider painted on the cover it will point in a new random direction.

You can find many other explanations at the wiki article devoted to this subject. The most reasonable is that manhole covers are round because manholes are round. Duh!

Thanks to Microsoft there are now many websites with pictures of and discussions on the shape of manhole covers. For example, Manhole Covers Etc. or Manhole.ca or Manhole Covers of the World. As you can see many manhole covers are square or rectangular. They say that New Hampshire had triangular covers at some point.

But my favorite answer to this interview question was sent to me by Jorge Tierno:

Since manhole covers are not necessarily round, but you are asking why they are round, you are probably asking why round manhole covers are round. Round manhole covers are round by definition.

Now I have my own favorite question to ask you during a job interview: “Why are some manhole covers square?”

For his Master’s thesis, my son Alexey Radul wrote the Symmetriad — a computer program to compute and display highly symmetric objects.

The objects the Symmetriad is after are the 4D generalizations of Platonic and Archimedean solids. His thesis contains a picture gallery made with the Symmetriad, and these are my three favorite pictures.

The pictures have cute titles. The problem is that I still haven’t installed the Wordpress plugin that allows me to put captions under the pictures. That is why you have to guess which title matches which picture. The titles are: “The Planets are Aligned,” “Great Jaws,” and “Diamonds are Forever.”

If you are wondering why one of the pictures shows a non-connected object, in fact the object is connected, but some of the edges are white, so that you can better see 3D cells of the object.

Subsequent to the publication of this thesis, Alexey enhanced his software to make even more dramatic pictures. The following pictures have no titles, so feel free to suggest some:

I think it would be nice to publish a book with all these pictures. As a book on symmetries should be published on a symmetric date, the next opportunity would be 01.02.2010.

Mid-Summer Status Report

I resigned from my job half a year ago. If you remember I was planning to rebuild my career in academia and to find myself along the way.

The problem with re-entering academia is that to find a job starting September 2008, I would have had to apply in December 2007. I really didn’t want to apply before finding my new direction in mathematics and publishing some papers to rebuild my name. So I decided to apply for academic jobs in December 2008, while using the intervening year for research and to try to publish.

The problem with delaying the start of my new academic job until September 2009, is that I didn’t save enough money to cover such a long period of time. Even though I cut down my expenses significantly, I still need some additional income in the meantime. However, temporary jobs consume the time I need for research in order to go back to academia. To resolve this Catch-22 situation, I decided to choose jobs of only two kinds: first, either they pay a lot, so for a limited time of work I can buy a lot of extra time for my research; or second, they’re aligned with my goals. I wasn’t yet looking very hard for work, but nonetheless several jobs came my way.

One of the jobs I accepted was a temporary job as a math competition coach at Advanced Math and Science Academy (AMSA) Charter School. This gave me a chance to check once again how I feel about teaching. I love entertaining people with mathematics. I showed magic tricks to my students, played games with them and so on. I enjoyed myself; my students liked me. But I do not know enough tricks or games to teach 24 hours a week as a regular school teacher. I decided that I really do not want to be a school math teacher. But I love being a coach, because it takes less time and I get the best kids.

I also worked on the Organizing Committee for the Women and Mathematics Program in Princeton in May 2008. The irony is that I lived in Princeton for seven years and ignored this program for most of them. Initially I was prejudiced against such a program. I felt that I should go to lectures only for their mathematical value. The gender of the lecturer doesn’t matter.

I think I was missing the whole point of the program. I should write about this program more.

The surprising result of the last half year is that I am having a blast blogging. Wouldn’t it be fabulous to find a job in mathematical journalism, if such a profession exists.

Grand Tour Puzzles

I love Grand Tour puzzles more than I love Sudoku. You are given a graph, for example, a square grid like the one on the left. Some edges are highlighted. You need to find a closed path that visits each vertex exactly once and includes the highlighted edges as part of the path. Mathematically speaking you need to reconstruct a Hamiltonian circuit on a graph, once you are given a part of it. The highlighted edges are chosen to guarantee a unique solution to the puzzle.

On the left you can see a sample grand tour problem with its solution. This puzzle was designed by Glenn Iba. On Glenn’s Grand Tour Puzzle Page you can find many grand tour puzzles of varying levels of difficulty. The puzzles are playable. That is, you can click or unclick an edge. You can also branch out in a different color, which is especially useful for difficult puzzles when you want to test a hypothesis. I just want to warn you: these puzzles are addictive — I couldn’t stop playing until I solved all of them.

Below there is a simple grand tour puzzle from Glenn’s collection, but this time on a triangular grid:

You do not need a grid to construct a puzzle. But these puzzles look very natural on grids. I tried to analyze square grid puzzles a little bit. The first important point is that for square grids with odd number of vertices on each side of the square, Hamiltonian cycles do not exist. This point is easier to prove for directed Hamiltonian cycles. You can make a directed cycle from an undirected one by choosing a direction. If you have a directed cycle on a square grid, then the number of edges pointing up should be the same as the number of edges pointing down. We can say the same thing about edges on the cycle pointing left or right. Hence, the number of edges of a Hamiltonian cycle on a square grid should be even. At the same time, the number of edges of any Hamiltonian cycle equals the number of vertices.

I just proved that you need only consider square grids with an even number of vertices on each side. For square grids with two vertices on each side, there is only one Hamiltonian cycle, namely the border of the square. The only grand tour puzzle for this grid won’t have highlighted edges at all. For a square grid with four vertices on each side there are only two different Hamiltonian cycles up to isomorpshisms:

If we count all the reflections and rotations, we will get six Hamiltonian cycles. The next picture shows all 11 grand tour puzzles on this grid. If we count rotations and reflections, we will get 66 different grand tour puzzles.

Below are the sequences associated with this puzzle. Except for one case, I do not know if these sequences are in the Online Encyclopedia for Integer Sequences. I don’t know because I only counted two terms of each sequence and this information is not sufficient to identify the sequence.

• A003763 Number of Hamiltonian cycles on 2n by 2n square grid of points. The sequence starts 1, 6, 1072, ….
• Number of Hamiltonian cycles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 2, ….
• Number of Grand Tour puzzles on 2n by 2n square grid of points. The sequence starts 1, 11, ….
• Number of Grand Tour puzzles up to isomorphism on 2n by 2n square grid of points. The sequence starts 1, 66, ….
• The smallest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 2, ….
• The largest number of edges in a Grand Tour puzzle on 2n by 2n square grid of points. The sequence starts 0, 4, ….

If you look at Glenn Iba’s 6 by 6 square grid puzzles you can see that the smallest number of edges is not more than 6. And the largest number of edges is no less than 12.

You can also make similar sequences for a triangular grid.

I invite you to calculate these sequences and submit them to the OEIS, if they are not already there.

Challenging Start

Start is the STate of the ART question-answering system. You can ask Start any question in plain English — for example, “What is the population of Moscow?” — and instead of producing millions of pages like Google, it provides one exact answer: “The population of Moscow, Russia, is 8,746,700.” I am not sure where this number comes from, as Russian sites suggest that the population of Moscow is more than 10 million people. But anyway, back to my challenge.

I have my email address in plain sight on my webpage. As a result, I get a lot of spam. So, I am thinking about a way to present my address so that humans can easily deduce it, but computers can’t. Here it is: my email server is Yahoo and my user name consists of 7 lower case letters. Each letter answers one of the questions below, in the right order. As of today, Start can’t answer any of these questions.

1. What is the first letter of the word 3?
2. What is the first letter of the alphabet?
3. What is the only common letter in the words “knowledge” and “triamphant”?
4. What is the last letter of all the days of the week?
5. What is the first letter of almost all the continents?
6. What is the first letter of the word “knight”?
7. What is the most frequent letter in the word “although”?

The advantage of presenting my user name in this manner is that I will restrict my new correspondence to people who are sufficiently eager to write to me that they can spare ten seconds figuring out my email address. The main advantage is that Start can’t answer these questions, giving me hope that spamming software can’t do it either.

I do think that the state of the art question-answering system should know the first letter of the alphabet. Start: these questions are a challenge for you. How much time will it take you to do it?

Watch out. Maybe Google can do it faster.

A Math Paper by Moscow, U.S.S.R.

I’m not kidding; there is such a paper. It is titled, “A Headache-causing Problem” and its authors are Conway (J.H.), Paterson (M.S.), and Moscow (U.S.S.R.). The acknowledgements in the paper shed some light on how Moscow became a mathematician:

The work described here was carried out when the first and second named authors enjoyed the hospitality of the third. The second and third authors are indebted to the first for expository details. The first and third authors gratefully remark that without the constant stimulation and witty encouragement of the second author this paper

[The next part was meant to be on the following page, Conway told me, but the editor missed the humor and just continued the sentence…]

was completed.

As a consequence of this joke, Moscow is envied by many mathematicians as it has an Erdős number of 2. Now wait for a couple of hundred years, and Moscow will be the only living mathematician with an Erdős number of 2. I can just imagine future mathematicians trying to persuade Moscow to coauthor papers with them, because this will be the only way for them to score an Erdős number of 3.

Even though I lived there for 30 years, I had no idea that Moscow had a talent for math. Of course, this talent only emerged when Moscow was more than 800 years old.

This wonderful paper by Moscow was very difficult to find. It was presented to Hendrik W. Lenstra on the occasion of his doctoral examination. It was published in 1977 in a book titled “Een pak met een korte broek,” which in Dutch means, “A Book in Short Trousers.”

I tried to find it on the Internet — it wasn’t there. I asked John Conway — it took him quite some time to find it. Here is the picture of John Conway searching for a headache-causing problem. Luckily for you and me, he found it. To save you from another headache, I am uploading the scan of it in pdf format here: A Headache-causing Problem by J.H. Conway, M.S. Paterson, and U.S.S.R. Moscow.

I hope that Moscow will not start complaining that I never asked its permission to post the paper. Some might argue that Moscow, U.S.S.R., doesn’t exist anymore, but I would counter that it exists, but with a changed name. If Moscow tries to sue me, I hope it’s not because it is still bitter that I left it behind in 1990.

Hey Moscow, it’s time we were friends again. Would you like to co-author a paper with me?