Tanya Khovanova's Math Blog

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?