Tanya Khovanova's Math Blog

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.

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?

I resigned from BAE Systems on January 3, 2008. At the beginning of a year, it often takes time for people to adjust to writing the new number. Probably out of habit, someone somewhere wrote that I resigned in January, 2007. The computer at my medical insurance company Cigna got overexcited. It noticed that Cigna paid all my medical bills for 2007, a period for which, according to that creative but premature resignation date, I was ineligible. In its zeal Cigna retracted the money that they had already paid to my doctors for all of my 2007 visits.

In an instant, I became a delinquent; my doctor bills were suddenly more than a year overdue and my credit score probably plummeted. My taxes became suspect, too. I had claimed that I had medical insurance on my Massachusetts taxes, which now Cigna wouldn’t confirm.

While Cigna was racing to get their money back from my doctors, they conveniently forgot that I and BAE Systems paid a lot of money for their insurance. They didn’t hurry to return this money. At one point I was thinking I would be richer if I got back the money paid to Cigna for my insurance and paid the doctors myself.

I had a conference call among Cigna, my former employer and myself. My employer confirmed that I had Cigna coverage until January, 2008, but this was not enough. Cigna insisted that it needed “computer confirmation,” even though it was their shoddy computer work that caused all this trouble.

After many phone calls and conference calls, finally Cigna admitted that I am right and reinstated my medical insurance coverage for the year 2007.

Can you guess what happened next? I received a new bill from my doctor. Cigna reinstated me, but didn’t pay the money back to my doctors. Now there was another round of phone calls and conference calls.

As of today, the time and nerves I spent to resolve this issue exceeded the money Cigna owes to my doctors and I am still waiting for the money to be transferred.

If they are fighting so hard not to pay their debt of $1,000, I wonder about the financial situation of this company. I would definitely consider it very risky to buy Cigna stocks.

Recently I published my ideas for a Flexible Zipcar Algorithm that allows customers to rent Zipcars one-way. I had a dream the night after I published it: the Zipcar research lab invited me to give a presentation about my algorithm and they asked me a lot of questions. I would like to answer these questions now, but first let me give you a short description of the algorithm:

Some locations are flexible. The number of cars assigned at a flexible location is not fixed, but rather a range between the minimum and the maximum. A Zipster would be allowed to use a car one-way from one flexible location to another, as long the number of assigned cars doesn’t move outside the range.

Question. Zipsters expect to pick up the exact vehicle they reserved. With vehicles changing locations you will break this system. I am operating on the assumption that Zipsters will continue to pick up the exact vehicle they reserved.

Question. What about people who get attached to the cars at their location? You can divide your pool of cars at a flexible location into two groups: fixed Zipcars and floating Zipcars. Only floating cars will be allowed to move. You should advise Zipsters who get attached to their cars to choose fixed cars as the object of their affection. This solution is less flexible, but it resolves your problem.

Question. You designed your algorithm using the min and max number of cars at a flexible location. Where is the desirable number of cars coming from? We need the desirable number of cars to calculate the financial incentives. For example, you can take the absolute value of the difference between the current number of cars at a flexible location and the desirable number of cars. Then sum it up over all locations. We can call this total the distance between the current state and the optimal state. If a one-way trip increases this distance, that Zipster pays extra and vice versa. You can also add a surcharge for all one-way trips to cover the extra expense for parking spaces.

Question. What if cars get stuck? For example, what if we always have the maximum number of cars at Harvard Square and the minimum number of cars at Coolidge Corner? You can always offer free rides from Harvard Square to Coolidge Corner. If every Zipster knows that you have a discount program which is easy to find, your cars will be in the right place in no time. For example, you can color code overstaffed and understaffed locations on your map; or you can add RSS feeds for people who are interested when cheap rides from Harvard Square to Coolidge Corner are available.

Question. Are you saying that instead of hiring drivers to move our cars around we find a much cheaper Zipster who needs to go in the same direction? Yes. If you go even further and offer a token payment or some Zipcar credits, you can have Zipsters driving your cars to oil changes and car washes for you.

Question. Why do you always talk about a small number of flexible locations? I would limit the number of flexible locations for your initial stage, so that for a small investment you get something new, you can experiment, you can observe and study trends in how cars are migrating, you can tune your financial incentives system and you can design and test your web support for this algorithm.

Question. What if someone reserves a car for a one-way trip one month in advance? What happens with the car during this month? If your car – let’s name it “Comfy” — is reserved from the Harvard Square location for a month from now, you need to lock this car into the Harvard Square location for a month. That means, no one can take Comfy for a one-way trip during this month. This looks like a bad case of inflexibility. To resolve it you can have a time-limit for one-way reservations. For example, you might limit one-way reservations to not more than three days in advance.

Question. Suppose we have four cars at the Harvard Square location and the desirable number is three. Then four people reserve four different cars at this location for round-trips on Labor Day. Are these four cars stuck at Harvard Square for a month until Labor Day? I can offer one solution using the earlier idea of fixed and floating cars. You can allow very advanced reservations for fixed cars, but floating cars can only be reserved three days in advance. Another possible solution is that you do the same without dividing your cars into fixed and floating. For example, you allow people to have very advanced reservations for any car which is currently assigned to the Harvard Square location. As soon as three cars are reserved for more than three days in advance, the fourth car is no longer available for very advanced reservations. The fourth car temporarily starts behaving like a floating car, without that being its permanent designation.

Question. Suppose today is Monday and Jack reserves Comfy one-way from Harvard Square to Coolidge Corner for Thursday. To which location is Comfy assigned for three days between Monday and Thursday? On one hand it should be assigned to Harvard Square as it takes a parking space there and we can’t allow another car to take up that space. Also, Comfy is available for reservations before Thursday at Harvard Square. At the same time, Comfy can’t be counted as an extra car anymore as we know that it is guaranteed to be moved. That means that even though Harvard Square actually houses an extra car for these three days, it shouldn’t be flagged as a location with extra cars that need to be reassigned. On the other hand, Comfy will take a spot at Coolidge Corner soon, so we can’t allow other cars to move into that spot. Even though Coolidge Corner doesn’t yet have the complete set of cars, we can’t allow other cars to take up Comfy’s future spot.

Question. It sounds complicated. Can we make it simpler? You can simplify this design for the first implementation. For example, you can only allow immediate one-way reservations. That eliminates any problem with conflicting reservations or an extra car holding up a space for three days. Also, keep in mind that the user doesn’t need to see all this complicated stuff. They are only interested in knowing whether or not they can reserve a car.

Question. What if someone reserves the car one-way then cancels the reservation? This only becomes a problem if someone else reserves the same car for a later time at the destination. In this case, you might institute a very big fee for cancellations of one-way reservations, so that you can either hire a driver or offer a super deal to other Zipsters. Of course, if you allow only immediate reservations for one-way cars this problem will be minimized.

Question. Suppose Jack reserves Comfy for two hours; his starting point is Harvard Square and his end point is Coolidge Corner. Where is Comfy assigned during these two hours? This is a great question. For round-trip Zipcars, you do not care if a person starts a half-hour late or returns the car one hour early. With a one-way car, you need to know when Comfy’s parking space will be available to other cars. To allow Jack to pick up his car as late as he wants or return it as early as he wants, the simplest solution is to assign Comfy for two hours to both locations. That is, no other car is allowed to move into Comfy’s parking spot at Harvard Square until the end of Jack’s rental period and the spot for Comfy should be ready at Coolidge Corner from the start of Jack’s rental period.

Question. You were talking about the simplest solution. Do you mean you have other solutions? I have many ideas, but I prefer to get some feedback from the car-sharing research community before continuing.

Hey, Zipcar! Let’s do it!

Suppose N mothers live in a city. Half of them have one child and half of them have two children. That means that an average mother has 1.5 children.

Suppose we pick the sexual orientation of every child by rolling dice. Let’s assume that a child has a 10% probability of being homosexual.

The number of mothers with one child who is homosexual is 0.05N. The number of mothers with two children both of them homosexual is 0.005N. The number of mothers with two children with only the first child homosexual is 0.045N, which is the same as the number of mothers of two children with only the second child homosexual. The total number of mothers who have two children with at least one of them homosexual is 0.095N.

Let’s calculate the average fertility of a mother with at least one homosexual child. It is (1*0.05N + 2*0.095N)/(0.05N + 0.095N) = 0.24/0.145 = 1.66. The resulting number — 1.66 — is much bigger than 1.5, the average number of children for a mother.

This means there is a correlation between homosexuality and the fertility of mothers. This suggests that there is a gay gene which at the same time is responsible for female fertility.

But the model is completely random — there can’t be any correlation.

Where is the mistake?

Obviously, you can substitute homosexuality with having blue eyes or math ability or whatever, but I invented this paradox while I was working on my “Fraternal Birth Order Threatens Research into the Genetics of Homosexuality” post. Besides, there is some research on correlation between homosexuality and fertility.

I look forward to your solution to this puzzle.