Tanya Khovanova's Math Blog

Only at MIT. Room 4-231.

by Tanya Khovanova, Konstantin Knop, Alexey Radul and Peter Sarnak

Let n coins weighing 1, 2, … n be given. Baron Münchhausen knows which coin weighs how much, but his audience does not. Define a(n) to be the minimum number of weighings the Baron must conduct on a balance scale, so as to unequivocally demonstrate the weight of at least one of the coins.

In the paper Baron Münchhausen’s Sequence, three of us completely described the Baron’s sequence. In particular, we proved that a(n) ≤ 2. Here we would like to outline another proof idea, which is interesting in part because it touches the Riemann hypothesis.We denote the total weight of coins in some set A as |A|.

Lemma. Numbers n that can be represented as T_i + T_j + T_k = 3n, where i ≤ j < k, such that there is a subset A of coins from j + 1 to k such that n = T_j + |A|, can be done in two weighings.

Proof. Suppose T_i + T_j + T_k = 3n and there is a subset A of coins from j + 1 to k such that n = T_j + |A|. We propose the two weighings

[1…j] + A = n

and

[1…i] + B = n + A,

where B is the complement of A in {j + 1, j + 2, … , k}.

If we sum up twice the first weighing with the second weighing we get

3[1…i] + 2[(i + 1)…j] + 2A + B = 3n + A.

In other words, three times the weight of the coins that were on the left side in both weighings, plus twice the weight of the coins that were on the left side in only the first weighing, plus the weight of the coins that were moved from the left cup to the right cup plus the weight of the coins on the left cup in only the second weighing equals three times the weight of the coin on the right cup in both weighings. Hence three times the weight of the coin on the right cup in both weighings can’t be less than the weight of the k other coins that participated plus the weight of the j coins that were on the left cup in the first weighing and weren’t moved to the right cup, plus the weight of the i coins that were one the left cup in both the first and the second weighing. But because T_i + T_j + T_k = 3n, then 3n is the smallest possible weight of any set of i plus j plus k coins, the coin on the right cup in both weighings has to be the n-coin.

We checked that any number up to 600,000 except 20 can be represented so as to satisfy the Lemma. To show how to solve 20 coins in two weighings is easy, and, as usual, is left as an exercise for the reader. Next, we want to look at the following lemma.

Lemma. Given a set of consecutive numbers {(j + 1), … , k}, if k > 2j + 2, then it is possible to find a subset in the set that sums up to any number in the range from j + 1 to (j + k + 1)(k – j)/2 – j – 1.

We won’t prove the lemma, but it means that if k is about twice larger than j, then we have a lot of flexibility for building our set A in the weighing above. For moderately large n (where 600000 >> “moderately large”), it is not hard to prove that this flexibility is sufficient.

Now the question becomes: can we find such a decomposition into triangular numbers? It is enough to find a representation T_i + T_j + T_k = 3n, where T_k is at least 81% of 3n.

We know that decompositions into triangular numbers are associated with decompositions into squares. Namely, if T_i + T_j + T_k = 3n, then (2i + 1)² + (2j + 1)² + (2k + 1)² = 24n + 3. If the largest square is at least 81% of 24n + 3, then the largest triangular number in the decomposition of 3n is at least 81%.

There is a theorem (W. Duke, Hyperbolic distribution problems and half-integral weight Maass forms, in Inventiones Math 92 (1988) p.73-90) that states that in the limit the decompositions of numbers into three squares are equidistributed. That is, if we take some region on the unit sphere x² + y² + z² = 1 (for example, the region |z| > 0.8) and view decompositions of 24n + 3 into squares as points on the sphere x² + y² + z² = 24n + 3, then, as n grows, decompositions whose projections fall into our chosen region are guaranteed to appear.

This theorem is great, because it tells us that for large enough n we will always be able to find a decomposition of 24n + 3 into triangle numbers where one of the triangle numbers will be much bigger than the others, and it will be possible to prove the weight of the n coin in two weighings. Unfortunately, this summary, as stated, does not tell us how large that n needs to be. So we need some exact estimates.

The number of decompositions of m into sums of three squares is about the square root of m. More precisely, it is possible to compute a number N, such that for any number m > N, with at most one exception, the number of decompositions is at least Cm^1/2−1/30, where C is a known constant.

The more specific statement of Duke’s theorem is that if the number of solutions to the quadratic x² + y² + z² = 24n + 3 is large, for a computable value of “large”, then the solutions are equidistributed. More precisely, let us denote 3n by m and fix an area Ω on the unit sphere. Then the number of solutions (x, y, z) such that the unit vector (x, y, z)/|(x, y, z)| belongs to Ω is

1/(4π) Ωh(8m+3) + E(m),

where h(8m+3) is the total number of solutions of x² + y² + z² = 24n + 3, and E(m) is an error term, which starting from some number satisfies the inequality: E(m) ≤ 1000m^1/2-1/7.

That’s pretty good, because combining these two lets us, at least in principle, actually calculate an N such that for all n > N except maybe one a(n) = 2. After that we hoped to write a program to exhaustively search smaller numbers by computer.

This situation is still somewhat annoying, because that possible exception must then be propagated into the proof, and if we are not careful, possibly into the final theorem. (“No matter how many coins the Baron has, he can prove the weight of one in at most two weighings, except maybe one number of coins, and we don’t know which…”) This is where the Riemann Hypothesis comes in. If the Riemann Hypothesis is true, then that exception isn’t there, and all is sunlight and flowers.

The beauty of the Baron’s puzzle is such that we actually do not need the Riemann hypothesis. As we can use unbalanced weighings, it is enough to find a good decomposition for one out of the four numbers 3n, 3n-1, 3n-2, or 3n-3.

Instead of finding all these exact estimates we found a different elementary proof of our theorem. But we are excited that methods that are used in very advanced number theory can be used to solve a simple math problem that can be described to middle school children.

It would be great if someone decided to finish this proof.

I am used to thinking that a “woman in numbers” means a female number theorist. But not anymore. I just discovered drawings by Svetlana Bogatyr. From now on the expression a “woman in numbers” will convey an additional meaning to me.

I am grateful to Svetlana for permitting me to post several of her drawings. The “Mature Woman” is on the left. “Eurydice”, “Girl in Scarf” and “Holland Woman ” are below.

Enjoy.

I just invented a two-player game. To start, you have an empty n by n board. When it’s your turn you must write an integer between 1 and n into an empty cell on the board. Your integer has to differ from the integers that are already present in the same row or column. If you finish filling up the board, you will get a Latin square and the game will be a tie. The person who doesn’t have a move loses. What is the best strategy?

Let’s see what happens if n is 2. The first player puts any number in one of the four corners of the 2 by 2 board. The second player wins by placing a different number in the opposite corner.

I played this game with my son Sergei Bernstein on a 3 by 3 board. We discovered that the first player can always win. Since this game is so much fun, I’ll leave it to the reader to play it and to find the winning strategy for the first player.

Can you analyze bigger boards? Remember that this game has many symmetries. You can permute rows and columns. Also, you can permute numbers.

While we were playing Sergei invented two theorems.

Sergei’s theorem 1. If n is odd the first player can guarantee a tie.

Proof. In the first move the first player writes (n+1)/2 in the center cell. If the second player puts number x in any cell the first player puts number n+1−x into the cell that is rotationally symmetric to the second player’s cell with respect to the center. With this strategy the first player will always have a legal move.

Sergei’s theorem 2. If n is even the second player can guarantee a tie.

Proof. If the first player puts number x in any cell the second player puts number n+1−x into the cell that is vertically symmetric to the first player’s cell with respect to the vertical line of symmetry of the board. With this strategy the second player will always have a legal move.

As you play the game, let me know if you develop any theorems of your own.

Suppose you meet a friend who you know for sure has two children, and he says: “I have a son born on Tuesday.” What is the probability that the second child of this man is also a son?

People argue about this problem a lot. Although I’ve discussed similar problems in the past, this particular problem has several interesting twists. See if you can identify them.

First, let us agree on some basic assumptions:

1. Sons and daughters are equally probable. This is not exactly true, but it is a reasonable approximation.
2. For our purposes, twins do not exist. Not only is the proportion of twins in the population small, but because they are born on the same day, twins might complicate the calculation.
3. All days of the week are equally probable birthdays. While this can’t actually be true — for example, assisted labors are unlikely to be scheduled for weekends — it is a reasonable approximation.

Now let us consider the first scenario. A father of two children is picked at random. He is instructed to choose a child by flipping a coin. Then he has to provide information about the chosen child in the following format: “I have a son/daughter born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of two daughters will make such a statement is zero. The probability that a father of differently-gendered children will produce such a statement is 1/14. Indeed, with a probability of 1/2 the son is chosen over the daughter and with a probability of 1/7 Tuesday is the birthday.

The probability that a father of two sons will make this statement is 1/7. Among the fathers with two children, there are twice as many who have a son and a daughter than fathers who have two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 1/2 for the second child to also be a son.

Now let us consider the second scenario. A father of two children is picked at random. If he has two daughters he is sent home and another one picked at random until a father is found who has at least one son. If he has one son, he is instructed to provide information on his son’s day of birth. If he has two sons, he has to choose one at random. His statement will be, “I have a son born on Mon/Tues/Wed/Thurs/Fri/Sat/Sun.” If his statement is, “I have a son born on Tuesday,” what is the probability that the second child is also a son?

The probability that a father of differently-gendered children will produce such a statement is 1/7. If he has two sons, the probability will likewise be 1/7. Among the fathers with two children, twice as many have a son and a daughter as have two sons. Plugging these numbers into the formula for calculating the conditional probability gives us a probability of 1/3 for the second child to also be a son.

Now let us consider the third scenario. A father of two children is picked at random. If he doesn’t have a son who is born on Tuesday, he is sent home and another is picked at random until one who has a son that was born on Tuesday is found. He is instructed to tell you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

The probability that a father of two daughters will have a son born on Tuesday is zero. The probability that a father of differently-gendered children will have a son who is born on Tuesday is 1/7. The probability that a father of two sons will have a son born on Tuesday is 13/49. Among the fathers with two children, twice as many have a son and a daughter than two sons. Plugging these numbers into the formula for calculating the conditional probability will give us a probability of 13/27 for the second child to also be a son.

Now let’s go back to the original problem. Suppose you meet your friend who you know has two children and he tells you, “I have a son born on Tuesday.” What is the probability that the second child is also a son?

What puzzles me is that I’ve never run into a similar problem about daughters or mothers. I’ve discussed this math problem about these probabilities with many people many times. But I keep stumbling upon men who passionately defend their wrong solution. When I dig into why their solution is wrong, it appears that they implicitly assume that if a man has a daughter and a son, he won’t bother talking about his daughter’s birthday at all.

I’ve seen this so often that I wonder if this is a mathematical mistake or a reflection of their bias.

How to solve the original problem? The problem is under-defined. The solution depends on the reason the father only mentions one child, or the Tuesday.

The funny part of this story is that I, Tanya Khovanova, have two children. And the following statement is true: “I have a son born on Tuesday.” What is the probability that my second child is a son?

How many different months’ lengths are possible?

For “simplicity” let’s stick to the Gregorian calendar.

Lennart Green is an amazing magician who performs card tricks. He is so good that the judges at the competition of the International Federation of Magic Societies didn’t believe his tricks. They assumed that he used the help of stooges, and unfairly disqualified him. At the next competition he used a judge to assist him and won first place in the cards category.

I saw his performance twice. Both times he brought a woman to the stage, but each time it was a different woman. It was clear that he talked to each woman before the performance, presumably asking her permission. Furthermore, during his performances, both of the women looked slightly bored, implying that it might be not their first time. My first impression was that the women were a part of the act. I was fooled just as the judges had been fooled.

What can I say? Lennart Green isn’t skilled at picking up the right women. Watch his performance at TED, and remember that he proved that the assistants were clueless.

When the Abel Prize was announced in 2001, I got very excited and started wondering who would be the first person to get it. I asked my friends and colleagues who they thought was the greatest mathematician alive. I got the same answer from every person I asked: Alexander Grothendieck. Well, Alexander Grothendieck is not the easiest kind of person to give a prize to, since he rejected the mathematical community and lives in seclusion.

Years later I told this story to my friend Ingrid Daubechies. She pointed out to me that my spontaneous poll was extremely biased. Indeed, I was asking only Russian mathematicians living abroad who belonged to “Gelfand’s school.” Even so, the unanimity of those responses continues to amaze me.

Now several years have passed and it does not seem that Alexander Grothendieck will be awarded the Prize. Sadly, my advisor Israel Gelfand died without getting the Prize either. I am sure I am biased with respect to Gelfand. He was extremely famous in Soviet Russia, although less well-known outside, which may have affected the decision of the Abel’s committee.

I decided to assign some non-subjective numbers to the fame of Gelfand and Grothendieck. On Pi Day, March 14, 2010, I checked the number of Google hits for these two men. All the Google hits in the rest of this essay were obtained on the same day, using only the full names inside quotation marks.

• Alexander Grothendieck — 95,600
• Israel Gelfand — 47,900

Google hits do not give us a scientific measurement. If the name is very common, the results will be inflated because they will include hits on other people. On the other hand, if a person has different spellings of their name, the results may be diminished. Also, people who worked in countries with a different alphabet are at a big disadvantage. I tried the Google hits for the complete Russian spelling of Gelfand: “Израиль Моисеевич Гельфанд” and got an impressive 137,000.

Now I want to compare these numbers to the Abel Prize winners’ hits. Here we have another problem. As soon as a person gets a prize, s/he becomes more famous and the number of hits increases. It would be interesting to collect the hits before the prize winner is announced and then to compare that number to the results after the prize announcement and see how much it increases. For this endeavor, the researcher needs to know who the winner is in advance or to collect the data for all the likely candidates.

• Jean-Pierre Serre — 63,400
• Michael Atiyah — 34,200
• Isadore Singer — 44,300
• Peter Lax — 118,000
• Lennart Carleson — 47,500
• Srinivasa Varadhan — 15,800
• John Thompson — 1,610,000
• Jacques Tits — 90,900
• Mikhail Gromov — 61,900

John Thompson is way beyond everyone else’s range because he shares his name with a famous basketball coach. But my point is that Gelfand and Grothendieck could have been perfect additions to this list.

I have this fun book at home written by Clifford Pickover and titled Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. It was published before the first Abel Prize was awarded. Chapter 38 of this book is called “A Ranking of the 10 Most Influential Mathematicians Alive Today.” The chapter is based on surveys and interviews with mathematicians.

The most puzzling thing about this list is that there is no overlap with the Abel Prize winners. Here is the list with the corresponding Google hits.

1. Andrew Wiles — 64,900
2. Donald Coxeter — 25,200
3. Roger Penrose — 214,000
4. Edward Witten — 45,700
5. William Thurston — 96,000
6. Stephen Smale — 151,000
7. Robert Langlands — 48,700
8. Michael Freedman — 46,200
9. John Conway — 203,000
10. Alexander Grothendieck — 95,600

Since there are other great mathematicians with a lot of hits, I started trying random names. In the list below, I didn’t include mathematicians who had someone else appear on the first results page of my search. For example, there exists a film director named Richard Stanley. So here are my relatively “clean” results.

• Martin Gardner — 292,000
• Ingrid Daubechies — 76,900
• Timothy Gowers — 90,500
• Persi Diaconis — 84,700
• Michael Sipser — 103,000
• James Harris Simons — 107,000
• Elliott Lieb — 86,100

If prizes were awarded by hits, even when the search is polluted by other people with the same name, then the first five to receive them would have been:

1. John Thompson — 1,610,000
2. Martin Gardner — 292,000
3. Roger Penrose — 214,000
4. John Conway — 203,000
5. Stephen Smale — 151,000

If we had included other languages, then Gelfand might have made the top five with his 48,000 English-language hits plus 137,000 Russian hits.

This may not be the most scientific way to select the greatest living mathematician. That’s why I’m asking you to tell me, in the comments section, who you would vote for.

I got this problem from my friend, a middle-school math teacher, Tatyana Finkelstein.

We have N coins that look identical, but we know that exactly one of them is fake. The genuine coins all weight the same. The fake coin is either lighter or heavier than a real coin. We also have a balance scale.
Unlike in classical math problems where you need to find the fake coin, in this problem your task is to figure out whether the fake coin is heavier or lighter than a real coin. Your challenge is that you are only permitted to use the scale twice. Find all numbers N for which this can be done.

I would like to add an extra twist to the problem above. It is conceivable that there might be several different strategies for finding the direction in which the weight of the fake coin deviates from the real coins. In this case it is better to choose a strategy that can redeem as many coins as possible — that is, to identify the maximum number of coins as real.

The number of coins you identify as real depends on the outcomes of your weighings. Then what is the precise definition of the best strategy?

Let us call a strategy k-redeem if after the weighings you are guaranteed to demonstrate that k coins are real, but you are not guaranteed to demonstrate that k+1 coins are real. Your task is to analyze two-weighing strategies and choose the most profitable one — the strategy that guarantees to redeem the largest possible number of coins, that is, a k-redeem strategy for the largest k.

Sara was born in Boston on February 29, 2008 at 11:00 am. Her parents were quite upset that their calendar-challenged daughter would only be able to celebrate her birthday once in four years. Luckily, science can help Sara’s parents. How? Sara can celebrate her birthday every year at the moment when the Earth passes the same point on its orbit around the Sun as when Sara was born.

Assuming that Sara lives her entire life in Boston and that the daylight savings time is not moved earlier into February, your task is to calculate the schedule of Sara’s birthday celebrations for 100 years starting from her birth. To simplify your homework, you can approximate one year as 365 days and 6 hours.