Tanya Khovanova's Math Blog

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.

I have forgotten all the problems from the math Olympiads I participated in, except for one. That problem cost me one point, and as result I didn’t get a perfect score. Here is Problem Number 4 from the 1976 IMO:

Determine the greatest number that is the product of some positive integers, and the sum of these integers is 1976.

The solution goes like this. Consider a partition of 1976. If there is an integer x in the partition greater than 5, then replacing it with two integers x-2 and 2 gives a bigger product. Replacing 4 in the partition by 2 and 2 doesn’t change the product. On the other hand, if there is 1 in the partition, it is profitable to attach it to any other number: to replace 1 and x by x+1.

That means the maximum-product partition of a number greater than one has to consist only of twos and threes. If we have three twos in the partition, we can replace them by two threes, thus increasing the product. That means that our partition should consist of twos and threes, and the number of twos shouldn’t be greater than three.

I lost my point when I made an elementary arithmetic mistake while calculating the remainder of 1976 modulo 3.

Let’s generalize this problem for any number n. If we define the maximum product of partitions a(n) as a function of the number n, we get the sequence A000792 in the Encyclopedia of Integer Sequences. This sequence has other interesting definitions, which appear if we add some structure to partitions of n.

For example, we can suppose that our n is not just a number, but it also represents n objects that are being permuted by the symmetric group S_n. In this case, we can associate some Abelian subgroups of the symmetric group with every partition. Namely, we can divide the set of n elements into disjoint subsets of sizes corresponding to our partition and cycle the elements in every subset. The product of these cycles is an Abelian subgroup, the order of which doesn’t depend on how exactly we partition or how we cycle. This order is the product of the partition numbers. It appears that we can get all maximal Abelian subgroups of the symmetric group in this manner. Thus the sequence a(n) is the maximum size of the maximal Abelian subgroup in a symmetric group S_n.

We can do something else with our n objects. Suppose they are represented by vertices of a graph. We take any partition of n and divide our graph into groups of vertices according to this partition. Next we connect vertices of the graph that belong to different groups. If we take a vertex from every group, then the corresponding subgraph is a clique. We can see that it is a maximal clique as two vertices from the same group are never connected and we can’t add any more vertices. The number of different cliques of this size is the product of the number of elements in every group. We can prove that a(n) is the maximum possible number of maximal cliques in a graph with n vertices.

Even though I can’t return to 1976 to correct my stupid mistake, I love this problem and the corresponding sequence.

A new study is out. Dr. Satoshi Kanazawa blogged about his new discovery. He claims that he can explain why many studies show that men have higher intelligence than women. In his posting Why men are more intelligent than women he posits that intelligence is correlated with height. Taller men on average are smarter than shorter men.

He also claims that given the same height, women are more intelligent than men. As he puts it: “Women who are 5’10” are on average more intelligent than men who are 5’10”.” According to him the only problem women have in the brains department is that they aren’t tall enough.

I couldn’t find the study itself, only his own announcement. My problem with his study is that, according to Dr. Kanazawa’s description, he used data from the National Longitudinal Study of Adolescent Health. If we are talking about adolescents we need to take into account that children grow taller and smarter with age. So any difference in intelligence among the kids of different heights may easily be explained by age. Taller boys may be older and therefore likely to perform better on intelligence tests.

As to intelligence differences between boys and girls of the same height, these girls who are 5’10” may be from higher grades than boys who are 5’10”.

Some IQ tests are designed to take age into account, but what’s totally weird is that a scientist is studying the correlation of intelligence and height, using a population that is in the middle of a physical and mental growth spurt.

As a mathematician, I’ve been around many people of great intelligence, but I’ve never perceived bright people as especially tall.

Here is the picture of the USAMO winners for 2007. These are certainly extremely smart kids and I know their heights. The sixth student on the left is my son, Sergei. I personally met all these kids and compared to their peers they are not — except for one boy — especially tall.

How many disjoint letters “O” can you draw on a plane? Clearly, the answer is infinitely many. Now the real question is whether this number can be uncountable. We assume that the letter “O” is just a circle. In this case, if we draw all possible concentric circles, we get an uncountable number of circles. I call letters for which you can build a disjoint uncountable set on the plane stackable letters.

If we do not allow one letter “O” to be drawn inside another, then we can prove that it is not possible to draw more than a countable number of letters “O”. Indeed, we can always find a special point inside each letter “O” with both coordinates being rational numbers. As circles do not overlap, no two circles can share the same special point. The set of ordered pairs of rational numbers is countable, thus this set of letters “O” has to be countable.

Now let us move to a more interesting question: how many disjoint letters “T” can you draw on a plane? Let us define the letter “T” as two perpendicular line segments, where the end point of one of the segments is the middle point of the other. Prove that the letter “T” is unstackable.

Can you analyze the whole alphabet for stackability? It doesn’t matter which alphabet — you just need to define the drawing of every letter in some reasonable manner.

My real question is, can you define the drawings of English letters in such a way that they are recognizable and the number of stackable letters is maximized? What is the biggest number of letters that you can make stackable?

I brought up this subject to my son Sergei one fine morning. As a result we came up with the following breakfast theorem: Stackable letters are topologically equivalent to a line segment or a circle.

And here is our proof. If the letter in question has a part which is topologically equivalent to “T”, then the letter is not stackable, because “T” is not stackable.

Fortunately, or unfortunately, this is not the whole story. The stackability of each letter depends on how you define its shape. There are two groups of letters in the English alphabet that you can make stackable. The first group consists of letters like “V” that can be described as a function on a segment and stacked as a parallel translation of the same letter. The second group, like letter “O”, can be described as a function of an angle in polar coordinates, and stacked as a dilation of the same letter.

It is clear that this doesn’t cover all cases. For example, a piece of a spiral can be stackable — you stack it by rotating it.

I invite my readers to define two different homeomorphic shapes for the same letter — stackable and unstackable.

I just watched the film Mackenna’s Gold for the first time. I would have liked it, if not for the sunrise. It is a treasure-hunting movie with gold lying around in a hidden canyon. The secret entrance to the canyon is revealed by the shadow of a big rock tower at the moment of sunrise.

The problem with this clue is that the azimuth of the sunrise differs depending on the day of the year. For example, at the latitude of Cairo, Tel Aviv or Los Angeles, the sunrise azimuth changes from 116 degrees to 62 degrees as the seasons change. This is more than a 40 degree span!

In any map where directions include a long shadow at sunrise, it should include the day of the year. To be more precise, the trajectory — of a given spot on Earth — around the Sun is not periodic. That means the Sun never rises at the exact same azimuth twice. If we are talking about the approximate azimuth, then the Sun rises in the same region two time periods per year. These periods are mirror reflections of each other, with the winter solstice as their focal point. That means MacKenna and his companions needed to wait for several months for the right moment.

I wonder whether the filmmakers knew about this mistake. I see two possibilities.

The first one is that no one noticed. This is very bad. It confirms that this country is illiterate. In fact, it is worse than that, since you don’t really need an education to know that sunrise and sunset happen at different points in the sky depending on the time of year. You just need to look out your window from time to time and pay attention.

The second possibility is that someone noticed, but the filmmakers decided to proceed with it anyway, on the assumption that the audience is too dumb to detect the error. Although there are Internet discussions of goofs in this movie, I was disappointed that I didn’t find any complaints about this mistake.

George Lucas borrowed many ideas for the Indiana Jones movies from Mackenna’s Gold. In particular, for Raiders of the Lost Ark he borrowed the sunrise mistake without the sunrise itself. In the movie the Sun is supposed to penetrate the crystal in the headpiece of the Staff of Ra and reveal the location of the Well of Souls. To do this, the Staff must be placed in a specific spot in the map room at a certain time of day.

The fact that the poetic idea of a sunrise was removed probably means that they knew that it was a mistake. It was replaced by a non-poetic certain time of day. But they kept the mistake. The Sun doesn’t repeat its trajectory every day. Like MacKenna, Indiana Jones would have needed to wait in the map room for several months for the Sun to be in the right spot. George Lucas opted for a fast-paced movie that disregards the laws of physics. The mystery of this movie for me is: Does anyone care?

Romanian Masters in Mathematics might become the most prestigious math competition for high school students. Romania invites teams from the 20 best countries from the previous year’s International Math Olympiad. This way they guarantee that all the competitors are extremely strong and they can give more difficult problems than the usual IMO problems.

This year they held their second competition and my son, Sergei Bernstein, was invited to join the USA team. Here is one of the problems:

For a finite set X of positive integers, define ∑(X) as the sum of arctan(1/x) for all elements x in X. Given a finite set S, such that ∑(S) < π/2, prove that there exists a finite set T such that S is a subset of T and ∑(T) = π/2.

The official solution involved a tedious greedy algorithm. My son, Sergei, got an extra point for his unique solution, which was very different from the official one. Here’s his solution:

To an integer x we associate a complex number x + i, which in polar coordinates is r(cosθ + i sinθ). Note that θ equals arctan(1/x). That means we can interpret ∑(X) as the angle in the polar form of ∏(x+i) — the product of (x+i) for all x in X.

We are given a set S with elements s_j such that ∏(s_j+i) has a positive real part, and we need to find other elements t_k, such that ∏(s_j+i) multiplied by ∏(t_k+i) has real part 0.

But we know that the ∏(s_j+i) = a + bi, for some integers a and b. I claim that we can always find a positive integer y, so that (a + bi)(y + i) has a smaller real part than a.

Note that ∑(S) < π/2, hence a and b are positive. By an ever so slightly modified version of the division algorithm we can find integers q and r such that b = aq + r, 0 < r ≤ a. Now simply set y equal to q + 1 (which is a positive integer). Then the real part of (a + bi)(y + i) equals ay – b = a – r, and is a non-negative number less than a.

Now we just repeat the process, which obviously has a finite number of steps.

My son’s solution wasn’t complete. The problem talked about sets of numbers and that implies that the numbers should be distinct. I leave it to my readers to finish this solution for distinct numbers.

This story happened in the summer of 1975. I was 16. Before that, I was naive and brainwashed; by the end of the summer I had grown up. All that summer I was stunned and didn’t know what to do as I watched this story unfold.

I was invited to the summer training camp for the International Math Olympiad. There I became friends with a fellow team member Sasha (Alexander) Reznikov. Sasha had dreamed of being a mathematician from childhood. He was gifted and brilliant and when he was in the 7th grade he got noticed by professional mathematicians. They told him that the only way to become a mathematician is to do undergraduate studies at the math department of Moscow State University. He was also told that the math department doesn’t accept Jews. Sasha was Jewish.

But there was a hole in the system. If he could get to the International Math Olympiad, he would be admitted to the place of his choice by an order of the Ministry of Education. As the IMO was conducted during entrance exams for universities, there was this special arrangement for the team members. Besides, the Soviet Math Olympiad wasn’t yet corrupted, so the Olympiads would give him a chance.

Sasha was brilliant, but he had a disadvantage — he was 2 years younger than his classmates because he had skipped grades. Since the IMO is only for high school students, he had to make it to the IMO before he graduated at 15 years old.

He worked very hard and really pushed himself, and he made it on to our team. The photo of two kids is of Sasha and me that summer.

We had a supervisor — Zoya Ivanovna — who was a Ministry liaison. She was to compile the list of team members for the Ministry of those who should be accepted without entrance exams to universities and colleges. The team had eight people, so every year the list consisted of eight students. That year was special, since we actually only had six people on our team who were high school seniors. Two of us, Sergey Finashin and I, were not yet seniors. But Zoya Ivanovna who was a good-hearted lady decided to sneak in eight people and added our two alternates to the list. As our alternates were preparing for the IMO instead of preparing for entrance exams, this was a generous and fair thing to do. Everything was fine and everyone was happy.

Until one day when strange things started to happen. We were invited for a meeting where Zoya Ivanovna told us that there was a problem with Moscow State University. We were told that the math department has a limit of four people who can be accepted without an entrance exam, and we had five students applying. Zoya Ivanovna asked if there was a volunteer who might reconsider. At this point Alexey Muzykantov said that he would volunteer since he was an alternate. Besides, he was always as interested in physics as in math, and would be happy to study in the physics department.

After the meeting I stumbled upon Zoya Ivanovna crying in the ladies room. She told me that she didn’t know what to do. The problem was that out of five people applying for the math department of Moscow State University, three were Jews. Three Jews were too many out of the 400 people annually accepted to the department. Our team coordinator, Valentin Anatolievich Skvortsov, was working at the math department, where he was being pressured. Zoya Ivanovna told me he had been threatened with expulsion from the Communist Party if he didn’t reduce the number of Jews by at least one. Being expelled from the Communist Party was a serious threat at that time and Zoya Ivanovna was eager to help, so she invented this idea about the limit. The idea didn’t work, because Alexey Muzykantov, who removed himself from the list, wasn’t Jewish.

After several days, Sasha Reznikov’s mother appeared at the summer program. She told me that she was being pushed to persuade Sasha not to go to Moscow State University.

I asked Zoya Ivanovna why she chose Sasha. She told me that out of the three Jews, one was from Moscow, so she didn’t consider him, and Sasha was much younger than the third student and, besides, he had health problems. So she tried to convince Sasha’s mother that Sasha would be better off in his home town Kiev than in Moscow.

Sasha went to Kiev University. The system had had a hole through which two Jews passed that year, so even though Sasha had made astonishing efforts, he hit a wall. He was crushed.

Later he tried to transfer to Moscow State University, but was ridiculed, humiliated and denied. Eventually Sasha moved to Israel and got his PhD in mathematics. He died in 2003 by, according to rumors, suicide.

This piece of graph theory was inspired by a logic puzzle The Sexaholics of Truthteller Planet at the 2009 MIT mystery hunt.

Suppose we have a graph where nodes are people and edges connect two people who ever had sex with each other. Given this graph, I am wondering what we can derive about the gender and sexual orientation of the people involved. To do this I need to make some assumptions.

As these are people from another planet, Truthteller, I can choose any assumptions I please, so let us assume that people are of two genders and two types of sexual orientation. The first type of sexual orientation is strictly straight — people of this type only have sex with strictly straight people of the opposite gender. The second type of sexual orientation is strictly homosexual — people of this type only have sex with strictly homosexual people of the same gender. Whoops! I almost forgot: as I assume simplicity, no threesomes happen on that planet.

My question is: Looking at the sex graph can we say anything about sexual orientation? Given any graph, all the vertices can represent homosexual people of the same gender. Is it possible to say, on the other hand, that a vertex of this graph can correspond to a straight person? Let us consider a connected graph representing sex between strictly straight people. This graph has to be bipartite. Hence, given a graph, the maximum number of vertices that correspond to straight people is the total number of vertices in all bipartite connected components.

Similarly, all vertices in a non-bipartite component of a graph are guaranteed to correspond to homosexuals.

Here I would like to name these graphs. If a graph doesn’t have a bipartite connected component I will call this graph an all-homosexual graph. The sequence for which the n-th term is the number of all-homosexual graphs with n vertices for n > 0 starts as 0, 0, 1, 3, 16, 96, 812… and is sequence A157016 in the Online Encyclopedia of Integer Sequences. The smallest all-homosexual graph is a complete graph with 3 vertices.

I would like to name not all-homosexual graphs as someone-can-be-straight graphs. The corresponding sequence is A157015.

Thank you to the people who helped me to calculate and clean these two sequences. I received more help with these two sequences than all the sequences I’ve tried to submit to the Encyclopedia. And it is definitely not because they are about sex, because I purposefully didn’t tell them that I was going to relate these sequences to sex. Thanks to Max Alekseyev, Edwin Clark, Brendan McKay and Wouter Meeussen.

You are visiting your girlfriend and she orders pizza. Your evil girlfriend has perfect eyesight and notices fly droppings in three places on the pizza. She is seeking revenge on you for refusing to babysit her poodle and proceeds to cut the pizza. Assuming that the droppings occurred independently and in random places, what is the probability that she will be able to cut a half-circle pizza slice with all three droppings in one half?

Now that I’ve ruined your appetite, here’s a simpler puzzle you can solve as an appetizer to the one I just gave you above. In this puzzle, you have a bread stick that is, of course, in the shape of a line segment. Your girlfriend notices that the bread stick also has three fly droppings on it and she offers to cut an exact half length out of the middle for you. What is the probability that she can cut it so that you end up with all the droppings?

Can you bear to continue this tasty discussion? If so, I’ll give you an even simpler problem. Try to solve both of the above puzzles — but with only two droppings instead of three.

If I’ve spoiled your appetite so completely that you’ll skip dinner, why not use the extra time to solve the most challenging of these problems with a meatball that has four fly droppings on it. These droppings, too, are in random places and you must calculate the probability that you are able to cut a semi-sphere with all four droppings on one side.

This final puzzle — in a less distasteful setting — was sent to me by Nick Petry.