Tanya Khovanova's Math Blog

I have a leased Toyota Corolla, and I am happily enrolled in AutoCheck payments with Toyota’s Financial Services. So I do not even look at my bills. Once I opened my bill and noticed that the requested payment was twice as high as I expected. I looked closer and the bill had a car tax included in it. I looked even closer and read that:

Your Current Payment Due will be automatically withdrawn from your checking or savings account on the above Payment Due Date or the next banking day.

I decided that everything was taken care of and continued my relaxed life. After several months I checked my bill again, and the car tax was still there. After more careful study of my bill I discovered that Toyota’s “Current Payment Due” doesn’t include my car tax. Obviously they assume that their definition of “Current Payment Due” is crystal clear to everyone.

I got worried about this delayed car tax payment and went online to pay it. I tried to make this payment, but Toyota’s website rejected it. The website informed me that because I am enrolled in AutoCheck, I am not allowed to make separate online payments. I couldn’t believe it: to do so, I would have to de-enroll first!

So I just wrote a check.

In one day my feelings for my Toyota Corolla were turned around. If their financial system is designed so stupidly, what can we say about their car designs? Suddenly the sound of my brakes and the squeak in my steering wheel worry me.

A year ago I posted a chessboard puzzle. Recently I stumbled on a September 2008 issue of “Math Horizons” where it was presented as a magic trick.

When the magician leaves the room, the trickees lay out eight coins in a row deciding which side is turned up according to their whim. They also think of a number between 1 and 8 inclusive. The magician’s assistant then flips exactly one of the coins, before inviting the magician back in. The magician looks at the coins and guesses the number that the trickees thought of.

The magician’s strategy can be derived from the solution to the chessboard puzzle. The assistant numbers the coins from zero to seven from left to right. Then s/he flips the coin so that the parity addition (XORing) of all the numbers corresponding to heads is the number that the magician needs to guess. For this trick to work, the number of coins needs to be a power of 2.

Andrey Zelevinsky posted (in Russian) a cool variation of this trick with two decks of cards.

The magician has two identical card decks and he is out of the room for now. A random person from the audience thinks of a card. Next, the audience chooses several cards from the first deck. Then the assistant adds one card from the second deck to the set of chosen cards, lays them on a table, and then invites the magician back. The magician looks at the cards on the table and guesses the card that was thought of.

Unlike in the coin trick above, the number of cards in the deck doesn’t need to be a power of 2. This flexibility is due to the fact that the magician has two decks of cards, as opposed to one set of coins. Having the second deck is equivalent to the assistant in the coin trick being allowed to flip one or ZERO coins.

Nikolay Konstantinov, the creator and the organizer of the Tournament of the Towns, discussed some of his favorite tournament problems in a recent Russian interview. He mentioned two beautiful geometry problems by Sergey Markelov that I particularly loved. The first one is from the 2003 tournament.

An ant is sitting on the corner of a brick. A brick means a solid rectangular parallelepiped. The ant has a math degree and knows the shortest way to crawl to any point on the surface of the brick. Is it true that the farthest point from the ant is the opposite corner?

The other one is from 1995.

There are six pine trees on the shore of a circular lake. A treasure is submerged on the bottom of the lake. The directions to the treasure say that you need to divide the pine trees into two groups of three. Each group forms a triangle, and the treasure is at the midpoint between the two triangles’ orthocenters. Unfortunately, the directions do not explain how exactly to divide the trees into the groups. How many times do you need to dive in order to guarantee finding the treasure?

Tanya Khovanova, Alexey Radul

Perfidy is to parity as odious is to odd and evil is to even. As a reminder, odious numbers are numbers with an odd number of ones in their binary expansions. From here you can extrapolate what the evil numbers are and the fact that the perfidy of an integer is the parity of the number of ones in its binary expansion. We live in a terrible world: all numbers are perfidious.

So why are we writing about the perfidy of negative numbers? One would expect it to be a natural extension of the perfidy of positive numbers, but it turns out that the naive way of defining it doesn’t work at all. Is there hope? Could negative numbers be innocent of evil and free of odiousness? Is zero an impenetrable bulwark against perfidy? Not quite, but something interesting does happen to evil as it tries to cross zero. Read on.

To define perfidy for negative numbers, let us study how perfidy behaves for positive numbers. It is easiest to think about the perfidies of power-of-two-sized chunks of non-negative integers at a time. Let us denote by T_n the string of perfidies of the integers from 0 to 2ⁿ−1, with evil being zero and odious being 1. So T₀ = 0, T₁ = 01, T₂ = 0110, T₃ = 01101001, …. The recurrence relation governing the T_n is T_n+1 = T_nT_n, where T is the bitwise negation of the string T, and juxtaposition is concatenation. The limit of this as n tends to infinity is the (infinite) sequence of perfidies of non-negative integers. This sequence is called the Thue-Morse sequence: 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,….

So defining the perfidy of negative numbers is equivalent to extending the Thue-Morse sequence to the left. If we are to define “the” perfidy of negative numbers, that definition should preserve most of the properties of the Thue-Morse sequence after extension.

So, let’s see. We asked around, and most people said that the binary expansion of a negative integer should be the binary expansion of its absolute value, but with a minus sign. Defining perfidy as parity of number of ones in this binary expansion corresponds to the following extended Thue-Morse sequence in which we mark values corresponding to negative indices with bold font: … 0, 1, 1, 0, 1, 1, 0, ….

One of the major properties of the Thue-Morse sequence is its fractal property: if you replace every zero of the Thue-Morse sequence by 0,1 and every one by 1,0, you will get the Thue-Morse sequence back. Clearly, our new extended sequence doesn’t have this property.

Another set of properties for the Thue-Morse sequence, called avoidance properties, is a long list of patterns that the sequence avoids. For example, the Thue-Morse sequence doesn’t contain any overlapping squares — patterns axaxa, where a is a character and x is a word. But you can see above, our first extension contains it. So this definition is wrong, not just once but twice (and two wrongs only make a right under very unusual circumstances). Perfidy is stymied by the cross-over from zero to minus one. Are negative numbers protected from the ravages of evil? (and odiousness?)

Unfortunately, there are many people, for example John Conway, who inadvertently extend the reach of perfidy by arguing that the binary expansion of a negative integer should be different. Indulge in a flight of fancy and imagine the binary expansion that consists of infinitely many ones to the left: …1111. What happens when you add 1 to it? The carry gets pushed infinitely far away, and you get …000000 — zero. So it is quite reasonable to let …1111 be the binary expansion of −1. Similarly, the string …1110 represents −2, …1101 represents −3, etc. Continuing this we see that the binary expansion of a negative integer −n is the bitwise negation of the binary expansion of n − 1 (including the leading zeros). This is called the Two’s complement representation.

Why is two’s complement a reasonable representation? Suppose you were trying to invent a binary notation for negative numbers, but you wanted to pursue uniformity by not using a minus sign. The problem is that the standard definition of the binary representation allows you to represent only positive numbers. But you can solve this problem with modular arithmetic: modulo any fixed N, every negative number is equivalent to some positive number (by adding enough multiples of N), so you can just represent it by representing that positive number. If you choose N to be a power of two, modding out by it is just truncation of the binary representation. If you let those powers of two tend to infinity, you get the two’s complement representation described above.

Aside: When you are building a computer, uniformity is money, because special cases cost special transistors. The two’s complement idea lets one build arithmetic units that just operate on positive numbers with some number of bits (effectively doing arithmetic modulo 2^k), and leave the question of negativeness to the choice of representatives of those equivalence classes.

If we take two’s complement as the binary expansion of negative numbers, how will we define the perfidy? Is the number of ones in the infinite string …1111 corresponding to −1 even or odd?

We can’t answer that question, but we know for every binary expansion of negative numbers the parity of the number of zeroes. Thus we can divide all negative integers in two classes with different perfidy. We just do not know which one is which.

Let us consider two cases. In the first case we consider a negative number odious if the number of zeroes in its binary expansion is odd. The corresponding extended Thue-Morse sequence is: … 0, 1, 1, 0, 0, 1, 1, 0, …. The negative half is the reflection of the classical Thue-Morse sequence. In the second case we consider a negative number odious if the number of zeroes in its binary expansion is even. The corresponding extended Thue-Morse sequence is: … 1, 0, 0, 1, 0, 1, 1, 0, …. The negative half is the bitwise negation of the reflection of the classical Thue-Morse sequence.

Can we say that one of the sequences is better than the other? Both of them respect the fractal property of the classical Thue-Morse sequence. Let us look at the avoidance properties. The avoidance properties are symmetric with respect to switching zeroes with ones and with respect to changing the direction of the sequence. Hence, the negation, the reflection, and the reflection of the negation of the Thue-Morse sequence will continue to respect these properties.

Thus, we only need to check the avoidance properties of the finite subsequences that span both negative and non-negative indices. We claim that for both definitions of perfidy, any finite middle subsequence of the extended Thue-Morse sequence occurs as a subsequence in the classical Thue-Morse sequence. So any avoidance properties that are true for the Thue-Morse sequence will also be true for both extensions.

Indeed, it is easy to show that the strings T_2n defined above are palindromes. So for the first definition of perfidy the string in the middle will be a substring of T_2nT_2n for some large n, and for the second definition a substring of T_2nT_2n. But the classical Thue-Morse sequence contains the subsequence T_2nT_2nT_2nT_2nT_2nT_2nT_2nT_2n. So whichever way we extend the Thue-Morse sequence to the left any finite middle part will always be a repetition of a piece in the classical Thue-Morse sequence. Thus, all the avoidance properties will hold.

We see that there are two logical ways to define perfidy for negative integers. There are two clear groups of numbers with the same perfidy, but which is called evil and which odious is interchangeable. So evil doesn’t stop at zero after all, but at least it gets an identity crisis.

* * *

A note posted on the door of the tech-support department:

“Theory — you know everything, but nothing works. Practice — everything works, but nobody knows why. In our department we merge theory with practice: nothing works and nobody knows why.

* * *

A plus is two minuses at each others’ throats.

I was teaching my students PIE, the Principle of Inclusion and Exclusion. This was the last lesson of 2010 and it seemed natural to have a party and bring some pie. It appears that the school has a new rule. If I want to bring any food to class, I need to submit a request that includes all food ingredients. The administrators send it to the parents asking them to sign a permission slip and then, if I receive all the slips back in time, I can bring pie to school. We had to study PIE without pie.

Our most important task as parents and teachers is to teach kids to make their own decisions. They are in high school; they know by now about their own allergies and diets; they should be able to avoid foods that might do them harm. I understand why schools create such rules, but we are treating the students like small children. We can’t protect them forever; they need to learn to protect themselves.

Next semester, we will study the mathematics of fair division. I will have to teach them how to cut a cake without a cake.

I once wrote a story about a mistake that my medical insurance CIGNA made. They had a typo in the year of the end date of my insurance coverage in their system. As a result of this error, they mistakenly thought they had paid my doctors after my insurance had expired and tried to get their money back. While I was trying to correct all this mess, an interesting thing happened.

To help me explain, check out the following portion of my bill. (If it looks a bit funny, it’s because I cut out some details including the doctor’s name).

On the bill you can see that I had a mammography for which I was charged $493.00, but CIGNA paid only $295.80. The remaining $197.20 was removed from the bill as an adjustment, as frequently happens because of certain agreements between doctors and insurance companies. A year later when CIGNA made their mistake, they requested that the payment be returned. You can see on the bill that once the payment was reversed, my doctors reversed the adjustment too.

When CIGNA fixed the typo, they repaid the doctors, but the adjustment stayed on the bill, which the doctors then wanted me to pay. And that was only one of many such bills. It took me a year of phone calls to get the adjustments taken off, but this is not what I am writing about today.

If not for this mistake, I would have never seen these bills and the revealing information on the different amounts doctors charge to different parties, and how much they really expect to receive. As you can see my doctors wanted 67% more for my mammogram than they later agreed to.

The difference in numbers for my blood test was even more impressive. I was charged $173.00, and the insurance company paid $30.28 — almost six times less.

If I ever need a doctor and I don’t have insurance, I will take these bills with me to support my request for a discount. I do not mind if you use this article for the same purpose.

I met Ed (Edik) Frenkel 20 years ago at Harvard when he was a brilliant math student of my now ex-husband, and a handsome young man. Now, at 42, he is a math professor at Berkeley and he is even hotter. He made a bizarre move for a mathematician: he produced and starred in an erotic short movie, Rites of Love and Math. If he wants to be known as the sexiest male mathematician alive, he just might get the title.

The movie created a controversy when Mathematical Sciences Research Institute (MSRI) withdrew its sponsorship for the first screening after a lot of objections based on the trailer. My interest was piqued by a painting that dominated the visual of the trailer’s erotica scene. The black and white amateur painting is of the integral sign with Russian letters stylized as math symbols that spell the word “Truth”. In addition, the name of the woman in the movie, Mariko, means “truth” in Japanese. Though it felt pretentious, I was hoping that the movie would be symbolic. When I heard that the actors do not talk in the movie, my expectations of symbolism grew. I love movies that are open to interpretation. So I bought the movie, watched it and wrote the following review. Before getting to the review itself I would like to thank Ed Frenkel for sending me the photos and giving me permission to use them in my frank assessment of his work.

Here is the plot:

A Mathematician, hoping to serve humanity, discovers a formula of Love. Bad guys find an evil way to use the formula to destroy humanity and are hunting for the Mathematician, who is hiding in his lover Mariko’s home. The Mathematician fears for his own life. Although it would make sense to destroy all the papers with the formula, the Mathematician loves his formula even more than his lover and himself. He wants to preserve the formula and tattoos it on her body with her consent.

There is much about the film that I like, including the slow pace and the visuals, with their minimalistic background and palette of black, white and red. The camera work is superb.

I welcomed the idea of a Love formula, because mathematics is ready to broaden the scope of its models, including venturing into love. Of course, some mathematical models of relationships already exist.

It’s great that the mathematician is portrayed against the stereotype: he’s neither introverted nor asexual. Unfortunately, the movie plays into other stereotypes of male mathematicians — being creepy and demanding sacrifices from their wives in the name of mathematics. As I mentioned, I was looking forward to the movie, hoping that it would encourage the imagination of viewers in their interpretations. To my disappointment, every scene in the movie is preceded by text that describes the plot, removing any flexibility of interpretation. Besides that, the emotions portrayed didn’t quite match the written plot, in no small part because Ed Frenkel is not a good actor.

The idea of preserving a formula by tattooing it on someone is beyond strange. He could have used a safe-deposit box. Or put the formula in an envelope and given it to the lover to keep, or just encrypted it, etc. With narcissistic lack of consciousness, the Mathematician seems unaware of the implications of his action of imprinting this dangerous secret on Mariko. She can never go swimming, or go to the gym, or be intimate with anyone else. Moreover, if the bad guys discover that Mariko is the Mathematician’s lover, her life will be in grave danger. Not to mention that tattooing is painful.

Something that could have been interesting and watchable in a historic movie, in this contemporary movie seems pointlessly cruel, dehumanizing and senseless.

I know for sure that Ed Frenkel is not stupid, so what are his reasons for constructing the plot in this way? Before investigating his reasons, I have a mathematical complaint about the movie. Every mathematician and teacher knows that when asserting a formula you need to indicate its interpretation: what its symbols refer to in the real world. For example, suppose I tell you my own great Formula of Love: C_n = (2n)!/(n+1)!n!. You may recognize C_n as the Catalan numbers, but what does this have to do with Love? To give the formula meaning I need to tell you that C_n is the number of ways you can seat n loving couples at a round table with 2n chairs, so that each couple can join hands (assuming the arms are long enough to reach across the table) without any two pairs of arms crossing. Assigning an interpretation makes the Catalan numbers part of the world’s growing body of romantic research.

Writing a formula without mentioning what the variables mean fails to preserve it for the future. Ed Frenkel knows that. Wait a minute. The formula in the movie is actually not the Formula of Love, but a real formula from Ed’s paper on instantons. It’s right there, formula 5.7 on page 74. Every variable is explained in the paper. Ah-ha! So his movie isn’t actually about art, but rather about Ed’s formula. Indeed, there is no real Formula of Love. In such situations in other movies, they have simply shown fragments of a formula. However, in Rites of Love and Math, Frenkel’s formula — which has nothing to do with Love — is shot in full view, zooming in slowly.

The movie is a commercial. Ed is using our fascination with sex to popularize his formula, and using his formula and his scientific standing to advertise his body.

I was so disappointed that the default interpretation of the movie was imposed on me by those pre-scene texts, that I decided to watch the movie for a second time, trying to ignore the text, hoping to find some new meaning.

If you decide to see the movie, you’ll probably come up with your own interpretation of the plot. I actually came up with several. I had a funny one and an allegorical one, but the most interesting task for me was to try create an interpretation matching the emotions portrayed:

Mariko knows that something is wrong in her sex life with the Mathematician. But she still loves him and writes him a love letter. The Mathematician comes to Mariko’s place. He is distant and cold. They cuddle. He explains to her that sex doesn’t bring him pleasure anymore and that moreover, he can’t even perform. He tells her that the only thing that brings him joy is mathematics and suggests that his sexual dysfunction and lack of pleasure will be fixed if they tattoo his favorite formula on her body. She agrees, but first they decide to give sex a last try. They try real hard. But he can’t relax and he doesn’t enjoy it, so she agrees to the tattoo. He does get excited during the tattooing process itself, but once he finishes his whole formula, he is no longer turned on. Mariko’s suffering has been in vain.

Janet Mertz wrote several papers about the gender gap in mathematics. One of her research ideas was to find girls who went to the International Math Olympiad (IMO) and compare their fate to that of their teammates with a similar score. She asked me to find Soviet and Russian IMO girls. All my life I had heard about Lida Goncharova, the first girl on a Soviet team, and the first girl in the world who took a gold medal, but I had never dared to reach out to her. A little push by Janet Mertz was enough for me to find Lida’s phone number in Moscow and call her.

My conversation with Lida Goncharova

Lida got interested in mathematics when she was five years old. Luckily, many of her relatives were mathematicians and she started bugging them for math puzzles.

Her involvement with math was interrupted by the death of her parents — her mother when she was seven, and her father when she was nine. She ended up living with her sister, but felt very lonely.

After several years of personal turmoil, she renewed her pursuit of mathematics. Lida started discussing math with her mother’s first husband. She joined a math circle which was run at Moscow State University. When she was 13 she went to a summer camp and found a mentor there to study trigonometry. Eventually she ended up at School Number 425, one of the first schools in Moscow that opened for children gifted in math.

At the end of high school she went to the IMO as part of the Soviet team and won a gold medal there. After that she enrolled in the most prestigious Soviet institute for the study of math — Moscow State University (MSU).

Half of her high school classmates went to MSU, including her high school sweetheart Alexander Geronimus. Lida married Alexander when she was a sophomore and they had their first son in her fourth year of undergraduate school.

Meanwhile, she wasn’t doing as well in her studies as she had hoped. Lida was very fast to pick up math ideas during conversations, but she had difficulty reading books. As ideas were becoming more complicated and involved, this became a problem. She started feeling that she was falling behind her friends. When her friends gathered together to discuss mathematics she couldn’t understand everything. She wanted to ask questions, but was too shy. Plus, she didn’t want to impose on them. She made a decision to be silent. As a result she started ignoring the conversations of others and became discouraged as she fell behind.

She had her second child at the beginning of graduate school, where she studied under the supervision of Dmitry Fuchs. Lida was already losing her self-esteem and so she chose a self-contained problem that didn’t require a lot of outside knowledge. The solution involved some combinatorial methods, but Lida didn’t quite understand the big picture and the problem’s goal.

I contacted Dmitry Fuchs and asked him about Lida’s thesis. He told me that Lida’s main result is extremely important and widely cited. It is called Goncharova’s theorem.

Meanwhile, her husband finished his PhD in math and secured a great job in an academic institution. They had started as peers, but her work was interrupted by having their children. Lida finished her PhD a couple of years after her husband and got a very boring job as an algorithm designer. She even wrote some papers at the job, but she was not much interested. She continued her attempts to do mathematics and continued asking everyone for problems, but it didn’t go anywhere. Her friends were not very interested in her calculations and after the birth of her third child she began to lose hope in her research.

When Lida and her husband entered graduate school they became religious. Ten years later, Alexander decided to pursue the Russian Orthodox religion as a career and got a parish in 600 km from Moscow. They didn’t want to move their children away from Moscow, with its educational and cultural opportunities. So they started living in two places with long commutes. This didn’t help her math either.

Eight years after the third son, the fourth son was born. Although Lida sporadically continued her calculations, she still didn’t talk about them to anyone.

When the older children went to high school, Lida enjoyed solving their math problems tremendously. In 1990 perestroika started and Lida lost her job. She got an offer to create a private school and teach there. By this time she had had two more children, a son and a daughter. Lida continued working for the private school until her six children grew out of it. Lida enjoyed teaching and inventing methods to teach mathematics. The school ended in 2004. But she continues working with kids sharing with them her joy of mathematics.

Lida believes that she has had an extremely lucky life in many ways. The only exception was her unsuccessful math career. She can’t live without math, and will continue working with kids, solving fun problems and doing her private research.

When I first called her and said I wanted to talk about her and math, she told me: —There is nothing to talk about. I stopped doing math after my PhD. Almost.— That —almost— kept me asking questions.

Lida’s teammates

Janet Mertz was considering a serious research project comparing the fates of IMO medal girls with the fates of their teammates, to see whether gender plays a role later. However, due to the language and cultural differences and the fact that most of the girls changed their last name, it was difficult to locate them. So Mertz put this research project on hold.

She had asked me to find and contact the Russian women and I was so fascinated with Lida’s story that I decided to write it up in this article. And because the research is on hold, I decided to include the fates of Lida’s teammates.

Lida Goncharova got her gold medal in the 1962 IMO with 42 points and was ranked third. The teammate with the closest score was Joseph Bernstein with another gold medal and 46 points. I don’t even have to check Wikipedia to tell you about Joseph, as I was once married to him. He used to be a professor at Harvard University and is now a professor at Tel-Aviv University. He is a member of the Israel Academy of Sciences and Humanities and the United States National Academy of Sciences. He achieved a lot and is greatly respected by his peers.

Joseph Bernstein might not be the best person to compare Lida to as he had a perfect score. Some might argue that a perfect score indicates that he might have done better if the problems had been more difficult.

The two Soviet teammates whose scores were the closest to that of Lida, but below her, were Alexey Potepun with 37 points and Grigory Margulis with 36 points.

Alexei Potepun got a PhD in mathematics and is now a professor at Saint-Petersburg University. He has published eleven papers.

Next to Alexey Potepun is Grigory Margulis, who is a professor at Yale and was awarded the Fields Medal and the Wolf Prize. He is a member of the U.S. National Academy of Sciences.

You might notice that the two people who moved to the US are much more famous than those who stayed in Russia. You might say that moving to the US is a better predictor of success than gender. Sure, living in a free country helps, but Margulis got his Fields medal while he was in the USSR. And Bernstein invented his famous D-Modules while in Russia also.

My conversation with Lida was personally inspiring. I loved the tone of her voice when she talked about mathematics. There were many elements that prevented her from having the mathematical career she might have had: the untimely death of her parents, her shyness, raising six children, many years of long commutes. When we look at the achievements of her closest teammates, we can’t help but wonder what kind of mathematics we lost.

This conversation was very encouraging for me. I felt there were similarities between Lida and myself in more ways than I expected. What we share most of all is a love for mathematics. I could hear that in her voice.

I gave my students a problem from the 2002 AMC 10-A:

Tina randomly selects two distinct numbers from the set {1, 2, 3, 4, 5}, and Sergio randomly selects a number from the set {1, 2, …, 10}. The probability that Sergio’s number is larger than the sum of the two numbers chosen by Tina is: (A) 2/5, (B) 9/20, (C) 1/2, (D) 11/20, (E) 24/25.

Here is a solution that some of my students suggested:

On average Tina gets 6. The probability that Sergio gets more than 6 is 2/5.

This is a flawed solution with the right answer. Time and again I meet a problem at a competition where incorrect reasoning produces the right answer and is much faster, putting students who understand the problem at a disadvantage. This is a design flaw. The designers of multiple-choice problems should anticipate mistaken solutions such as the one above. A good designer would create a problem such that a mistaken solution leads to a wrong answer — one which has been included in the list of choices. Thus, a wrong solution would be punished rather than rewarded.

Readers: here are three challenges. First, to ponder what is the right solution. Second, to change parameters slightly so that the solution above doesn’t work. And lastly, the most interesting challenge is to explain why the solution above yielded the correct result.