Tanya Khovanova's Math Blog

I recently wrote two pieces about the puzzle relating to sons born on a Tuesday: A Son born on Tuesday and Sons and Tuesdays. I also posted a beautiful essay on the subject by Peter Winkler: Conditional Probability and “He Said, She Said”. Here is the problem:

You run into an old friend. He has two children, but you do not know what their gender is. He says, “I have a son born on a Tuesday.” What is the probability that his second child is also a son?

A side note. My son Alexey explained to me that I made an English mistake in the problem in those previous posts. It is better to say “born on a Tuesday” than “born on Tuesday.” I apologize.

Despite this error, I was gratified to hear from a number of people who told me that I had converted them from their solution to my solution. To ensure that the conversion is substantial, I’ve created a new version of the puzzle on which my readers can test out their new-found understanding. Here it is:

You run into an old friend. He has two children, but you do not know what their gender is. He says, “I have a son born on a Tuesday.” What is the probability that his second child is born on a Wednesday?

I was terribly shy when I was a teenager. I worked on this problem and overcame it. But when I moved to the US my shyness returned in a strange form. I was fine around Russians but shy around Americans. At first I assumed that it was a language problem.

I became friends with a Russian sexologist and psychotherapist. He pointed out that I never initiated a conversation with Americans and so I realized that my shyness had returned. He prescribed an exercise for me: I had to invite a new American guy to lunch once a week.

Why guys? Maybe because he was a sexologist or maybe because my problems with self-esteem were more pronounced when I was around men. In any case, I decided to do the exercise.

To paint the full picture I need to add some relevant details. At that time I was married, although I didn’t wear a ring, and wasn’t especially interested in other men. The reason I didn’t wear a ring was that Joseph, my husband at the time, did not himself want to wear a ring. As I love symmetry in relationships more than I love rings, I didn’t wear one either.

The men I was about to invite to lunch were mere acquaintances, because I had not yet made any American friends. So although I didn’t intend to hide it, they may not have realized that I was married.

Two things surprised me in this exercise. First, it was very easy. Most people agreed to do lunch with me.

Second, every man I invited mentioned his girlfriend. This was unexpected. From my experience with Russians, I anticipated that every man would hide his involvement with someone else, even with a wife, at least for some time. At the very least, many Russian men would try to flirt.

The Americans were different. Unclear why I had invited them out, they wanted to be upfront with me from the start, just in case I was interested in them. Since that experience, I admire the way that American men come clean.

I never invited any of these guys out twice: I just needed a supply of new men for my exercise in overcoming my shyness. I wonder if they thought I was put off by their confessions. Perhaps my loss of interest in them after the first lunch confirmed their suspicions that I was attracted to them.

The sexologist’s exercise was a success. Today I have no trouble inviting someone to lunch.

John Conway has a T-shirt with his theorem on it. I couldn’t miss this picture opportunity and persuaded John to pose for pictures with his back to me. Here is the theorem:

If you continue the sides of a triangle beyond every vertex at the distances equaling to the length of the opposite side, the resulting six points lie on a circle, which is called Conway’s circle.

Poor John Conway had to stand with his back to me until I figured out the proof of the theorem and realized which point must be the center of Conway’s circle.

Heard somewhere:

Teacher: What’s bigger: 22/7 or 3.14?
Student: They are equal.
Teacher: Why do you say that?!
Student: They are both equal to π.

For the last three years I’ve been coming to the Institute for Advanced Study in Princeton every spring for the Women and Mathematics program. Every year I am assigned to an office in the main building: Fuld Hall.

The problem is that there is a different office that I crave. Every year I go and check on it over in Simonyi Hall, where the Mathematics Department is located. This year I took this photo of the empty name-tag, hoping that one day it will say Tanya Khovanova.

Credit cards often keep your mother’s maiden name in their database for security purposes. This so called “security” is based on two assumptions:

• Your mother was married.
• Your mother changed her last name to her husband’s last name.

Were these assumptions true, only your close relatives would know your mother’s maiden name. In reality, if your mother was never married, then your last name is the same as your mother’s last name. So, crooks who are trying to steal identities can try to use your last name as your mother’s presumed maiden name. Very often they will succeed. Besides, many women do not change their last names. If you have a different last name from your mother, but your mother uses her maiden name, then the bank’s security question is not very secure at all.

If you want your identity to be secure you might need to invent a maiden name for your mother. Alternatively, perhaps your parents can tell you a family secret that will help you choose a name that is related to you, but not transparent to the public.

My relative Martin took his wife’s last name after their marriage. Before his children apply for credits cards and bank accounts, he needs to explain to them that it is better for them to use his maiden name as their mother’s maiden name for banking purposes.

I was driving on MassPike when, for no apparent reason, a car driving in the opposite direction started flashing its headlights. I remembered the Russian tradition of informing the oncoming traffic that the police are nearby. So I adjusted my speed and very soon I saw a police car. I got this warm feeling in my heart because I didn’t need to panic or check my speedometer. I mentally thanked that anonymous Russian driver and started wondering why the tradition had not been adopted in the USA. Is it because we are so responsible that we want to punish speeders, or do we think that the police are on our side?

The following problem was sent to me by Joel Lewis.

You have 12 mice, one of which eats faster than all the others. You need to find it. You have a supply of standard cupcakes that you value very much and want to minimize how many of them you have to use. The only way you can find the mouse is to give cupcakes to several groups of mice and see which group is the fastest.

We assume that mice chew at a constant speed and all the mice in one group can attack the cake at the same time. I love this puzzle because I love coin problems. Let me restate the puzzle as a coin problem:

You have 12 coins, one of which is fake and weighs less than all the others. You have a balance scale with multiple pans, that is you can weigh several things at once and order them by weight. You do not care about the total number of weighings as in most classical coin puzzles, instead, this time using a pan is expensive and you want to find the fake coin with as few pan-uses as possible.

Spoiler warning: below I will discuss the solution for n mice.

You can, of course, give a cake to every mouse and see which one finishes first. You can save one cake by giving cakes at the same time to all but one of the mice. If everyone finishes simultaneously, the faster mouse is the unfed one.

It wastes cakes to give them to unequally-sized groups of mice. We can do better by copying the classical way to find a fake coin with the minimum number of weighings. That is, for each test, divide the mice into three groups as evenly as possible and give a cake to each of two equally-sized groups. The number of cakes you use is about 2log₃n.

I wouldn’t have written this essay if that was the solution. Sometimes you can do even better. For example, you can find the faster mouse out of 12 using only 5 cakes.

First, if you give out k cakes in one test, the test tells you which of k+1 groups the mouse is in. In the worst case, the faster mouse will be in the biggest group, so you should minimize the biggest group. Hence, your groups that get cakes should have ⌈n/(k+1)⌉ mice.

A test with one cake gives no information. I argue that giving out more than three cakes doesn’t gain anything. Indeed, suppose we use four cakes in a test. That is, we divide the mice into five groups A, B, C, D and E, of which the first four are the same size. We can simulate the test by two tests in each of which we give out two cakes. In the first test we give cakes to A+B and C+D. If one of the groups is faster, say A+B, then in the second test give cakes to A and B; if not, E has the faster mouse. I leave it as an exercise to simulate a test with more than four cakes.

Thus, in an optimal strategy we can use two or three cakes per test. Also, if you give one test with k − 1 cakes and the next one with m − 1 cakes, you can switch them with the same effect. The largest group after either order of tests will have at most ⌈n/km⌉ mice.

I don’t need two tests of three cakes each, which would give me a group of size at least ⌈n/16⌉. I can achieve the same result with three tests of two cakes each, with the faster mouse restricted to a group of size at most ⌈n/27⌉.

That means all my tests use two cakes, except I might use three cakes once. It doesn’t matter in what order I conduct the tests, so I can wait until the end to use three cakes. I leave it as an exercise to the reader that the only small number of mice for which we would prefer three cakes is four. From this it follows quickly that for numbers of mice between 3 * 3ⁱ + 1 and 4 * 3ⁱ, the number of cakes is 2i + 1. For numbers between 4 * 3ⁱ + 1 and 3ⁱ⁺² the answer is 2i + 2.

A week ago I chatted with my son Sergei about memorable math problems. He mentioned problem 5 from USAMO 2007. The problem can be reduced to the following:

Prove that (x⁷ + 1)/(x + 1) is composite for x = 7⁷ⁿ, where n is a non-negative integer.

Perhaps Sergei remembered this problem because as far as he knew, he was the only one in that competition to solve it. That made me curious as to how he solved it. His solution is available as solution 2 at the Art of Problem Solving website. His solution seemed mysterious and impossible to invent on the spot. I became even more curious to understand the thought process underlying his solution.

Here is his recollection:

We need to factor x⁶ − x⁵ + x⁴ − x³ + x² − x + 1. If such factoring existed it would have been known. Therefore, we need to somehow use the fact that x = 7⁷ⁿ. What is the simplest way to factor? We should try to represent the polynomial in question as the difference of squares. Luckily, x is an odd power of 7. We can make it a square if we multiply or divide it by 7 or another odd power of 7. So with a supply of squares on one side, we need to find a match for one of them to build the difference.

Let us simplify the problem and see what happens for (y³ + 1)/(y + 1) for y = 3³ⁿ, when n = 1. In other words we want to represent 703 as a difference of squares. This can be done: 703 = 28² − 9². Now let us see how we can express 28² and 9² through y which in this case is equal to 27. The first term is (y + 1)², and the second is 3y.

Now let’s go back to 7 and x, and check whether (x + 1)⁶ − (x⁶ − x⁵ + x⁴ − x³ + x² − x + 1) is 7x. Oops, no. The difference is 7x⁵ + 14x⁴ + 21x³ + 14x² +7x. On the plus side, it is divisible by 7x which we know is a square. The leftover factor is x⁴ + 2x³ + 3x² +2x + 1, which is a square of x² +x + 1.

The problem is solved, but the mystery remains. The problem can’t be generalized to numbers other than 3 and 7.

I decided to take a closer look at the Putnam Competition. I analyzed the results of the three top contenders for the best Putnam teams: Harvard, MIT, Princeton. I looked at the annual number of Putnam Fellows from each of these three schools starting from 1994.

As you may notice MIT couldn’t even generate a Putnam Fellow until 2000, but starting from 2003 MIT consistently had more Putnam Fellows than Harvard or Princeton.

Richard Stanley, the coach of the MIT team, kindly sent me the statistics for the most recent competition, held in 2009.

Furthermore, MIT had 40% in the top 5, 33% in the top 15, 32% in the top 25, and 35% in the top 81. For comparison, in the top 81, MIT had 28 winners — more than the next three schools together: Caltech 11, Harvard 9, Princeton 7.

No comment.