Tanya Khovanova's Math Blog

For students applying to PRIMES, we have a question about their research interests. RSI asks a similar question from their applicants.

I am looking at all the submissions, and this essay will help our applicants to get projects that are well-suited for them.

We, at PRIMES and RSI Math, usually have research projects lined up in advance. That means, we are not creating projects to match applicants’ requests. We match existing projects to students’ backgrounds and interests.

If you are applying to one of these programs, here is my advice.

Don’t be too specific about what you want. Suppose you want to study the symmetries of an icosahedron. This request is too narrow: there is a high probability we do not have such a project. How will we match you to a project? Our hope, in this case, is to find clues in your essay. For example, we might discover that you heard a fascinating lecture on icosahedron’s symmetries, which is why you requested the topic. In this case, we assume that another fascinating lecture on a different topic might also excite you, and you will be matched with a random project. But if your description is broader, say, if you write that you like group theory or geometry, your match won’t be as random.

Specify things you do not want. Given our project distribution, you might not get a project in the area that is your first or even your second choice. On the other hand, if you write to us that you hate geometry, it is very easy to find a project without a geometric component. If there is something you definitely do not want, it is advantageous for you to mention it. Be precise about your advanced knowledge. For example, linear algebra is one of the most powerful tools in mathematics. Not surprisingly, we often have projects that require a serious background in linear algebra and specifically look for students who know it. Unfortunately, we often receive inadequate descriptions of students’ backgrounds. Even if you took a linear algebra course, it might be useful to mention which book you used and how many chapters you covered. This also applies to other advanced topics. An applicant might say they are proficient in cohomologies after half-listening to one half-hour lecture on the topic. This is not proficiency; it only indicates interest. If you claim advanced knowledge, specify the scope. The best way to start is by listing the books you have attempted to read. For each book, describe which chapters you only scanned, which chapters you read and understood, and for which chapters you solved all of the exercises.

Add more information if your first choice is number theory. Almost every year, we have several students requesting number theory. This might be explained by the successes of the Ross and PROMYS summer programs. The graduates from these programs love number theory and have a good number theory background. However, modern number theory is very advanced, and we seldom have these types of projects. So, if number theory is your top choice, there are two things you can do. First, mention your second choice. Second, specify what you like about number theory. For example, if you are into the more abstract parts of number theory, another abstract project might be a good fit.

Describe your priorities in broader terms. It is beneficial for every starting mathematician to figure out the area they like by asking themselves broader questions. If you know the answers to the questions below, it is helpful to write them on the application form.

• Do you love or hate abstractions?
• Do you prefer discreet or continuous problems?
• Is the real-life impact or inner beauty of your project more important to you?
• Do you enjoy having a visual component to your project?
• Do you like when problems involve programs and calculations?

If you follow my advice, you might get a project that matches your tastes better. Not only that: figuring out the answers to these questions will help you build the life you love.

I recently posted a cute Shapovalov’s puzzle about gnomes. Here is another easier gnome puzzle, also by Alexander Shapovalov.

Puzzle. All gnomes are knights or knaves: knights always tell the truth, and knaves always lie. There is a gnome on every cell of a 4 by 4 chessboard. It is known that both knights and knaves are present in this group. Every gnome states, “Among my neighbors, the number of knaves is the same as the number of knights”. How many knaves are there, if by neighbors they mean orthogonally adjacent gnomes?

The next gnome puzzle has a different author, Alexander Gribalko. Gnomes in this puzzle are not knights or knaves but rather friendly and polite beings.

Puzzle. Nine gnomes repeated the following procedure three times. They arranged themselves on a 3 by 3 chessboard with one gnome per cell and greeted all their orthogonal neighbors. Prove that not all pairs of gnomes greeted each other.

Here is another lovely problem from a prolific problem writer, Alexander Shapovalov.

Problem. Every cell of a 7 by 7 chessboard has a gnome standing on it. For every pair of gnomes whose cells share an edge, their beards’ lengths differ by no more than 1 inch. Now, we take these gnomes and sit them around a table. Prove that we can do so in a way that any two gnomes sitting next to each other have their beards’ lengths differ by no more than 1 inch.

A standard chessboard is 8 by 8. Why would this problem have a 7 by 7 board? Let’s see.

For even-sized boards, the problem is easy. I will explain why, but first, let me construct a graph related to a board, in this case, any board.

Each cell is a vertex, and two vertices are connected by an edge if the corresponding cells are orthogonal neighbors (share an edge) on the board. A cycle that goes through a graph and visits every vertex exactly once is called a Hamiltonian cycle. A Hamiltonian cycle is a potential way to sit the gnomes around the table and solve the problem. When we sit the gnomes in a circle following a Hamiltonian cycle, two neighbors at the table are also neighbors on the board, and so they have their beards’ lengths differ by no more than 1 inch.

The problem is easy for even-sized boards because it is easy to draw a Hamiltonian cycle on them. An odd-sized chessboard can’t have a Hamiltonian cycle. To prove this, let me color the board in a checkerboard manner. Then, cells that share an edge are different colors. And you can’t make a cycle through the board, where you switch colors at each step, but the total number of steps is odd.

It follows that for odd-sized boards, it is impossible to solve the problem by just connecting neighboring cells on the board. There should be another way. Can you find it?

I want to discuss a problem from a test I gave recently.

Problem. My dog, Fudge, likes books. He brought two books to his corner in the morning and three more books in the evening. How many books will he read tonight?

As I expected, many students didn’t pay attention and just summed up the two numbers in the problem and gave five as the answer. Here are three answers that I especially liked.

Answer 1. Zero, because most dogs can’t read.

This cautious student added most to be on the safe side.

Answer 2. You cannot tell how many books he will read. Just because he brings books to his corner doesn’t mean he will read them.

The second answer demonstrates great logical thinking, were Fudge a human. But the third answer made me laugh.

Answer 3. Three. If he brought three more books to his corner in the evening, it means he finished the two from that morning, so there are three books left for him to read.

Thinking about genders, we used to have only two options: male and female. Now we have more. I have a lot of young acquaintances who are non-binary. So I started to rethink my gender identity.

I was a typical girl: at least, I thought I was. I hated playing with boring dolls. I preferred cars, or even better, construction sets and board games. In second grade, I wanted to be a ballerina but later fell in love with Sherlock Holmes. My dreams switched to becoming a detective or a spy. In fifth grade, I signed up for rifle-shooting training. That same year, my school forced me to compete in an orienteering event, and I won.

Orienteering became my favorite sport, and I did it for many years. I was really good with maps. I would go to a competition, leisurely walk my course and win. Other kids were running around like crazy, but I always knew where to go and was overall faster than them. With time, other kids learned to read maps better, but I myself never learned to run faster. So I stopped winning, but I enjoyed the sport anyway.

It goes without saying: I loved math. Solving math problems was the best entertainment ever.

Later, to my surprise, I discovered that most girls liked shopping and wasted a lot of time on make-up. Not many girls were even interested in math. I actually liked that. I started having crushes on boys since second grade and enjoyed being the only girl in math clubs, having all these nerds to myself.

I grew up in Soviet Russia. While growing up, I wasn’t bombarded with gender stereotypes. My first eye-opening experience was when I was 17 years old. My long-time boyfriend knew that I liked mathematics, and this was okay. But when I told him that I planned to go to college to study mathematics, he didn’t approve. I broke up with him on the spot.

My mom used to tell me that most men do not like brainy women. My reply was that there are more men who like brainy women than brainy women. I got a new boyfriend the day after my breakup.

My gender identity didn’t bother me much in Russia. What bothered me was the Russian tradition for both spouses to work, but the house chores and child-rearing duties fell only on women. I read somewhere that, on average, in Russia, women worked for 4 hours a day more than men. Life was unfair to women but not to their self-esteems.

As I said, I grew up thinking I was a typical girl until I came to the US. This happened 30 years ago, and I was 30 at the time. In the US, I got bombarded with gender stereotypes: they made me feel inadequate and doubt my femininity. Just for reference: by that time, I was in my third marriage breastfeeding my second child. Still, according to those stereotypes, I was not a real woman.

For some time, I wondered what was wrong with me. Then, I was elated to find a book called Brain Sex: The Real Difference Between Men and Women by Anne Moir and David Jessel. (This was many years ago.) Among other things, this book talks about the differences between men and women with respect to the brain. According to the book, men are better on average at abstract thinking and spatial visions, aka math and maps. Women, on the other hand, are better at connecting with people and have higher social intelligence. Boys are less interested in games related to storytelling, aka dolls, preferring more concrete activities. And so on.

The book also describes situations in which girls don’t fit the paradigm. The authors attribute this variation to the mother’s hormones during pregnancy. I found myself described perfectly in the section titled “girls who have been exposed to male hormones in the womb.” I am pretty sure that my mom didn’t take any hormone supplements while pregnant with me back in Soviet Russia. On the other hand, the description in the book was spot-on.

This book classifies me as “a male brain in a female body.”

I was glad to find myself after a period of self-doubt. I was glad that I wasn’t alone and even fit into a special category with a name.

Several years later, I met Sue Katz, a writer who also has a blog Sue Katz: Consenting Adult. She made me realize how ridiculous the whole story was: I was pressured by gender stereotypes to feel bad about myself. Then I was grateful for a book based on those same stereotypes, only because it described women like me and gave me permission to exist. I liked the book because I accepted those stereotypes in the first place. If there were no stereotypes, there wouldn’t be any problems at all.

Why can’t I just be me?

Over the past few years, I have become happier than I have ever been. I do not care what society thinks about my gender. I am no longer ashamed of not feeling 100 percent female.

I like that people in the modern world embrace the idea of individuals being themselves. For example, my daughter-in-law, Robin Dahan, designed a whole line, You-Be-You, for her company, Dash of Pep.

Am I non-binary? I do not know and do not care. I am just me, proudly wearing my You-Be-You socks.

Assume that we have n men and n women, all of whom want to get married. They rank each other without ties. After that, we can match them into n pairs for marriage. The matching is called stable if there are no rogue couples. A rogue couple is defined as a man and a woman who prefer each other over their assigned future spouses.

A famous theorem says that, whatever all the rankings are, a stable matching always exists. But how good could a stable matching be? There is a way to assign a quality score to a matching, called the egalitarian cost. The egalitarian cost of any matching is the sum of the rankings that each person gave their assigned partner. The best potential outcome is when all people are matched with their first choices. This corresponds to the minimum egalitarian cost of 2n. But what is the maximum egalitarian cost of a stable matching? I couldn’t find it in the literature, so I proved that it is n(n+1).

Proof. It is easy to see that the egalitarian cost of n(n+1) is achievable. For example, if all men gave an identical ranking to the women, and vice versa, the matching algorithm will end up with couples having mutual rankings (j,j) for different values of j. Another example is a Latin preference profile. Each woman ranks a man n+1−x whenever he ranks her x. In this case, every potential couple’s mutual rankings sum to n+1. Thus, any matching for such rankings ends up with the egalitarian cost of n(n+1).

The next step is to prove that the egalitarian cost can’t be greater. Suppose the cost of a stable matching is C and is greater than n(n+1). Then, for every person, we count the number of people who are better (ranked smaller) than their assigned partner and sum these numbers over all the people. The result must be C−2n, which is the number of pairs of people of opposite genders such that the first person prefers the second one over their assigned partner. Moreover, the result is greater than n(n−1).

The total number of possible couples is n². Thus, the number of unrealized potential couples is n(n−1). We can conclude that we counted one of these unrealized couples twice. In such a couple, two people prefer each other over their assigned partners. Thus, they form a rogue couple, contradicting our assumption that the matching is stable.

Here is an old goodie.

Puzzle. A criminal is sentenced to death. He is offered the last word. He is allowed to make one statement. If the statement is true, the criminal will be electrocuted. If the statement is false, he will be hanged. Can you find a good piece of advice for this man?

The standard answer to this puzzle is for the criminal to say, “I will be hanged.” This creates a paradox. If he is hanged, the statement is true, and he should be electrocuted. If he is electrocuted, the statement is false, and he should be hanged.

Thinking about it, any paradox works. If the man says, “This statement is false,” then the type of punishment he gets can’t be determined.

Thinking about it some more, asking a question instead of making a statement will confuse his executioners all the same.

One of my students advised the criminal to stay silent. This was not my favorite solution, as staying silent requires some concentration. My favorite solution was the statement, “It will rain exactly a thousand years from now.” This way, the criminal can relax, at least for a thousand years.

Today I discuss ideas for solving the puzzle I posted previously in my blog: A Scooter Riddle.

Riddle. Alice, Bob, and Charlie are at Alice’s house. They are going to Bob’s house, which is 33 miles away. They have a 2-seat scooter that goes 25 miles per hour with 1 rider, or 20 miles per hour with 2 riders. Each of the 3 friends has a walking pace of 5 miles per hour. What is the fastest time that all three of them can end up at Bob’s house?

Let’s start.

• The scooter and the three people should always be on the move. Moreover, whenever the scooter moves towards Bob’s house, it should carry two people, and only the driver should be on the scooter whenever it is going back.
• We do not care about each individual’s path: whenever people meet at the same place at the same time, we can swap them. Therefore, we can assume that the scooter’s driver is the same person at all times.
• Thinking about it, we can ignore the scooter’s driver and assume that the scooter is self-driving, and there are only two people, Alice and Bob, who need to get to Bob’s house.
• If Alice and Bob arrive at Bob’s house at different times, there is room for improvement: the fastest person should have used the scooter less and walked more, allowing the other person more use of the scooter. Hence, we can assume that they arrive at Bob’s house simultaneously.
• Without loss of generality, we can assume that Alice starts on the scooter first.
• So the scooter should carry Alice for some time, drop her off, come back for Bob, then drop him off, come back for Alice, and so on. Without loss of generality, we can combine all scooter trips by the same person into one ride.
• Thus, the plan is the following. The scooter drives Alice for x hours, drops her off, and she finishes on foot. Meanwhile, Bob starts on foot. The scooter goes back after dropping off Alice, picks up Bob, and drives him x hours the rest of the way.

Now this is just algebra. Each person covers 20x miles on the scooter and 33 − 20x miles on foot. The walking takes 33/5 − 4x hours. Thus the total trip for each person takes 33/5 − 3x hours.

Now we calculate what the scooter does. The scooter covers 20x miles with Alice and the same number of miles with Bob. It covers 40x − 33 miles alone. Thus the scooter spends 2x + (40x − 33)/25 hours in transit. The two times must be the same. So we have an equation: 6.6 − 3x = 2x + 1.6x − 1.32. Thus, x = 1.2, and the answer to the puzzle is 3 hours.

If you can figure out my number without the Internet, call me.

• The number of letters in the first name of Anna Karenina’s love.
• The number of times the word nevermore appears in the famous poem, subtracted from the month when the events took place.
• The only number in the title of a Bergman movie.
• The number of vowels in the original and more historically meaningful name for the sorcerer’s stone in Harry Potter books.
• The number of vertices of the other geometric shape in “Girl on a Ball”.
• The cube root of the age mentioned in one of the earliest Beatles songs.
• The number corresponding to the lexicographically first string representing an integer in English.
• The first digit of the age at which Pushkin and Mozart died.
• The smallest of two primes such that their sum and difference are also prime.
• The only triangular number that is also prime.

(Just in case: this is a joke and not my actual phone number.)

This is my second crocheting project to help finance our new program, Yulia’s Dream, in honor of Yulia Zdanovska, a young Ukrainian math talent killed in the war.

I made four Whitehead links in the colors of the Ukrainian flag. You can read about my other crocheting project in my previous post: Hyperbolic Surfaces for Ukraine.

Fun trivia about the Whitehead links.

• Why are these links so famous? They are the simplest non-trivial links with the linking number zero.
• What’s the linking number? The linking number is an invariant of a link. If two loops are not linked (they are called an unlink), their linking number is zero. If they are linked, then their linking number is usually not zero. Here the loops are linked, but the linking number is nevertheless zero. Thus, the linking number can’t differentiate this link from an unlink. To explain how to calculate the linking number, I need to explain another simpler invariant: the crossing number.
• What’s the crossing number? The crossing number is the smallest number of crossings when projecting the link on a plane. The top two pictures have 6 crossings, and the bottom two pictures have 5. The top two pictures emphasize the symmetry of the link, and the bottom two pictures have the smallest possible number of crossings for the Whitehead link. So the crossing number of the Whitehead link is 5.
• Can you now explain how to calculate the linking number? One way to calculate the linking number is to choose directions for the blue and yellow loops and select the crossings where the blue is on top. After that, following the chosen direction of the blue loop, at each crossing with the yellow loop, check the latter’s direction. If the direction is from right to left, count it with a plus and, otherwise, with a minus. The total is the linking number. In the case of the Whitehead link, it is zero.
• Is there a more elegant explanation for why the Whitehead link has the linking number zero? Yes. The linking number only looks at the crossings of two different strands and ignores self-crossings. If you look at the two bottom pictures, there is one self-crossing of the blue loop. Now imagine you change the crossing by moving the top blue strand underneath. After such a transformation, the crossing number doesn’t change, but the loops become unlinked. Thus, the linking number of the Whitehead link must be zero.