Tanya Khovanova's Math Blog

I am starting yet another part-time job as the Head Mentor at PRIMES, a new MIT research program for high schoolers. I am very excited about this program, for it will be valuable not only to kids who want to become researchers, but also to kids who just want to see what research is like. Kids who want to learn to think in a new way will also find it highly useful.

PRIMES is in many ways similar to RSI, which it augments and complements. There are also a lot of differences. Keep in mind that I am only comparing PRIMES to the math part of RSI, with which I was working as a coordinator for two years. I do not know how RSI handles other sciences.

Different time scale. RSI lasts six weeks; PRIMES will take about a year. I already wrote about some peoples’ skepticism towards RSI in my piece called “Fast Food Research?.” PRIMES creates a more natural pace for research.

Choices. Because of the time schedule at RSI, students get their project as soon as they start. Students who realize by the end of the second week that they do not like their project are at a disadvantage: if they do not change their project, they’re stuck with something that does not inspire them or is too difficult, and if they do change their project, they won’t have enough time to do a great job. At PRIMES students will have time to talk to the mentors before starting their project, so that they can participate in choosing their project. Depending on how it goes later, they’ll have time to try several different directions. I believe that the best research comes from the heart: students who have the time and opportunity to shape their choices will be more invested in their project.

Application process. At RSI, The Center for Excellence in Education reviews the applications. Even though they usually do a superb job at sending us great students, I believe it would be an advantage if mentors were able to influence the review process, for they might find even better matches to their projects. At PRIMES, the mentors will have this opportunity to review the applications.

Geography. RSI accepts students from all over the US and from some other countries. PRIMES can only accept local students — those who live close enough to visit MIT once a week for four months. Because of this restriction, PRIMES is recruiting from a smaller pool of students than RSI. But for local students it means that it will be easier to get accepted to PRIMES than to RSI.

Coaching. At RSI, students get a lot of coaching. I think that every student is in close contact with four adults. Two of them are from the math department — mentor and coordinator (that’s me!) — and two tutors from CEE. PRIMES will have less coaching. A student will have a mentor and me, the head mentor. In addition, mentors might arrange for students to talk to the professors who originated their projects.

Immersion. RSI students are physically present. They are housed at MIT with the expectation that they completely devote their time to their research. Students at PRIMES will be integrating their research into the rest of their lives and their commitments. That will require good organizational skills and a lot of self-discipline. RSI students have discipline imposed on them by their situation — which may be an advantage to them.

Olympiads. While they are at RSI, students can’t go to IMO or other summer activities. This is why many strong Olympiad students choose not to go to RSI, or they turn down an RSI acceptance if in the meantime they have gotten on to an Olympic team. At PRIMES you can do both. It is possible to go to an Olympiad, in addition to writing a paper.

Grade. RSI students have to be juniors. There are no grade limitations for PRIMES. Thus, it is possible to go to PRIMES in one’s senior year. In this case, it may be too late to use PRIMES on college applications, but it is perfectly fine for the sake of research itself. Or it might be possible to go to PRIMES as a sophomore, and then apply for RSI the next year. This will strengthen the student’s application for RSI.

RSI is well-established and has proven itself. PRIMES is new and hopefully will offer young mathematicians additional opportunities to try research.

I think that the American system of education creates a lot of pressure for teachers to drill their students for standardized tests and multiple choice questions. This blocks creative thinking. Every program like PRIMES is very good for unleashing students’ creativity and contributing to the development of the future thinkers of American society.

Silvio Micali taught me cryptography. To explain one-way functions, he gave the following example of encryption. Alice and Bob procure the same edition of the white pages book for a particular town, say Cambridge. For each letter Alice wants to encrypt, she finds a person in the book whose last name starts with this letter and uses his/her phone number as the encryption of that letter.

To decrypt the message Bob has to read through the whole book to find all the numbers. The decryption will take a lot more time than the encryption. If the book increases in size the time it takes Alice to do the encryption almost doesn’t increase, but the decryption process becomes more and more draining.

This example is very good for teaching one-way functions to non-mathematicians. Unfortunately, the technology changes and the example that Micali taught me fifteen years ago isn’t so cute anymore. Indeed you can do a reverse look-up online of every phone number in the white pages.

I still use this example, with an assumption that there is no reverse look-up. I recently taught it to my AMSA students. And one of my 8th graders said, “If I were Bob, I would just call all the phone numbers and ask their last names.”

In the fifteen years since I’ve been using this example, this idea never occurred to me. I am very shy so it would never enter my mind to call a stranger and ask for their last name. My student made me realize that my own personality affected my mathematical inventiveness.

Since modern technology is murdering my 15-year-old example, I would like to ask my readers to suggest other simple examples of one-way functions or ways to resurrect the white pages example.

I received a message at the beginning of October: “This month has 5 Fridays, 5 Saturdays and 5 Sundays; this only happens every 823 years.”

Wait a minute. The Gregorian calendar cycles every 400 years. Where is the figure of 823 coming from?

Wait another minute. Within a century the calendar repeats itself every 28 years. So we are guaranteed that October 2038 will be the same as October 2010.

Wait one more minute. To have a month with five Fridays, Saturdays and Sundays, we need a month that has 31 days and starts on a Friday. There are seven months a year with 31 days, so on average we would expect to have such a month once a year.

If you study the calendar you can see that the seven long months start on six different days. This means that two of the months start on the same day and one of the days is skipped altogether. We see this in both leap years and non-leap years.

Ironically, 2010 is the year with two long months starting on Friday — October and January. Despite the claims of the email about this only happening every 823 years, in fact the same phenomenon occurred twice this year. The next time this will happen is in July 2011.

For those people who get all excited when a month has five Fridays, five Saturdays and five Sundays, I have good news for you. The month following each of these months has to start on Monday. And unless it is a February of a non-leap year, it will have five Mondays.

I asked my son Alexey Radul what exactly he is doing for his postdoc at the Hamilton Institute in Ireland. Here is his reply:

The short, jargon-loaded version: We are building an optimizing compiler for a programming language with first-class automatic differentiation, and exploring mathematical foundations, connections, applications, etc.

Interpretation of jargon:

Automatic differentiation is a technique for turning a program that computes a function into a program that computes that function together with its derivative; with a constant factor overhead. This is better than the usual symbolic differentiation that, say, Mathematica does because there is no intermediate-expression bulge. For example, if your function is a large product

Product f1(x) f2(x) … fn(x),

the symbolic derivative has size n²

Sum (Product f1′(x) f2(x) … fn(x)) (Product f1(x) f2′(x) … fn(x)) … (Product f1(x) f2(x) … fn'(x))

automatic differentiation avoids that cost. Automatic (as opposed to symbolic) differentiation also extends to conditionals, data structures, higher-order functions, and all the other wonderful things that distinguish a computer program from a mathematical expression.

First-class means that the differentiation operations are normal citizens of the programming language. This is not the case with commonly used automatic differentiation systems, which are all preprocessors that rewrite C or Fortran source code. In particular, we want to be able to differentiate any function written in the language, even if it is a derivative of something, or contains a derivative of something, etc. The automatic differentiation technique works but becomes more complicated in the presence of higher order, multivariate, or nested derivatives.

We are building an optimizing compiler because the techniques necessary to get good performance and correct results with completely general automatic differentiation are exactly the techniques used to produce aggressive optimizing compilers for functional languages, so we might as well go all the way.

It appears that the AD trick (or at least half of it) is just an implementation of synthetic differential geometry in the computer. This leads one to hope that a good mathematical foundation can be found that dictates the behavior of the system in all the interesting special cases; there is lots of math to be thought about in the vicinity of this stuff.

Applications are also plentiful. Any time you want to optimize anything with respect to real parameters, gradients help. Any time you are dealing with curves, slopes help. Computer graphics, computer vision, physics simulations, economic and financial models, probabilities — there’s so much stuff to apply a high quality such system to that we don’t know where to begin.

I usually give a lot of lectures and I never used to announce them in my blog. This time I will give a very accessible lecture at the MIT “Women in Mathematics” series. It will be on Wednesday October 6th at 5:30-6:30 PM in room 2-135. If you are in Boston, feel free to join. Here is the abstract.

I will discuss several coin-weighing puzzles and related research. Here are two examples of such puzzles:

1. Among 10 given coins, some may be real and some may be fake. All real coins weigh the same. All fake coins weigh the same, but have a different weight than real coins. Can you prove or disprove that all ten coins weigh the same in three weighings on a balance scale?

2. Among 100 given coins, four are fake. All real coins weigh the same. All fake coins weigh the same, but they are lighter than real coins. Can you find at least one real coin in two weighings on a balance scale?

You are not expected to come to my talk with the solutions to the above puzzles, but you are expected to know how to find the only fake coin among many real coins in the minimum number of weighings.

In 2009 I was working at MIT coordinating math research for Research Science Institute for high school students. One of our students Jacob Hurwitz got a project on decycling graphs.

“Decycling” means removing vertices of a graph, so that the resulting graph doesn’t have cycles. The decycling number of a graph is the smallest number of vertices you need to remove.

Decycling is equivalent to finding induced forests in a graph. The set of vertices of the largest induced forest is a complement to the smallest set of vertices you need to remove for decycling.

Among other things, Jacob found induced trees and forests of the highest densities on graphs of all semi-regular tessellations. On the pictures he provided for this essay, you can see an example of a tessellation, a corresponding densest forest, and a corresponding densest tree. The density of the forest and the tree is 2/3, meaning that 1/3 of the vertices are removed.

To motivate RSI students I tried to come up with practical uses for their projects. When I was talking to Jacob about decycling, the only thing I could think of was terrorists. When terrorists create their cells, they need to limit connections among themselves, in order to limit the damage to everyone else in the cell if one of them gets busted.

That means the graph of connections of a terrorist cell is a tree. Suppose there is a group of people that we suspect, and we know the graph of their contacts, then the decycling number of the graph is the number of people that are guaranteed to be innocent.

Have you noticed how Facebook and LinkedIn are reasonably good at suggesting people you might know? The algorithm they use to analyze the data is fairly effective in revealing potential connections. Recently, someone was able to download all of the Facebook data, which means that any government agency ought to be able to do the same thing. They could analyze such data to discover implicit connections. As a byproduct of looking for terrorists, they would also discover all of our grudges.

Oh dear. What are they going to think when they find out I’m not connected to my exes?

In the name of privacy, I have changed the names of the men I did not marry. But there is no point in changing the names of my ex-husbands, as my readers probably know their names anyway.

I received my first marriage proposal when I was 16. As a person who was unable to say “no” to anything, I accepted it. Luckily, we were not allowed to get married until I was 18, the legal marriage age in the USSR, and by that time we broke up.

To my next proposal, from Sasha, I still couldn’t say “no”, and ended up marrying him. The fact that I was hoping to divorce him before I got married at 19 shows that I should have devoted more effort in learning to say “no”. I decided to divorce him within the first year.

My next proposal came from Andrey, I said yes, with every intention of living with Andrey forever. We married when I was 22 and he divorced me when I was 29.

After I recovered from my second divorce, I had a fling with an old friend, Sam, who was visiting Moscow on his way to immigrate to Israel.

Sam proposed to me in a letter that was sent from the train he took from the USSR to Israel. At that point I realized I had a problem with saying “no”. The idea of marrying Sam seemed premature and very risky. I didn’t want to say yes. I should have said no, but Sam didn’t have a return address, so I didn’t say anything.

That same year I received a phone call from Joseph. Joseph was an old friend who lived in the US, and I hadn’t seen or heard from him for ten years. He invited me to visit him in the US and then proposed to me the day after my arrival. The idea of marrying Joseph seemed premature and very risky, but in my heart it felt absolutely right. I said yes, and I wanted to say yes.

I was very glad that I hadn’t promised anything to Sam. But I felt uncomfortable. So even before I called my mother to notify her of my marriage plans, I located Sam in Israel and called him to tell him that I had accepted a marriage proposal from Joseph. I needed to consent to marry someone else as a way of saying “no” to Sam.

After I married Joseph, I came back to Russia to do all the paperwork and pick up my son, Alexey for our move to the US. There I met Victor. I wasn’t flirting with Victor and was completely disinterested. So his proposal came as a total surprise. That was the time I realized that I had a monumental problem with saying “no”. I had to say “no” to Victor, but I couldn’t force myself to pronounce the word. Here is our dialogue as I remember it:

• Me: I can’t marry you, I am already married.
• Victor: I am sure it’s a fictitious marriage; you just want to move to the USA.
• Me: That’s not true. It’s a real marriage.
• Victor: If it were a fictitious marriage, you wouldn’t admit it. So, it’s a fictitious marriage. My proposal stands.

My sincere attempt at saying “no” didn’t work. I moved to the US to live with Joseph and I soon got pregnant. Victor was the first person on my list to notify — another rather roundabout way to reject a proposal.

The marriage lasted eight years. Sometime after I divorced Joseph, I met Evan who invited me on a couple of dates. I wasn’t sure I wanted to get involved with him. But he proposed and got my attention. I was single and available, though I had my doubts about him.

Evan mentioned that he had royal blood. So I decided to act like a princess. I gave him a puzzle:

I have two coins that together make 15 cents. One of them is not a nickel. What are my coins?

He didn’t solve it. In and of itself, that wouldn’t be a reason to reject a guy. But Evan didn’t even understand my explanation, despite the fact that he was a systems administrator. A systems administrator who doesn’t get logic is a definite turn-off.

So I said “no”! That was my first “no” and I have mathematics to thank.

When the Women and Math program at IAS was coming to an end, Ingrid Daubechies invited me to a picnic at her place for PACM

(The Program in Applied and Computational Mathematics at Princeton University). I accepted with great enthusiasm for three reasons: I was awfully tired and needed a rest; PACM was my former workplace, so I was hoping to meet old acquaintances; and most of all, I loved the chance to hang out with Ingrid.

Ingrid is a great cook, so she prepared some amazing deserts for the picnic. While I was helping myself to a second serving of her superb lemon mousse, a man asked me if I was Ingrid’s sister. Ingrid overheard this and laughingly told him that we are soul-sisters.

I admire Ingrid, so at first I took this as a compliment and felt all warm and fuzzy. But when my critical reasoning returned, I had to ask myself: Why would someone think I am Ingrid’s sister with my Eastern European round face, my Russian name and my Russian accent?

I started talking to the man. He asked me what I do. I told him that I am a mathematician. He was stunned. What is so surprising in meeting a mathematician at a math department picnic?

Now I think I understand what happened. It never occurred to him that I was a mathematician. I was clearly unattached, so he couldn’t place me as someone’s wife. As the picnic was at Ingrid’s house, he must have concluded that I had to be Ingrid’s relative. Very logical, but very gender biased.

I heard this problem many years ago when I was working for Math Alive.

Three men are fighting in a truel. Andrew is the worst shot; he misses 2/3 of the time. Bob is better; he misses 1/3 of the time. Connor is the best shot; he always hits. Each of the three men have an infinite number of bullets. Each shot is either a kill or a miss. They have to shoot at each other in order until two of them are dead. To make it more fair they decide to start with Andrew, followed by Bob, and then Connor. We assume that they choose their strategies to maximize their probability of survival. At whom should Andrew aim for his first shot?

This is a beautiful probability puzzle, and I will not spoil it for you by writing a solution. Recently, I watched an episode of Numb3rs: The Fifth Season (“Frienemies”) which featured a version of this puzzle. Here is how Dr. Marshall Penfield, a frienemy of the protagonist Charlie Eppes, describes it:

Imagine a duel between three people. I’m the worst shot; I hit the target once every three trials. One of my opponents [Charlie] is better; hits it twice every three shots. The third guy [Colby] is a dead shot; he never misses. Each gets one shot. As the worst I go first, then Charlie, then Colby. Who do I aim for for my one shot?

This is a completely different problem; it’s no longer about the last man standing. Colby doesn’t need to shoot since the other two truelists have already expended their only shots. If Charlie believes that Colby prefers nonviolence, all else being equal, then Charlie doesn’t need to shoot. Finally, the same is true of Marshall. There is no point in shooting at all.

To make things more mathematically interesting, let’s assume that the truelists are bloodthirsty. That is, if shooting doesn’t decrease their survival rate, they will shoot. How do we solve this problem?

If he survives, Colby will kill someone. If Charlie is alive during his turn, he has to shoot Colby because Colby might kill him. What should Marshall do? If Marshall kills Colby, then Charlie misses Marshall (hence Marshall survives) with probability 1/3. If Marshall kills Charlie, then Marshall is guaranteed to be killed by Colby, so Marshall survives with probability 0. If he doesn’t kill anyone, things look much better: with probability 2/3, Colby is killed by Charlie and Marshall survives. Even if Colby is alive, he does not necessarily shoot Marshall, so Marshall survives with probability at least 2/3. Overall, Marshall’s chances of staying alive are much better if he misses. He should shoot in the air!

The sad part of the story is that Charlie Eppes completely missed. That is, he completely missed the solution. In the episode he suggested that Marshall should shoot Charlie. If Marshall shoots Charlie, he will be guaranteed to die.

It is disappointing that a show about math can’t get its math right.

From the 1966 Moscow Math Olympiad:

Prove that you can choose six weights from a set of weights weighing 1, 2, …, 26 grams such that any two subsets of the six have different total weights. Prove that you can’t choose seven weights with this property.

Let us define the sequence a(n) to be the largest size of a subset of the set of weights weighing 1, 2, …, n grams such that any subset of it is uniquely determined by its total weight. I hope that you agree with me that a(1) = 1, a(2) = 2, a(3) = 2, a(4) = 3, and a(5) = 3. The next few terms are more difficult to calculate, but if I am not mistaken, a(6) = 3 and a(7) = 4. Can you compute more terms of this sequence?

Let’s see what can be said about upper and lower bounds for a(n). If we take weights that are different powers of two, we are guaranteed that any subset is uniquely determined by the total weight. Thus a(n) ≥ log₂n. On the other hand, the total weight of a subset has to be a number between 1 and the total weight of all the coins, n(n+1)/2. That means that our set can have no more than n(n+1)/2 subsets. Thus a(n) ≤ log₂(n(n+1)/2).

Returning back to the original problem we see that 5 ≤ a(26) ≤ 8. So to solve the original problem you need to find a more interesting set than powers of two and a more interesting counting argument.