Tanya Khovanova's Math Blog

* * *

—Mike, here are 10 chocolates. Give half of them to your brother.
—OK. I’ll give him three chocolates.
—You can’t count?
—I can, but he can’t.

* * *

—How is your progress?
—50%.
—Done or left to do?

* * *

—Q: What did Al Gore play on his guitar?
—A: An Algorithm.

* * *

I put my root beer in a square glass. Now it’s just beer.

* * *

—Q: Why shouldn’t you argue with a decimal?
—A: Decimals always have a point.

* * *

—I am cold.
—Go stay in the corner. It’s 90 degrees.

* * *

Arithmetic is the art of counting up to twenty without taking off your shoes.

* * *

I bought a book online “How to implement an Internet scam.” Somehow, though, it’s been a while, and I still haven’t received it.

* * *

Sex is a pathetic thrill for losers who are not able to take a triple integral.

* * *

Paradox: Less money, more need to count it.

How many letters are there in the correct answer to this question?

What is the answer to this question?

In my paper Nim Fractals written with Joshua Xiong we discovered an interesting graph structure on P-positions of impartial combinatorial games. P-positions are vertices of the graph and two vertices are connected if they are consecutive P-positions in an optimal longest game.

A longest game of Nim is played when exactly one token is removed in each turn. So in Nim two P-positions are connected if it is possible to get from one of them to the other by removing two tokens.

In the paper we discussed the evolution graph of Nim with three piles. The graph has the same structure as three branches of the Ulam-Warburton automaton.

For completeness, I would like to describe the evolution graph of the 2-pile Nim. The P-positions in a 2-pile Nim are pairs (n,n), for any integer n. Two positions (n,n) and (m,m) are connected if and only if m and n differ by 1. The first picture represents this graph.

The Wythoff’s game is more interesting. There are two piles of tokens. In one move a player can take any number of tokens from one pile or the same number of tokens from both piles.

The P-positions (n,m) such that n ≤ m start as: (0,0), (1,2), (3,5), (4,7), (6,10) and so on. They can be enumerated using φ: the golden ratio. Namely, n_k = ⌊kφ⌋ and m_k = ⌊kφ²⌋ = n_k + k, where k ≥ 0.

In a longest Wythoff’s game the difference between the coordinates decreases by 1. That is, it takes a maximum of 2k steps to end an optimal game starting from position (n_k,m_k). The picture shows the evolution graph.

The interesting part of the picture is the crossover between two “lines”. From positions with large coordinates like (6,10) with a difference of 4 you can get to only one position with a difference of 3: (4,7) and not (7,4). But from position (3,5) with a difference of 2 you can get to both positions with a difference of 1: (1,2) and (2,1).

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.