Tanya Khovanova's Math Blog

I added some new jokes to my collection of math, computer and geek humor:

* * *

— What do you do to protect yourselves from viruses?
— We use disposable computers …

* * *

Microsoft offers a new service. They sell ad spots in their error messages.

* * *

Sysadmin:
— I do not care if everyone insists that using the name of my own cat as a password is a bad idea! RrgTt_fx32!b, kitty-kitty-kitty …

* * *

Due to technical difficulties the release of Windows 2000 is delayed until February 1901.

* * *

A doctor looking at patient’s X-rays:
— Hmm, multiple hip fractures, tibia and fibula fractures. Oh well, Photoshop can fix all that.

* * *

After learning how much money Bill Gates has, Satan offered him his own soul.

* * *

Question: What did one math book say to the other?
Answer: Don’t bother me. I have my own problems.

* * *

Student: Teacher, would you punish me for something I didn’t do?
Teacher: No, why?
Student: I didn’t do my homework.

* * *

— My teacher said we would have a test today, rain or shine.
— Then why are you so happy?
— Because it’s snowing.

* * *

Question: How many sides does a box have?
Answer: Two — the inside and the outside.

* * *

Question: What did the calculator say to everyone?
Answer: You can count on me.

Just updated my collection of Funny Math Pictures.

Here is a puzzle that my ex-brother-in-law, Dodik, gave to me today:

Prove that every group with more than two elements has a non-trivial automorphism.

I usually love puzzles that are solved with a counter-intuitive brilliant idea. This puzzle is different — I didn’t solve it in one elegant swoop. But I still love the puzzle: it feels so natural, and it’s solution feels so natural, that I even decided to call this puzzle “organic.” Or, maybe, I am just in an organic mood today waiting for my organic bananas to be delivered from Boston Organics.

Here is a funny puzzle from Kvant (1996, vol 4), the best Russian journal of recreational math.

When Alice goes through the looking-glass, she might meet many multi-headed, multi-armed, multi-legged beings. A being with H heads, A arms and L legs is considered:

• smart, if H > A+L,
• strong, if A > H+L,
• fast, if L > H+A.

Can there exist a well-rounded personality behind the looking-glass: someone who is smart, strong and fast at the same time?

Once I witnessed John H. Conway factoring large numbers in his head. Impressed, I stared at him. Encouraged by my interest, he told me that if I ever want to be able to factor large numbers, I should know all the primes below one thousand.

The secret to knowing all such primes is to remember the composites, he continued. Obviously, we don’t need to remember trivial composites — the ones divisible by 2, 3, 5, or 11. Also, everyone knows all the squares below one thousand, so we can count squares as trivial composites. We only need to remember the non-trivial composites. There are not that many of them below one thousand — only 70. I mean, 70 is nothing compared to the number of primes: 168.

So, I need to remember the following seventy numbers:

91, 119, 133, 161, 203, 217, 221, 247, 259, 287, 299, 301, 323, 329, 343, 371, 377, 391, 403, 413, 427, 437, 469, 481, 493, 497, 511, 527, 533, 551, 553, 559, 581, 589, 611, 623, 629, 637, 667, 679, 689, 697, 703, 707, 713, 721, 731, 749, 763, 767, 779, 791, 793, 799, 817, 833, 851, 871, 889, 893, 899, 901, 917, 923, 931, 943, 949, 959, 973, 989.

If you are very ambitious and plan to learn the primes up to 50,000, then the trick of learning non-trivial composites instead of primes is of no use to you. Indeed, for larger numbers the density of primes goes down, while the density of non-trivial composites stays about the same or increases very slightly due to a smaller number of squares.

The turning point is around 11,625: the number of primes below 11,625 equals the number of non-trivial composites below it. So, compare your ambition to 11,625 and tailor your path of learning accordingly.

If you are lazy, you can learn primes only up to 100. In this case your path is clear; you should stick with remembering non-trivial composites, for you need to remember only one number: 91.

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.

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.

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.

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.