Tanya Khovanova's Math Blog

I enjoy doing research in recreational mathematics. The biggest problem is that the probability that something I’ve done has already been done before is very high. This is partially because of the nature of this area of research. Trying to find new questions that are not buried deep in the abstract means someone else could have stumbled upon the same question. In addition, I like going in different directions: geometry, number theory, probability, combinatorics, and so on. That means I am not an expert in any of the areas. This too increases my probability of doing something that has already been done before.

This is quite unpleasant: to discover that I reinvented the wheel. And I keep reinvented different wheels on a regular basis. When I complain, my mathematician friends give me the same advice over and over:

Find your own niche!

I’ve been trying to understand what they mean, and finally I got it:

Do something no one else is interested in using methods no one else can understand.

Finding a topic that is not interesting almost guarantees that other people didn’t do it before. Developing new complicated methods helps limit the number of followers and prevents the niche from becoming crowded.

Now I know why I see so many boring math papers I can’t understand.

To hell with my own niche!

Let me start with a real story that happened a long time ago when I worked with my co-author on a math project. When I told him the idea I came up with, he dismissed it. The next day he came to me very excited with his new idea. He repeated the idea I had proposed the day before.

I said, “I suggested this exact idea to you yesterday.” He didn’t believe me. Luckily for our relationship, I knew him very well. He was not a person who lied. I remembered how preoccupied he was when I had laid out the idea to him. Now I think that he didn’t pay attention to my idea at the time, but it was lodged somewhere in his subconscious and surfaced later. I am sure that he truly believed that the idea was his. (Unfortunately, he didn’t believe me. But this is another story.)

This story made me think about the nature of collaboration and how people can’t really separate ownership of the results of a joint project. Let me tell you another story, one that I do not remember happening, although it could have.

I was working on a paper with my co-author on Sharelatex. One day an idea for a lemma came to me that we hadn’t discussed before. My co-author lives in a different time zone, so instead of discussing the idea with him, I just added Lemma 3 and its proof to our paper. I was truly proud of my own contribution.

The next day I came up with Lemma 4 while driving back home. It was another completely new direction for our research. When I came home to my laptop, I discovered my Lemma 4 neatly written and proven by my co-author. Is this lemma his? It can’t be completely his. It was a natural extension of what we discussed; he just got to a computer before me.

Did you notice in the last story that the situation is symmetric, but my hypothetical feelings are not? In a true collaboration ideas are bounced off each other. Very often people come up with the same idea at the same time, but you can’t ascribe ownership to the first person who speaks. Because of many stories like this, I made a rule for myself: never discuss in public who did what in a joint paper. Just always say “we.”

Unfortunately I keep forgetting to teach my PRIMES/RSI students that. The question usually doesn’t come up until it is too late, when one of the students in a group project during a presentation says, “I proved Theorem 5.” Oops!

Round 1 of Who Wants to Be a Mathematician had the following math problem:

Bob and Jane have three children. Given that one child is their daughter Mary, what is the probability that Bob and Jane have at least two daughters?

In all such problems we usually make some simplifying assumptions. In this case we assume that gender is binary, the probability of a child being a boy is 1/2, and that identical twins do not exist.

In addition to that, every probability problem needs to specify the distribution of events over which the probability is calculated. This problem doesn’t specify. This is a mistake and a source of confusion. In most problems like this, the assumption is that something is chosen at random. In this type of problem there are two possibilities: a family is chosen at random or a child is chosen at random. And as usual, different choices produce different answers.

The puzzle above is not well-defined, even though this is from a contest run by the American Mathematical Society!

Here are two well-defined versions corresponding to two choices in randomization:

Bob and Jane is a couple picked randomly from couples with three children and at least one daughter. What is the probability that Bob and Jane have at least two daughters?

Mary is a girl picked randomly from a pool of children from families with three children. What is the probability that Mary’s family has at least two daughters?

Now, if you don’t mind, I’m going to throw in my own two cents, that is to say, my own two puzzles.

Harvard researchers study the influence of identical twins on other siblings. For this study they invited random couples with three children, where two of the children are identical twins.

1. Bob and Jane is a couple picked randomly from couples in the study with at least one daughter. What is the probability that Bob and Jane have at least two daughters?
2. Mary is a girl picked randomly from a pool of children participating in the study. What is the probability that Mary’s family has at least two daughters?

The puzzle Family Ties was written for the 2013 MIT Mystery Hunt, but it never made it to the hunt. Here’s your chance to solve a puzzle no one has seen before. I wrote the puzzle jointly with Adam Hesterberg. The puzzle is below:

Mathematics professor S. Lee studies genealogy and is interested in the origins of life.

1. Alexei Mikhailovich Ivanov
2. Alexei Petrovich Ivanov
3. Amminadab
4. Anna of Moscow
5. Arador
6. Arahad II
7. Arassuil
8. Arathorn I
9. Arathorn II
10. Aravorn
11. Argonui
12. Asger Thomsen
13. Caecilia Metella Dalmatica
14. Egmont
15. Eldarion
16. Ellesar
17. Endeavour
18. Faustus Cornelius Sulla
19. Henry Frederick
20. Hezron
21. Isaac
22. Ivan the Great
23. Ivan the Terrible
24. Jacob
25. James I and VI
26. James V
27. Jens Knudsen
28. John Francis
29. Joseph Patrick
30. Joseph Patrick
31. Jørgen Jensen
32. Judah
33. Knud Nielsen
34. Margaret Stuart
35. Maria Donata
36. Mary Stuart
37. Matthew Rauch
38. Mikhail Ivanovich Ivanov
39. Niels Møller
40. Ole Pedersen
41. Peder Petersen
42. Peter Jørgensen
43. Petr Alexeyevich Ivanov
44. Pharez
45. Ram
46. Robert Francis
47. Rose Elizabeth
48. Søren Thomsen
49. Thomas Olsen
50. Ursula Gertrud
51. Vasily I of Moscow
52. Vasily II of Moscow
53. Vasili III of Russia
54. Yuri of Uglich
55. Zerah

I promised to explain my job situation to my readers. I currently have six part-time jobs, which I describe below in the order that I started them.

The job I have had the longest is coaching math for competitions at AMSA Charter School. I started there in the spring of 2008 and I am still teaching there every week. I post my homework assignments on my webpage for other teachers and students to use.

The next longest has been as the Head Mentor at RSI, which I started in the summer of 2009. RSI is a great program where high school students from all over the world come to MIT to do research during summer vacations. It is amazing how much an ambitious student can do during a short five-week period. My first year I saw some great research done, but I was surprised that RSI papers were generally not available online. Beginning in 2012, at my recommendation, our Director Slava Gerovitch now posts the RSI papers at the math department RSI webpage.

As good a program as it is, RSI is too short for a research project. So we decided to develop our own program called PRIMES (Program for Research in Mathematics, Engineering, and Science for High School Students). I am also the Head Mentor in this program. I provide general supervision of all the projects and review conference slides and final papers. In addition to being the Head Mentor, I mentor my own students, which is great fun. I usually have three projects, but if something happens to a project or a mentor, I take it over.

Together with Pavel Etingof, PRIMES Chief Research Advisor, and Slava Gerovitch, PRIMES Director, I wrote an article Mathematical Research in High School: The PRIMES Experience that appeared in Notices.

My job #4, since the fall of 2013, is as a Teaching Assistant for the MIT linear algebra course.

This year I took on two more jobs at MIT. I am the Head Mentor at Mathroots, a summer program for high school students from underrepresented backgrounds. I am also teaching at PRIMES STEP, the program for gifted middle-school students in the Boston area. The goal of the program is to teach students mathematical thinking, have fun, and prepare them for PRIMES.

Overall, I have reached the stage in my career when I do not have time to breath and I still do not make enough money to pay my bills. The good news: my jobs bring me satisfaction. I just hope that I will not be too tired to notice that I am satisfied.

I already wrote about the sliding-window variation of the Secretary Problem. In this variation, after interviewing a candidate for the job, you can pick him or any out of w − 1 candidates directly before him. In this case we say that we have a sliding window of size w. The strategy is to skip the first s candidates, then pick the person who is better than anyone else at the very last moment. I suggested this project to RSI and it was picked up by Abijith Krishnan and his mentor Shan-Yuan Ho. They did a good job that resulted in a paper posted at the arXiv.

In the paper they found a recursive formula for the probability of winning. The formula is very complicated and not explicit. They do not discuss the most interesting question for me: what is the advantage of a sliding window? How much better the probability of winning with the window as opposed to the classical case without the window?

Let us start with a window of size 2, and n applicants. We compare two problems with the same stopping point. Consider the moment after the stopping point when we see a candidate who is better than everyone else before. Suppose this happens in position b. Then in the classic problem we chose this candidate. What is the advantage of a window? When will we be better off with the window? We will be better if the candidate at index b is not the best, and the window allows us to actually reach the best. This depends on where the best secretary is, and what happens in between.

If the best secretary is the next, in position b + 1, then the window gives us an advantage. The probability of that is 1/n. Suppose the best candidate is the one after next, in position b + 2. The window gives us an advantage only if the person in position b + 1 is better than the person in position b. What is the probability of that? It is less than 1/2. From a random person the probability of the next one being better is 1/2. But the person in position b is not random, he is better than random, so the probability of getting a person who is even better decreases and is not more than 1/2. That means the sliding window wins in this case with probability not more than 1/2n.

Similarly, if the best candidate is in position b + k, then the sliding window allows us to win if every candidate between b and b + k is better than the previous one. The probability of the candidate being better at every step is not more than 1/2. That means, the total probability of getting to the candidate in position b + k is 1/2^k-1. So our chances to win when the best candidate is at position b + k are not more than 1/2^k-1n. Summing everything up we get an advantage that is at least 1/n and not more than 2/n.

The probability of winning in the classical case is very close to 1/e. Therefore, the probability of winning in the sliding window case, given that the size of the window is 2, is also close to 1/e.

Let us do the same for a window of any small size w. Suppose the best secretary is in the same window as the stopping candidate and after him, that is, the best candidate is among the next w − 1 people. The probability of this is (w − 1)/n. In this case the sliding window always leads to the best person and gives an advantage over the classical case. When else does the sliding window help? Let us divide the rest of the applicants into chunks of size w − 1. Suppose the best applicant is in the chunk number k. For the sliding window to allow us to get to him, the best candidate in every chunk has to be better than the best one in the previous chunk. The probability of that is not more than 1/2^k-1. The probability that we get to this winner is not more that (w-1)/2^k-1n. Summing it all up we get that the advantage of the window of size w is between (w − 1)/n and 2(w − 1)/n.

I already wrote about my favorite problem from the 2015 All-Russian Math Olympiad that involved tanks. My second favorite problem is about coins. I do love almost every coin problem.

A coin collector has 100 coins that look identical. He knows that 30 of the coins are genuine and 70 fake. He also knows that all the genuine coins weigh the same and all the fake coins have different weights, and every fake coin is heavier than a genuine coin. He doesn’t know the exact weights though. He has a balance scale without weights that he can use to compare the weights of two groups with the same number of coins. What is the smallest number of weighings the collector needs to guarantee finding at least one genuine coin?

My name is Tanya and here’s why. When my mom was pregnant, she was discussing the child’s name with my father, Gueliy Khovanov. They decided that she could choose a boy’s name while he could choose a girl’s name. She wanted me to be Andrey in honor of her half-brother who died in World War II. He wanted me to be Tanya in honor of the unrequited love of his life. In an act of incomprehensible generosity, my mother agreed to name me after this woman. My parents were not even married when I was born.

After the decision was made, I was born on my own Name Day. In Russian culture, different names are celebrated on different dates. The a holiday for Tanyas is especially big and it falls on January 25, the day I was born. This serendipity led me to be very attached to my given name.

When I was a child, I believe that my father introduced me to his love, Tanya, although I do not have any clear memory of her. I doubt they were ever actually together. I do remember how my father loved her all his life. Even today I am sure that his love for Tanya brushed off on me, being her namesake.

I especially remember one day, when I was still a kid, my father agonizing about Tanya and calling to offer her help. My mom grimaced when he offered to babysit her children. My parents were divorced by then, and my father showed no interest in babysitting his own children. Now I understand that watching Tanya’s children was the least he could do. This was happening in 1968 when the USSR invaded Czechoslovakia, and Tanya’s husband, Konstantin Babitsky, was one of the few people in the USSR who risked their lives to openly protest against it. Tanya’s life and freedom were also at risk. Offering any help was the right and only call.

Right before my father died of an illness in 1980, he asked me for one last favor: to tell Tanya that he had died. I was 20 years old and didn’t have a clue how to find her; I only knew that her name was Tanya Velikanova. She was a famous Soviet human rights activist and dissident. That made it dangerous for me and for the people I might ask for assistance.

I finally asked my father’s best friend to do it for me. He said that Tanya was in exile, but promised to pass a message to her. I am not sure he did it and I still feel guilty that I didn’t do it myself before she died.

I forgot to tell you how my dad met the love of his life. They met as teenagers at a math Olympiad, where she beat him.

I already wrote how I build a magic SET hypercube with my students. Every time I do it, I can always come up with a new question for my students. This time I decided to flip over two random cards, as in the picture. My students already know that any two cards can be completed to a set. The goal of this activity is to find the third card in the set without trying to figure out what the flipped-over cards are. Where is the third card in the hypercube?

Sometimes my students figure this out without having an explicit rule. Somehow they intuit it before they know it. But after several tries, they discover the rule. What is the rule?

Another set of questions that I ask my students is related to magic SET squares that are formed by 3 by 3 regions in the hypercube. By definition, each magic SET square has every row, column, and diagonal as a set. But there are four more sets inside a magic SET square. We can call them super and sub-diagonal (anti-diagonal) wrap-arounds. Can you prove that every magic SET square has to have these extra four sets? In addition, can you prove that a magic SET square is always uniquely defined by any three cards that do not form a set, and which are put into places that are not supposed to from a set?

I love The Secretary Problem. I first heard about it a long time ago with a different narrative. Then it was a problem about the marriage of a princess:

The king announces that it is time for his only daughter to marry. Shortly thereafter 100 suitors line up in a random order behind the castle walls. Each suitor is invited to the throne room in the presence of the princess and the king. At this point, the princess has to either reject the suitor and send him away, or accept the suitor and marry him. If she doesn’t accept anyone from the first 99, she must marry the last one. The princess is very greedy and wants to marry the richest suitor. The moment she sees a suitor, she can estimate his wealth by his clothes and his gifts. What strategy should she use to maximize the probability of marrying the richest person?

The strategy contains two ideas. The first idea is trivial: if the princess looks at a suitor and he is not better than those she saw before, there is no reason to marry him. The second idea is to skip several suitors at the beginning, no matter how rich they might seem. This allows the princess to get a feel for what kinds of suitors are interested in her. Given that we know the strategy, the interesting part now is to find the stopping point: how many suitors exactly does she have to skip? The answer is ⌊N/e⌋. (You might think that this formula is approximate. Surprisingly, it works for almost all small values. I checked the small values and found a discrepancy only for 11 and 30 suitors.)

The problem is called The Secretary Problem, because in one of the set-ups the employer tries to hire a secretary.

In many situations in real life it is a good idea to sample your options. Whether I’m shopping for an apartment or looking for a job, I always remember this problem, which reminds me not to grab the first deal that comes my way.

Mathematically, I try to find variations of the problem that are closer to real life than the classical version. Here’s one of the ideas I had: you can always delay hiring a secretary until you have interviewed several candidates. You can’t wait too long, as that good secretary you interviewed two weeks ago might have already found a job. And of course the king has a small window of time in which he can run out of the castle and persuade a suitor to come back before he saddles up his horse and rides away.

To make the problem mathematical we should fix the window size as an integer w. When you are interviewing the k-th suitor, you are allowed to go w − 1 suitors back. In other words, the latest you can pick the current suitor is after interviewing w − 1 more people. I call this problem: The Secretary Problem with a Sliding Window.

It is easy to extrapolate the standard strategy to the sliding window problem. There is no reason to pick a suitor who is not the best the princess have seen so far. In addition, if she sees the best person, it is better to wait for the last moment to pick him in case someone better appears. So the strategy should be to skip several people at the beginning and then to pick the best suitor at the last moment he is available.

The difficult part after that is to actually calculate the probabilities and find the stopping point. So I suggested this project to RSI 2015. The project was assigned to Abijith Krishnan under the direction of Dr. Shan-Yuan Ho. Abijith is a brilliant and hard-working student. Not only did he (with the help from his mentor) write a formula for the stopping point and winning probabilities during the short length of RSI, he also resolved the case when the goal is to pick one candidate out of the best two.

If you are interested to see what other RSI students did this year, the abstracts are posted here.