Tanya Khovanova's Math Blog

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.

I have an old book which I value a great deal. The book is called 200 Problems in Linguistics and Mathematics and only 1,550 copies were printed in 1972. Luckily, a new extended edition just appeared on the web. Both editions are in Russian, so I decided to translate some of the problems into English. Here is a sample:

Problem 1. Here are phrases in Swahili with their English translations:

• atakupenda — He will love you.
• nitawapiga — I will beat them.
• atatupenda — He will love us.
• anakupiga — He beats you.
• nitampenda — I will love him.
• unawasumbua — You annoy them.

Translate the following into Swahili:

• You will love them.
• I annoy him.

Problem 2. You are given words in Swahili: mtu, mbuzi, jito, mgeni, jitu and kibuzi. Their translations in a different order are: giant, little goat, guest, goat, person and large river. Make the correspondence.

Problem 3. In Russian the middle name is the patronymic. Thus, the middle initial is the first letter of the father’s first name. And, as in many languages, the first initial is the first letter of the first name. Here are names of males in a family:

• A.N. Petrov
• B.M. Petrov
• G.K. Petrov
• K.M. Petrov
• K.T. Petrov
• M.M. Petrov
• M.N. Petrov
• N.M. Petrov
• N.K. Petrov
• N.T. Petrov
• T.M. Petrov

Draw the family tree of the Petrovs, given that every father has two sons, the patriarch of the family has four grandsons, and his sons have two grandsons each. Prove that the solution is unique.

Problem 4. In Latvian a noun can be one of two genders; furthermore, adjectives agree with nouns in gender, number and case. You are given phrases in either the nominative or the genitive case with their translations:

• silts ezers — warm lake
• melns lauva — black lion
• liela krāsns — big oven
• lielas jūras — big sea’s
• sarkana ezera — red lake’s
• melna kafija — black coffee
• sarkans putns — red bird
• liela kalna — big mountain’s
• sarkanas lapas — red leaf’s
• sarkana pils — red castle
• liels ezers — big lake
• melna putna — black bird’s
• liela lauvas — big lion’s
• silta jūra — warm sea
• melnas kafijas — black coffee’s
• liels kalns — big mountain

Indicate which words are nouns and which are adjectives. Divide Latvian nouns into two groups, so that each group contains words of the same gender.

Problem 5. The Portuguese language takes its roots from Latin. In this problem modern Portuguese words are written on the left and their roots (in Latin and other languages on the right). All the words on the left belong to one of three classes: ancient borrowing, early borrowing and late borrowing.

• chegar — plicare
• praino — plaine
• plátano — platanum
• chão — planum
• plebe — plebem
• cheio — plenum
• prancha — planche

For every Portuguese word, indicate which class it belongs to. (Note that in Portuguese “ch” is pronounced as “sh”.)

I bought the book “Math Doesn’t Suck: How to Survive Middle School Math Without Losing Your Mind or Breaking a Nail“ by Danica McKellar because I couldn’t resist the title. Sometimes this book reads like a fashion magazine for girls: celebrities, shopping, diet, love, shoes, boyfriends. At the same time it covers elementary math: fractions, percents and word problems.

You can apply math to anything in life. Certainly you can apply it to fashion and shoes. I liked the parallel between shoes and fractions that Danica used. She compared improper fractions to tennis shoes and mixed numbers to high heels. It is much easier to work with improper fractions, but mixed numbers are far more presentable.

Danica is trying to break the stereotype that girls are not good at math by feeding all the other stereotypes about girls. If you are a typical American girl who hates math and missed some math basics, this book is for you. If you want to discover whether the stars are on your side when you are learning math, the book even includes a math horoscope.

I am celebrating the first hundred essays I have written for my blog. My English teacher and editor Sue Katz edited most of them. Sue Katz not only corrects my English mistakes, but also helps me to choose better and more descriptive words and rearranges my text so that it doesn’t sound like a direct translation from Russian.

If you’re looking for an editor, she’s superb.

Sue is an extremely interesting person. She was one of the first women to gain a black belt in Tae Kwon Do and taught martial arts and dance on three continents. Now she concentrates on her blog and writing. In her blog Sue Katz: Consenting Adult she writes a lot about sex and also about current affairs. She reviews books and movies and expresses her interesting and unique perspective on things. Some of my favorite posts:

• Philosophical and romantic — Six-Word Memoirs: Sought revolution, got pantsuits, want more
• Down-to-earth and funny — The Drip Dominatrix rules her bladder
• Bitter and sweet — Film Review: The Diving Bell and the Butterfly

I am not only grateful to Sue for the excellent professional job, but also for encouraging me. She laughs at my jokes and is a devoted fan of my blog. Thank you, Sue!

I love “Knights and Knaves” logic puzzles. These are puzzles where knights always tell the truth and knaves always lie. A beautiful variation of such a puzzle with Gnyttes and Mnaivvs was given at the 2009 MIT mystery hunt. In this puzzle people’s ability to tell the truth changes during the night depending on the sex partner. You will enjoy figuring out who is a Gnytte or a Mnaivv for each day, who is infected and who slept with whom on each night. Just remember that the ultimate answer to the puzzle is a word or a phrase. So there is one more step after you solve the entire logic part. You do not really need to do this last step, but you might as well. Here we go:

The Sexaholics of Truthteller Planet

Each inhabitant of Veritas 7, better known as the Truthteller Planet, manifests one of two mutations: Gnytte or Mnaivv. Gnyttes always tell the truth, and Mnaivvs always lie. Once born a Gnytte or Mnaivv, the inhabitant can never change…until now.

Veritas 7 is in the midst of an outbreak of a nasty virus dubbed Nallyums Complex II. If an infected inhabitant has sex with another inhabitant of that planet, each one can be converted from Gnytte to Mnaivv, or Mnaivv to Gnytte, as shown below:

• If the sex is heteroverific (1 Gnytte and 1 Mnaivv), both become Mnaivvs.
• If the sex is homoverific (2 Gnyttes or 2 Mnaivvs), both become Gnyttes.

This occurs if either party or both parties have the disease. The disease itself is not transmitted via sex, which is some relief.

Several members of a Veritas 7 village have just contracted Nallyums Complex II. Below are statements from the 15 village residents, taken over the 5-day period since the outbreak. Interviews were taken each morning, and sex occured only at night. Each night, residents paired off to form seven separate copulating couples, with one individual left out. No individual was left out for more than one night.

Can you identify the infected individuals and track their pattern of sexual activity?

A note on wording: If someone refers to sex with someone who was a Gnytte or Mnaivv, they are referring to the individual’s truth-telling status just before sex. If a clue says that two individuals had sex, it means they had sex with each other. “Mutation” refers to the individual’s current status as Gnytte or Mnaivv.

Interviews Day 1

• Artoo: Etrusco is not infected.
• Bendox: Cravulon and Flav are not the same mutation today.
• Cravulon: Either Artoo or Flav is a Gnytte today.
• Dent: Jax-7 and I are both Mnaivvs today.
• Etrusco: Greasemaster is a Mnaivv today.
• Flav: There are at least five Mnaivvs today.
• Greasemaster: Murgatroid is a Gnytte today.
• Holyoid: Etrusco is either an infected Mnaivv or an uninfected Gnytte today.
• Irono: Etrusco is a Mnaivv today.
• Jax-7: Among Artoo, Greasemaster, and Nebulose, exactly one is a Gnytte today.
• Killbot: Bendox is a Gnytte today.
• Lexx: Holyoid and Irono are not the same mutation today.
• Murgatroid: There are at least eight Gnyttes today.
• Nebulose: Murgatroid is a Mnaivv today.
• Oliver: Lexx is a Gnytte today.

Surveillance Night 1

Security cameras revealed that Jax-7 did not have sex with anyone last night, and that Nebulose and Murgatroid had sex.

Interviews Day 2

• Artoo: Last night, I did not have sex with an infected individual.
• Bendox: Last night, Oliver had sex with someone who was a Mnaivv.
• Cravulon: There are at least six Gnyttes today.
• Dent: If there are only five Gnyttes today, then Cravulon and Oliver had sex last night.
• Etrusco: Last night, Bendox had sex with someone who was a Mnaivv.
• Flav: Neither Killbot nor her partner last night is infected.
• Greasemaster: Last night, either Cravulon and Bendox had sex, or Oliver and Etrusco had sex, but not both.
• Holyoid: Last night, I had sex with someone who was a Gnytte.
• Irono: Last night, I did not have sex with Flav.
• Jax-7: Last night, Artoo had sex with Dent.
• Killbot: Last night, I had sex with someone who was a Mnaivv.
• Lexx: Cravulon is infected.
• Murgatroid: Nebulose is not infected.
• Nebulose: Last night, either Cravulon or Flav had sex with Etrusco.
• Oliver: Last night, Irono had sex with someone who was a Mnaivv.

Surveillance Night 2

Security cameras revealed that Holyoid did not have sex with anyone last night, and that Irono and Oliver had sex.

Interviews Day 3

• Artoo: Last night, I had sex with the individual who had sex with Murgatroid on Night 1.
• Bendox: Last night, I had sex with an uninfected individual.
• Cravulon: Last night, Jax-7 had sex with the individual who had sex with Lexx on Night 1.
• Dent: Last night, I had sex with someone who was a Mnaivv.
• Flav: Last night, I had sex with an uninfected individual.
• Holyoid: Neither Oliver nor Irono is infected.
• Irono: Last night, the individual who had sex with Oliver on Night 1 had sex with someone who was a Mnaivv.
• Jax-7: There are more than seven Gnyttes today.
• Killbot: Bendox and Murgatroid are the same mutation today.
• Lexx: Last night, the individual who had sex with Flav on Night 1 had sex with an infected individual.
• Nebulose: The individual who had sex with Etrusco on Night 1 is a Mnaivv today.
• Oliver: Last night, Lexx had sex with the individual who had sex with Bendox on Night 1.

Surveillance Night 3

Security cameras revealed that Dent and Jax-7 had sex.

Interviews Day 4

• Artoo: There are at most seven Gnyttes today.
• Cravulon: Last night, I had sex with someone who has never been a Gnytte.
• Dent: The two sex partners of an individual who was a Mnaivv on the first three days had sex last night.
• Etrusco: Last night, Oliver did not have sex.
• Flav: Last night, I had sex with an infected individual.
• Greasemaster: There are exactly eight infected individuals.
• Killbot: None of the individuals who have been left out of the sexual activity is infected.
• Murgatroid: Last night, I had sex with someone who was a Gnytte on Day 1.
• Nebulose: Last night, I had sex with someone who has had sex with Artoo.
• Oliver: Last night, an individual who had sex with Holyoid during one of the first two nights had sex with an individual who had sex with Jax-7 during one of the first two nights.

Surveillance Night 4

Security cameras have been vandalized.

Interviews Day 5

• Artoo: Last night, I had sex with a Mnaivv, but not the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with the individual who, on Night 1, had sex with Dent.
• Bendox: Last night, Dent had sex with the individual who, on Night 1, had sex with the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with Artoo.
• Cravulon: Last night, Holyoid had sex with the individual who, on Night 3, had sex with the individual who, on Night 2, had sex with the individual who, on Night 1, had sex with Murgatroid.
• Dent: Jax-7 is a Gnytte today.
• Flav: Last night, Cravulon did not have sex with the individual who, on Night 1, had sex with the individual who, on Night 2, had sex with the individual who, on Night 3, had sex with Cravulon.
• Jax-7: Last night, Greasemaster did not have sex.
• Nebulose: Last night, Killbot either had sex with an uninfected individual or did not have sex.

I do not remember where I dug this logic puzzle out from:

Folks living in Trueton always tell the truth. Those who live in Lieberg, always lie. People living in Alterborough alternate strictly between truth and lie. One night 911 got a call: “Fire, help!” The operator couldn’t identify the phone number, so he asked, “Where are you calling from?” The reply was Lieberg.
Assuming no one had overnight guests from another town, where should the firemen go?

After you have solved this problem, you will see that the sentence “Fire, help!” is true. I wonder, if this statement were a lie, how would we interpret it? It could be that it is just a joke and there is no fire and therefore no need for the police. Or it could be that help is needed — perhaps for a robbery, but not for a fire.

However, when you solve this puzzle, you’ll find out that the “Fire, help!” statement is true, so you do not need to wonder what it would mean if the statement were a lie. But I wondered, and as a result I invented several new puzzles.

Here is the first one:

Let’s say that people will call the police only if something is happening and there are only two things that could be happening: fire or robbery. Suppose that when people calling the police need to lie, they replace fire with robbery, and vice versa. Suppose also that when asked about location, people will not say, &quotI am not from Lieberg,” as they could have, but will always reply with one word, which is a name of one of three towns. So, there are two possibilities for the first statement — Fire, Help! or Robbery, Help! — and three possible answers to the question about location. — Trueton, Lieberg and Alterborough. My puzzle in this case is: What answer to the location question will give the biggest headache to the police?

We can branch the original puzzle out in a different way. Here is my second puzzle:

We can assume that only fire, not robbery, could happen in this remote place and when people call the police they either say “Fire, help!” or “We do not have a fire, thank you for your time.” Let us again assume that people will call the police only if something is happening. In this case, what combinations of first and second sentences of the callers will never happen?

My third puzzle is a more complicated version of the second puzzle:

Let’s assume that fires happen with the same probability in every town and that the cost of sending a team of firefighters is identical for every town. Furthermore, the ferocity of all the fires is minuscule and the cost of sending a team is the same, whether or not it turns out that there is a fire. If the police think that the call could have come from several places, they send several teams and the cost multiplies accordingly. The police are obsessed with making charts and the most important number they analyze is the cost they incur, depending on the content of the first sentence of each call.
Given that there are frequent fires, what could the ratio of the cost to police for the calls “Fire, help!” be compared to those that begin with “We do not have a fire, thank you for your time”?

I wanted to see how different presidents affected the Dow Jones index. The index was invented at the end of the nineteenth century, so for my convenience, I will start my analysis from the beginning of the twentieth century. I skipped the presidents who were in office for only four years — four years might not be enough to rebuild a bad economy or to destroy a good one. Besides, in order to give the presidents a fair chance, I compared them for the same time period: eight years.

So I removed from my consideration all those who only served for four years: William Howard Taft, Herbert Hoover, Jimmy Carter and George H.W. Bush. I also combined two presidents together, when one succeeded the other mid-term for a total of eight years. Namely, I combined Warren Harding with Calvin Coolidge, John Kennedy with Lyndon Johnson, and Richard Nixon with Gerald Ford. For Franklin Roosevelt, I only considered the first eight years of his presidency.

Please note that it was not always precisely eight years — the inauguration date was sometimes moved. So Theodore Roosevelt and Harry Truman had slightly less than eight years. I tried to use the Dow Jones index from the exact day of each inauguration, but not all the dates were available in the file I used. So sometimes I had to pick the previous day.

Some might argue that I need to scale the Dow Jones Index. For example, the inflation rate was very different for different presidents. It is generally accepted that the value of one point in the Dow Jones Index decreases with time, but inflation is only one of many elements contributing to that change. Nonetheless, I took a look at that and the resulting picture didn’t change much anyway when I adjusted for inflation.

The Dow Jones is just one number. An increase in the Dow Jones does not completely describe the state of the economy, but it is certainly an interesting measure in its own right.

Let’s look at how the presidents and the presidential teams performed, sorting them from best to worst:

When I started this calculation I expected Clinton to be doing well and Bush badly, I just didn’t know exactly how good/bad they were. But the most interesting result of this exercise is the fact that the highest increase in DJI happened right before the Great Depression.

What can I say? I should have done this analysis eight years ago. Maybe the proximity of Clinton’s performance to the pre-depression boom could have urged me to move my 401(k) from stocks. Sigh.