Tanya Khovanova's Math Blog

Konstantin Knop sent me the following coins puzzle, which was created by Alexander Shapovalov and first appeared at the Regional round of the all-Russian math Olympiad in 2000.

Baron Münchhausen has 8 identical-looking coins weighing 1, 2, …, 8 grams. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct one weighing on a balance scale, so that the guests will be convinced about the weight of one of the coins. Can the Baron do this?

This being a sequence-lover blog, we want to create a sequence out of this puzzle. The sequence is the following: Let the Baron initially have n identical-looking coins that weigh exactly 1, 2, …, n grams. Then a(n) is the minimum number of weighings on a balance scale that the Baron needs in order to convince his guests about the weight of one of those coins.

The original puzzle can be restated as asking whether a(8) = 1. The sequence is defined starting from index 1 and the first several terms are easy to calculate: 0, 1, 1, 1, 2, 1, 1, 1. Can you continue this sequence?

Let’s look at where ones occur in this sequence:

Theorem. If the weight of a coin can be confirmed with one weighing, then one cup of that weighing must contain all the coins with weights from 1 to some i, and the other cup must contain all the coins with weights from some j to n. Furthermore, either the scale must balance, or the cup containing the 1-gram coin must be lighter.

Proof. What does it mean for the Baron to convince his guests about the weight of some coin with one weighing? From the perspective of the guests, a weighing is a number of coins in one cup, a number of coins in the other cup, and a number of coins not on the scale, together with the result the scale shows (one or the other cup heavier, or both the same weight). For the guests to be convinced of the weight of some particular coin, it must therefore be the case that all possible arrangements of coin weights consistent with that data agree on the weight of the coin in question. Our proof strategy, therefore, is to look for ways to alter a given arrangement of coin weights so as to change the weight given to the coin whose weight is being demonstrated, thus arriving at a contradiction.

First, obviously, the coin whose weight k the Baron is trying to confirm has to be alone in its group: either alone on some cup or the only coin not on the scale. After that we can divide the proof of the theorem into several cases.

Case 1. The coin k is on a cup and the scale is balanced. Then we want to show two things: k = n, and the coins on the other cup weigh 1, 2, …, i grams for some i. For the first part, observe that if k < n, then the coin with weight k+1 must not be on the scale (otherwise it would overbalance coin k). Therefore, we can substitute coin k+1 for coin k, and substitute a coin one gram heavier for the heaviest coin that was on the other cup, and produce thereby a different arrangement with the same observable characteristics but a different weight for the coin the Baron claims has weight k.

To prove the second part, suppose the contrary. Then it is possible to substitute a coin 1 gram lighter for one of the coins on the other cup. Now, if coin k-1 is not on the scale, we can also substitute k-1 for k, and again produce a different arrangement with the same observable characteristics but a different weight for the coin labeled k. On the other hand, if k-1 is on the scale but k-2 is not, then we can substitute k-2 for k-1 and then k-1 for k and the weighing is again unconvincing. Finally, if both k-1 and k-2 are on the scale, and yet they balance k, then k=3 and the theorem holds.

Consequently, k = n = 1 + 2 + … + i is a triangular number.

Case 2. The coin k is on the lighter cup of the scale. Then: first, k = 1, because otherwise we could swap k and the 1-gram coin, making the light cup lighter and the heavy cup heavier or unaffected; second, the 2-gram coin is on the heavy cup and is the only coin on the heavy cup, because otherwise we could swap k with the 2-gram coin and not change the weights by enough to affect the imbalance; and finally n = 2 because otherwise we could change the weighing 1 < 2 into 2 < 3.

Thus the theorem holds, and the only example of this case is k = 1, n = 2.

Case 3. The coin k is on the heavier cup of the scale. Then k = n and the lighter cup consists of some collection of the lightest available coins, by the same argument as Case 1 (but even easier, because there is no need to maintain the balance). Furthermore, k must weigh exactly 1 gram more than the lighter cup, because otherwise, k-1 is not on the lighter cup and can be substituted for k, making the weighing unconvincing.

Consequently, k = n = (1 + 2 + … + i) + 1 is one more than a triangluar number.

Case 4. The coin k is not on a cup and the scale is not balanced. Then, since k must be off the scale by itself, all the other coins must be on one cup or the other. Furthermore, all coins heavier than k must be on the heavier cup, because otherwise we could make the lighter cup even lighter by substituting k for one of those coins. Likewise, all coins lighter than k must be on the lighter cup, because otherwise we could make the heavier cup even heavier by substituting k for one of those coins. So the theorem holds; and furthermore, the cups must again differ in weight by exactly 1 gram, because otherwise we could swap k with either k-1 or k+1 without changing the weights enough to affect the result on the scale.

Consequently, the weight of the lighter cup is k(k-1)/2, the weight of the heavier cup is 1 + k(k-1)/2. Thus the total weight of all the coins is n(n+1)/2 = k²+1. In other words, case 4 is possible iff n is the index of a triangular number that is one greater than a square.

Case 5. The coin k is not on a cup and the scale is balanced. This case is hairier than all the others combined, so we will take it slowly (noting first that all the coins besides k must be on some cup).

Lemma 1. The two coins k-1 and k-2 must be on the same cup, if they exist (that is, if k > 2). Likewise k-2 and k-4; k+1 and k+2; and k+2 and k+4.

Proof. Suppose they’re not. Then we can rotate k, k-1, and k-2, that is, put k on the cup with k-1, put k-1 on the cup with k-2, and take k-2 off the scale. This makes both cups heavier by one gram, producing a weighing with the same outward characteristics as the one we started with, but a different coin off the scale. The same argument applies to the other three pairs of coins we are interested in, mutatis mutandis.

Lemma 2. The four coins k-1, k-2, k-3 and k-4 must be on the same cup if they exist (that is, if k ≥ 5).

Proof. By Lemma 1, the three coins k-1, k-2, and k-4 must be on the same cup. Suppose coin k-3 is on the other cup. Then we can swap k-1 with k-3 and k with k-4. Each cup becomes heavier by 2 grams without changing the number of coins present, the balance is maintained, and the Baron’s guests are not convinced.

Lemma 3. If coin k-4 exists, that is if k ≥ 5, all coins lighter than k must be on the same cup.

Proof. By Lemma 2, the four coins k-1, k-2, k-3 and k-4 must be on the same cup. Suppose some lighter coin is on the other cup. Call the heaviest such coin c. Then, by choice of c, the coin with weight c+1 is on the same cup as the cluster k-1, …, k-4, and is distinct from coin k-2 (because c is on a different cup from k-3). We can therefore swap c with c+1 and swap k with k-2. This increases the weight on both cups by 1 gram without changing how many coins are on each, but moves k onto the scale. The Baron’s guests are again unconvinced.

Lemma 4. The theorem is true for k ≥ 5.

Proof. By Lemma 3, all coins lighter than k must be on the same cup. Further, if a coin with weight k+4 exists, then by the symmetric version of Lemma 3, all coins heavier than k must also be on the same cup. They must be on the other cup from the coins lighter than k because otherwise the scale wouldn’t balance, and the theorem is true.

If no coin with weight k+4 exists, that is, if n ≤ k+3, how can the theorem be false? All the coins lighter than k must be on one cup, and their total weight is k(k-1)/2. Further, in order to falsify the theorem, at least one of the coins heavier than k must also be on that same cup. So the minimum weight of that cup is now k(k-1)/2 + k+1. But we only have at most two coins for the other cup, whose total weight is at most k+2 + k+3 = 2k + 5. For the scale to even have a chance of balancing, we must have

k(k-1)/2 + k+1 ≤ 2k + 5 ⇔ k(k-1)/2 ≤ k + 4 ⇔ k(k-1) ≤ 2k + 8 ⇔ k² – 3k – 8 ≤ 0.

Finding the largest root of that quadratic we see that k < 5.

So for k ≥ 5, the collection of all coins lighter than k is heavy enough that either one needs all the coins heavier than k to balance them, or there are enough coins heavier than k that the theorem is true by symmetric application of Lemma 3.

Completion of Case 5. It remains to check the case for k < 5. If n > k+3, then coin k+4 exists. If so, all the coins heavier than k must be on the same cup. Furthermore, since k is so small, they will together weigh more than half the available weight, so the scale will be unbalanceable. So k < 5 and n ≤ k+3 ≤ 7.

For lack of any better creativity, we will tackle the remaining portion of the problem by complete enumeration of the possible cases, except for the one observation that, to balance the scale with just the coin k off it, the total weight of the remaining coins, that is, n(n+1)/2 – k must be even. This observation cuts our remaining work in half. Now to it.

Case 5. Seven Coins. n = 7. Then 5 > k ≥ n – 3 = 4, so k = 4. Then the weight on each cup must be 12. One of the cups must contain the 7 coin, and no cup can contain the 4 coin, so the only two weighings the Baron could try are 7 + 5 = 1 + 2 + 3 + 6, and 7 + 3 + 2 = 1 + 5 + 6. But the first of those is unconvincing because k+1 = 5 is not on the same cup as k+2 = 6, and the second because it has the same shape as 7 + 3 + 1 = 2 + 4 + 5 (leaving out the 6-gram coin instead of the asserted 4-gram coin).

Case 5. Six Coins. n = 6. Then 5 > k ≥ n – 3 = 3, and n(n+1)/2 = 21 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 9. The 6-gram coin has to be on a cup and the 3-gram coin is by presumption out, so the Baron’s only chance is the weighing 6 + 2 + 1 = 4 + 5, but that doesn’t convince his skeptical guests because it looks too much like the weighing 1 + 3 + 4 = 6 + 2.

Case 5. Five Coins. n = 5. Then 5 > k ≥ n – 3 = 2, and n(n+1)/2 = 15 is odd, so k must also be odd. Therefore k=3, and the weight on each cup must be 6. The only way to do that is the weighing 5 + 1 = 2 + 4, which does not convince the Baron’s guests because it looks too much like 1 + 4 = 2 + 3.

Case 5. Four Coins. n = 4. Then the only way to balance a scale using all but one coin is to put two coins on one cup and one on the other. The only two such weighings that balance are 1 + 2 = 3 and 1 + 3 = 4, but they leave different coins off the scale.

The remaining cases, n < 4, are even easier. That concludes the proof of Case 5.

Consequently, by the argument similar to the one in case 4 we can show that the number of coins in case 5 must be the index of a square triangular number.

This concludes the proof of the theorem.

Now we can describe all possible numbers of coins that allow the Baron to confirm a coin in one weighing, or, in other words, the indices of ones in the sequence a(n). The following list corresponds to the five cases above:

1. n is a triangular number. For example, for six coins the weighing is 1+2+3 = 6.
2. n = 2. The weighing is 1 < 2.
3. n is a triangular number plus one. For example, for seven coins the weighing is 1+2+3 < 7.
4. n is the index of a triangular number that is a square plus one. For example, the forth triangular number, which is equal to ten, is one greater than a square. Hence the weighing 1+2 < 4 can identify the coin that is not on the cup. The next number like this is 25. And the corresponding weighing is 1+2+…+17 < 19+20 +…+25.
5. n is the index of a square triangular number. For example, we know that the 8th triangular number is 36, which is a square: our original problem corresponds to this case.

If we have four coins, then the same weighing 1+2 < 4 identifies two coins: the coin that weighs three grams and is not in a cup and the coin weighing four grams that is in a cup. The other case like this is for two coins. Comparing them to each other we can identify each of them. It is clear that there are no other cases like this. Indeed, for the same weighing to identify two different coins, it must be the n-gram on the cup, and the n-1 coin off the scale. From here we can see that n can’t be big.

As usual we want to give something to think about to our readers. We have given you the list of sequences describing all the numbers for which the Baron can prove the weight of one coin in one weighing. Does there exist a number greater than four that belongs to two of these sequences? In other words, does there exist a total number of coins such that the Baron can have two different one-weighing proofs for two different coins?

To conclude this essay we would like to note that the puzzle we are discussing is related to the puzzle in one of Tanya’s previous posts:

You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same, except for their labels. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

The latter puzzle appeared at the last round of Moscow math Olympiad in 1991. The author of this problem was Sergey Tokarev.

Here is a palindrome problem by Nazar Agakhanov from the All-Russian Mathematical Olympiad, 1996:

Can the number obtained by writing the numbers from 1 to n, one after another, be a palindrome?

Of course, we should assume that n > 1.

When I give this problem to my friends, they immediately answer, “No, of course not.” The reasoning is simple. The last 9 digits of this palindrome should be 987654321 — all different digits. The earliest you can get these digits at the end of your string 1 to n, is when your number n is actually 987654321. By that time your string of digits is really huge. If we take a random number with 2k digits, then the probability of it being a palindrome is 10^(-k). There is no reason to think that writing consecutive integers increases the probability of finding a palindrome. So the probability of hitting a palindrome is so low, that you can safely answer, “No, of course not.”

After confidently saying “no”, my friends usually stop thinking about the problem altogether. Only my friend David Bernstein suggested a simple solution for this problem. You can try to find the proof, but I do not insist that you do. I am about to give you many other fun problems to solve, and you can choose which ones you want to think about.

Naturally, we can replace the sequence of natural numbers in the Agakhanov’s problem with any sequence. So, one problem becomes 160,000 different problems when you plug all current sequences from the Online Encyclopedia of Integer Sequences into it.

For some periodic sequences every concatenation you create is a palindrome. For example, for the sequence of all zeroes, every set of the first n terms is a palindrome. More interestingly, you can think of an increasing sequence such that any first n terms comprise a palindrome, as we see in the sequence of repunits: 1, 11, 111, 1111, etc. Can you think of other sequences like this?

For some sequences, not every concatenation you create is a palindrome, but you can obtain an infinite number of palindromes. One example, suggested by Sergei Bernstein, is the sequence a(n) of the last digit of the greatest power of 2 that divides n. Can you think of other sequences like that?

For some sequences only the initial term itself is a palindrome. Beyond that you can’t obtain a palindrome by concatenating the first n terms. For a few of those sequences, this fact is easy to prove. Take, for example, the sequence of powers of ten, or the sequence of squares, or the sequence of prime numbers. Can you think of other similar sequences?

There are many sequences that do not produce a palindrome beyond the first term, even if you try many times. I suspect that they do not, in fact, ever produce a palindrome, but I have no clue how to prove that. I have in mind the sequence of the digits of π. Can you suggest other sequences like that?

Instead of solving the initial problem, I gave you a variety of other problems. My last challenge for you is to find other sequences that can replace the sequence of natural numbers in the Agakhanov’s problem so that the problem becomes solvable and the solution is interesting.

In 2007 Alexander Shapovalov suggested a very interesting coin problem. Here is the kindergarten version:

You present 100 identical coins to a judge, who knows that among them are either one or two fake coins. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly two fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly two fake coins without revealing any information about any particular coin?

To solve this problem, divide the coins into two piles of 50 so that each pile contains exactly one fake coin. Put the piles in the different cups of the scale. The scale will balance, which means that you can’t have the total of exactly one fake coin. Moreover, this proves that each group contains exactly one fake coin. But for any particular coin, the judge won’t have a clue whether it is real or fake.

The puzzle is solved, and though you do not reveal any information about a particular coin, you still give out some information. I would like to introduce the notion of a revealing coefficient. The revealing coefficient is a portion of information you reveal, in addition to proving that there are exactly two fake coins. Before you weighed them all, any two coins out of 100 could have been the two fakes, so the number of equally probable possibilities was 100 choose 2, which is 5050 4950. After you’ve weighed them, it became clear that there was one fake in each pile, so the number of possibilities was reduced to 2500. The revealing coefficient shows the portion by which your possibilities have been reduced. In our case, it is (5050 − 2500)/5050 (4950-2500)/4950, slightly more less than one half.

Now that I’ve explained the kindergarten version, it’s time for you to try the elementary version. This problem is the same as above, except that this time you have 99 coins, instead of 100.

Hopefully you’ve finished that warm-up problem and we can move on to the original Shapovalov’s problem, which was designed for high schoolers.

A judge is presented with 100 coins that look the same, knowing that there are two or three fake coins among them. All the real coins weigh the same and all the fake coins weigh the same, but the fake coins are lighter than the real ones.

You yourself know that there are exactly three fake coins and you know which ones they are. Can you use a balance scale to convince the judge that there are exactly three fake coins, without revealing any information about any particular coin?

If you are lazy and do not want to solve this problem, but not too lazy to learn Russian, you can find several solutions to this problem in Russian in an essay by Konstantin Knop.

Your challenge is to solve the original Shapovalov puzzle, and for each solution to calculate the revealing coefficient. The best solution will be the one with the smallest revealing coefficient.

My son, Sergei Bernstein, got accepted to MIT through early action. Because the financial costs of studying at MIT worried me, I insisted that Sergei also apply to Princeton and Harvard, as I had heard they give generous financial packages. In the end, Sergei was rejected by Princeton and wait-listed and finally rejected by Harvard. Though many people have been rejected by Princeton and Harvard, not too many of them have won places on US teams for two different international competitions — one in mathematics and the other in linguistics. To be fair, Sergei was accepted by these teams after Princeton had already rejected him. Nonetheless, Sergei has an impressive mathematical resume:

• In 2005 he was the National MathCounts Written Test Champion.
• In 2005 he was the National MathCounts Master’s Round Champion.
• In 2007 and 2009 he was a USAMO winner.
• In 2008 he passed Math 55a at Harvard taught by Dennis Gaitsgory, which is considered to be the hardest freshman math course in the country. More than 30 students started it and less than 10 finished. Sergei was one of the finishers, and he was only a high school junior.
• In 2007, 2008 and 2009 he competed at a 12th grade level at the Math Kangaroo, while he actually was in 10th, 11th and 12th grade. He placed first all three times.
• In 2009 he was on the US team at the Romanian Masters in Mathematics competition, which might be a harder competition than the International Mathematical Olympiad. He got a silver medal and was second on the US team.
• In 2009 he placed 5th in the North American Computational Linguistics Olympiad, making it to the Alternate US Team for the International Linguistics Olympiad.

I am trying to analyze why he was rejected and here are my thoughts.

1. His application forms to Harvard and Princeton were different from MIT. Yes, MIT was his first choice and he wrote a customized essay for MIT. For other places he had a common essay. But as he was supposed to be flagged as a top math student, his essay should have been irrelevant, in my opinion.
2. Admissions offices made a mistake. I can imagine that admissions offices never heard of the Romanian Masters in Mathematics competition, because it is a relatively new competition and the USA only joined it in 2009 for the first time. On its own, though, it should have sounded impressive. Also, they might not have known about the Math 55 course at Harvard, as usually high-schoolers do not take it. But that still leaves many other achievements. Many people told me that admissions offices know what they are doing, so I assume that I can disregard this point.
3. Princeton and Harvard knew that he wanted to go to MIT and didn’t want to spoil their admission rate. I do not know if colleges communicate with each other and whether Princeton and Harvard knew that he was admitted early to MIT. Because he had sent them a common application essay, they may have been suspicious that they weren’t his first choice.
4. Harvard and Princeton didn’t want him. I always heard that Harvard and Princeton want to have well-rounded people, whereas MIT likes geeks. I consider Sergei quite well-rounded as he has many other interests and achievements beyond mathematics. Perhaps his other accomplishments aren’t sufficiently impressive, making him less round than I thought he was.
5. Harvard and Princeton are not interested in mathematicians. Many people say that they want future world leaders. I think it is beneficial for a world leader to have a degree in math, but that’s just my personal opinion. And of course, to support their Putnam teams, it is enough to have one exceptional math student a year.
6. Sergei couldn’t pay. Yes, we marked on the application that we need financial help. In the current financial crisis it could be that even though Harvard and Princeton do not have enough money to support students, they do not want to go back and denounce their highly publicized generosity.

Many people told me of surprising decisions by Ivy League schools this year. The surprises were in both directions: students admitted to Ivy League colleges who didn’t feel they had much of a chance and students not admitted that had every right to expect a positive outcome. I should mention that I personally know some very deserving kids who were admitted.

I wonder if there has been a change in the financial demographics of the students Harvard and Princeton have accepted this year. If so, this will be reflected in the data very soon. We will be able to see if the average SAT scores of students go down relative to the population and previous years.

I do not know why Sergei wasn’t accepted; perhaps I’m missing something significant. But if it was because of our finances, it would be ironic: Sergei wasn’t admitted to Princeton and Harvard for the same reason he applied there.

There is interesting data to show that MIT takes math students more seriously than Harvard and Princeton. By Michael Sipser’s suggestion I looked at the Putnam Competition results. Out of the top 74 scorers of 2007, 21 were from MIT, 9 from Harvard and 7 from Princeton. Keep in mind that the total freshman enrollment at MIT is much lower than at Harvard or Princeton. This story repeated itself in 2008: out of top 79 scorers 23 were from MIT, 11 from Harvard and 11 from Princeton.

Ironically, MIT’s team didn’t win Putnam in those years. MIT’s team won the third place after Harvard and Princeton. If you look at the results more closely, you will notice that had MIT arranged teams differently, MIT would have won.

It appears that MIT put their three top scorers from the previous year on their lead team. MIT shouldn’t assume that those three continue to be their strongest competitors. Instead they should probably test their students right before the Putnam competition, because if you look at MIT’s top individual performers, had they been on a team together, they would have won.

Maybe MIT should rethink its algorithm for creating teams, or maybe we should just wait. As it is obvious that MIT is more serious about math, all top math students may want to go to MIT in coming years. If this happens, the mathematics field will be absolutely dominated by MIT.

A long ago my son Sergei went to the Streamline School Olympiad. Some of the problems were really nice and I asked the organizer, Oleg Kryzhanovsky, where he took the problems from. It seems that he himself supplied all the problems, many of which are his original creations. He told me that he can invent a math Olympiad problem on demand for any level of difficulty on any math topic. No wonder that he is the author of almost all math problems at the Ukraine Olympiad.

The following is a sample of his problems from the Streamline Olympiad. For my own convenience I have chosen problems without figures and equations. Note: I edited some of them.

1998 (8th – 9th grade). Find three numbers such that each of them is a square of the difference of the two others.

1999 (9th – 10th grade). The positive integers 30, 72, and N have a property that the product of any two of them is divisible by the third. What is the smallest possible value of N?

1999 (9th – 10th grade). You have 6 coins weighing 1, 2, 3, 4, 5 and 6 grams that look the same. The number (1, 2, 3, 4, 5, 6) on the top of each coin should correspond to its weight. How can you determine whether all the numbers are correct, using the balance scale only twice?

1999 (11th – 12th grade). In how many ways can the numbers 1, 2, 3, 4, 5, 6 be ordered such that no two consecutive terms have a sum that is divisible by 2 or 3.

2000 (6th – 7th grade). Let A be the least integer such that the sum of all its digits is equal to 2000. Find the left-most digit of A.

2000 (8th grade). You have six bags with coins that look the same. Each bag has an infinite number of coins and all coins in the same bag weigh the same amount. Coins in different bags weigh 1, 2, 3, 4, 5 and 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times do you need to weigh coins in order to confirm that the labels are correct?

Until the introduction of the Abel prize, the Fields medal was the most prestigious prize in mathematics. The medal has been awarded 48 times and all of the recipients have been men. Can we conclude that women are inferior to men when it comes to very advanced mathematics? I do not think so.

The Fields medal was designed for men; it is very female-unfriendly. It is the prize for outstanding achievement made by people under age 40. Most people start their research after graduate school, meaning that people have 10-15 years to reach this outstanding achievement. If a woman wants to have children and devote some time to them, she needs to do it before she is 40. That puts her at a big disadvantage for winning the medal.

Recently the Abel prize for mathematics was introduced. This is the math equivalent of a Nobel prize and nine people have received the prize, all of them male. The Wolf prize is another famous award: 48 people have received it so far and they too have all been male.

On the grand scale of things, women have only recently had the option of having a career in mathematics. Not so long ago it was considered quite exceptional for a woman to work in mathematics. The number of female mathematicians is increasing, but as this is a new trend, they are younger people. At the same time, Abel prizes and Wolf prizes are given to highly accomplished and not-so-young people. That means the increase in the percentage of women PhDs in mathematics might affect the percentage of females getting the prize, but with a delay of several dozen years.

There are other data covering extreme math ability. I refer to the International Math Olympiad. The ability that is needed to succeed in the IMO is very different from the ability required to succeed in math research. But still they are quite similar. The IMO data is more interesting in the sense that the girls who participate are usually not yet distracted by motherhood. So in some sense, the IMO data better represents potential in women’s math ability than medals and prizes.

Each important math medal or prize is given to one person a year on average. So the IMO champion would be the equivalent of the Fields medal or the Wolf prize winner. While no girl was the clear best in any particular year, there were several years when girls tied for the best IMO score with several other kids. For example:

• In 1995, 14 students tied for the perfect score; two of them were girls. (Maryam Mirzakhani and Chenchang Zhu)
• In 1994, 22 students tied for the perfect score; two of them were girls. (Theresia Eisenkölbl and Catriona Maclean)
• In 1991, 9 students tied for the perfect score; one of them was a girl. (Evgenia Malinnikova)
• In 1990, 4 students tied for the perfect score; one of them was a girl. (Evgenia Malinnikova)
• In 1987, 22 students tied for the perfect score; one of them was a girl. (Jun Teng)
• In 1984, 8 students tied for the perfect score; one of them was a girl. (Karin Gröger)

In one of those years, a girl might have been the best, but because the problems were too easy, she didn’t have a chance to prove it. Evgenia Malinnikova was an outstanding contender who twice had a perfect score. In 1990, she was one out of four people, and she was younger than two of them, as evidenced by the fact they they were not present in 1991. Only one other person — Vincent Lafforgue — got a perfect score in 1990 and 1991. We can safely conclude that Evgenia was one of two best people in 1990, because she was not yet a high school senior.

This might be a good place to boast about my own ranking as IMO Number Two, but frankly, older rankings are not as good as modern ones. Fewer countries were participating 30 years ago, and China, currently the best team, was not yet competing.

Girls came so close to winning the IMO that there is no doubt in my mind that very soon we will see a girl champion. The Fields medal is likely to take more time.

Today I have my first invited guest blogger, J.B. He is a 2006, 2007, 2008 and 2009 USAMO qualifier. He was also selected to be on the US team at the Romanian Masters in Mathematics competition. Also, he placed 6th at the North American Computational Linguistics Olympiad. Here is his piece:

The analysis is based on the list of 2009 USAMO qualifiers.

There is a rule that if nobody naturally qualifies for the USAMO from a state, then the highest scoring individual will qualify. Unfortunately, this means that we must remove those states with only one USAMO qualifier. We have 33 states remaining. If we sort these strictly by number of USAMO qualifiers, then we find the following result.

States with at least 4 USAMO qualifiers (24 total) voted for Obama, with the following exceptions: Georgia, Texas, South Carolina, and Missouri. In addition, of the two states with 3 USAMO qualifiers, one voted for Obama and one for McCain. The remaining states with 2 qualifiers (5 total) voted Republican.

Now this is not really unexpected. States with very large populations tend to be democratic and also produce more USAMO qualifiers. The most notable exceptions are Georgia and Texas, both of which were indeed exceptions (major outliers, in fact) above. This prompts the following consideration.

States with at least 8 USAMO qualifiers per 10 million residents (25 total) voted for Obama, with the following exceptions: Florida, Wisconsin, South Carolina, Missouri, and Georgia. Of these, all but Georgia fall within 50% of the target 8 USAMO qualifiers per 10 million residents. Georgia has 18 qualifiers per 10 million residents. Note also that the entire USA has 16 qualifiers per 10 million residents.

Furthermore, if USAMO qualifiers had been used instead of population for determining electoral votes, Obama would have won with 86% of the vote rather than 68%. In general, if the Democrat can secure all those states with at least 1 qualifier per million residents (plus DC), he will win with 303 votes. He can even lose the three red states in that category (Georgia, Missouri, and South Carolina) for exactly 269.

USAMO qualifiers per 10 million residents (for states with more than one qualifier) are:

• NH — 122 (all of their qualifiers are from Phillips Exeter Academy)
• MA — 55
• ME — 30
• CA — 29
• NJ — 29
• CT — 29
• VA — 28
• MD — 25
• WA — 21
• IN — 19
• OR — 19
• NY — 18
• GA — 18
• IA — 17
• NM — 15
• MI — 15
• PA — 14
• MO — 14
• SC — 13
• IL — 13
• NC — 13
• OH — 9
• CO — 8
• MN — 8
• UT — 7
• KS — 7
• WI — 7
• KY — 7
• TX — 7
• FL — 6
• LA — 5
• AL — 4
• TN — 3

The states with only one USAMO qualifier are WY, VT, ND, AK, SD, DE, MT, RI, HI, ID, NE, WV, NV, AR, MS, OK, and AZ. The only blue one of these which falls below 8 qualifiers per 10 million is Nevada (we would expect it to have at least 2 qualifiers to fit the expected pattern). Otherwise, it is at least possible that each state fits the pattern of 8 qualifiers per 10 million residents if and only if it votes Democratic.

Testing in the US is dominated by multiple-choice questions. Together with the time limit, this encourages students to stop thinking and go for guessing. I recently wrote an essay AMC, AIME, USAMO Contradiction, in which I complained about the lack of proofs in the first two rounds of math competitions.

Is there a way to improve the situation? I grew up in the USSR, where each round of the math competition had the same format: you were given several hours to write proofs for three or four difficult problems. There are two concerns with organizing a competition in this way. First, the Russian system is much more expensive, whereas the US’s multiple choice tests can be inexpensively checked by a computer. Second, the Russian system is prone to unfairness. You need many math teachers to check all these papers on the highest level. Some of these teachers might not be fully qualified, and it is difficult to ensure uniform checking. This system can’t easily be adopted in the US. I am surprised I haven’t heard of lawsuits challenging USAMO results, but if we were to start having proofs at the AMC level with several hundred thousand participants, we would get into lots of trouble.

An interesting compromise was introduced at the Streamline Olympiad. The problems were multiple choice, but students were also requested to write proofs. Students got two points for a correct multiple choice answer, and if the choice was correct the proof was checked. Students could get up to three points for a correct proof. This idea solves two issues. The writing of proofs is rewarded at an early stage and the work of the judges is not as overwhelming as it would have been, had they needed to check every proof. However, there is one problem that I discussed in previous posts that this method doesn’t solve: with multiple choice, minor mistakes cost you the whole problem, even though you might have been very close to a solution. If we want to reward thinking more than accuracy, the proof system allows us to give credit for partial solutions.

I can suggest another approach. If the Russians require proofs for all problems and the Americans don’t require proofs for any problem, why not compromise and require a proof for one problem out of the set.

But I actually have a bigger idea in mind. I think that current development in artificial intelligence may soon help us to check the proofs with the aid of a computer. Artificial intelligence is still far from ready to validate that a mathematical text a human has produced constitutes a proof. But in this particular case, we have two things working for us. First, we can use humans and computers together. Second, we do not need to check the validity of any random proof; we need to check the validity of a specific proof of a simple problem that we know in advance, thus allowing us to prepare the computers.

Let us assume that we already can convert student handwriting into computer-legible text or that students write directly in LaTeX.

Here is the plan. Suppose for every problem, we create a database of some sample right, wrong and partial solutions with corresponding scores. The computer checks the students’ solutions against the given sample. Hopefully, the computer can recognize small typos and deviations that shouldn’t change the point value. If the computer encounters a solution that is significantly different from the ones in the sample, it sends the solution to human judges. Humans decide how to score the solution and the solution and its score is added to the sample database.

For this system to work, computers should be smart enough not to send too many solutions to humans. So how many is too many? My estimate is based on the idea that we wouldn’t want the budget of AMC to go too much higher than the USAMO budget. Since USAMO has 500 participants, judges check just a few hundred solutions to any particular problem. With several hundred thousand participants in AMC, the computer would have to be able to cluster all the solutions into not more than a few hundred groups. The judges only have to check one solution in each group.

As a bonus, we can create a system where for a given solution that is not in the database, the computer finds the closest solution and highlights the difference, thus simplifying the human’s job.

In order to improve math education, we need to add proofs when teaching math. My idea might also work for SATs and for other tests.

Now that there is more money available for education research, would anyone like to explore this?

To get to the national swimming championship, you need to win the state running championships.

What? Is that a joke? Perhaps you’re having the same reaction. Because this is exactly what is happening with math competitions. The official USA math competition has three rounds: AMC, AIME and USAMO.

AMC is a multiple-choice competition with 25 problems in 75 minutes. To be good at it, you need speed, accuracy and the ability to guess well.

AIME is 3 hours long and has 15 problems. The problems are a different level of difficulty and guessing will not help you. Though AIME is also multiple-choice, unlike AMC where you choose out of 5, in AIME you choose out of 1,000. But you still need speed and accuracy. A small arithmetic mistake will cost you the whole problem.

USAMO is a competition that runs for 9 hours and has 6 problems. The problems are much harder and you have to write proofs. Proofs? What proofs? Where are the proofs coming from? It is like you got to the national swimming championship because you are a great runner, but you do not know how to swim.

As the result of this system of selection, the USA team at the International Math Olympiad has diverse skills: these kids are good at all three types of the math competitions. It is like taking an Olympic triathlon team to the Olympic swimming event.

However, the US loses by selecting in this way. There are many kids who are great mathematicians: they may be good at difficult problems but not that good at speed-racing problems. An arithmetic mistake costs you only one point at IMO, but a whole problem at AIME. There are kids who are deep mathematicians prone to small arithmetic mistakes. They could get a gold medal at IMO, but they can’t pass AMC or AIME.

Not only that. As many AMC problems are boring and do not require ideas, AMC might discourage kids from all math competitions at an early stage.

I will write later with my ideas about how to change AMC. Right now I would like to offer a solution to a smaller problem. I am sure that the US math team organizers know many cases in which a non-senior kid does great at USAMO and is potentially a team member for the next year’s US IMO team, but, oops, next year he can’t pass AMC.

I suggest the following: USAMO participants are allowed to go to next year’s AIME no matter what their AMC scores are. USAMO winners are allowed to go to the next year’s USAMO no matter what their AIME results are. This way kids who have proved that they are great swimmers do not need to compete in running again.