Tanya Khovanova's Math Blog

My STEP students invented a coin-flipping game that doesn’t require a coin. It is called The No-Flippancy Game.

Alice and Bob choose distinct strings of length n consisting of the letters H (for heads) and T (for tails). The two players alternate selecting the outcome of the next “flip” to add to the sequence by the rule below.

The “flip” rule: Let i < n be the maximal length of a suffix of the sequence of chosen outcomes that coincides with a prefix of the current player’s string. The player then selects the element of their string with index i + 1 as the next term in the sequence.

Alice goes first, and whoever’s string appears first in the sequence of choices wins. In layman terms, the game rules mean that the players are not strategizing, but rather greedily finishing their strings.

Suppose n = 2 and Alice chose HH. If Bob chooses HT, then Bob wins. Alice has to choose H for the first flip. Then Bob chooses T and wins. On the other hand, if Bob chooses TT for his string, the game becomes infinite. On her turn, Alice always chooses H, while on his turn Bob always chooses T. The game outcome is an alternating string HTHTHT… and no one wins.

Suppose n = 4, Alice chooses HHTT, and Bob chooses THHH. The game proceeds as HTHHTHHH, at which point Bob wins.

This game is very interesting. The outcome depends on how Alice’s and Bob’s chosen strings overlap with each other. We wrote a paper about this game, which is available at math.CO arXiv:2006.09588.

The academic year is over and my junior PRIMES STEP group finished their paper about a classification of magic SET squares. A magic SET square is a 3 by 3 square of SET cards such that each row, column, and diagonal is a set. See an example below. The paper is posted at the arXiv:2006.04764.

In addition to classifying the magic SET squares, my students invented the game of SET tic-tac-toe. It is played on nine cards that form a magic SET square. Two players take turns picking a card from the square. The first player who has a set wins.

One might think that this game is the same as tic-tac-toe, as a player wins as soon at they have cards from the same row, column, or diagonal. But if you build a magic SET square, you might notices that each magic SET square contains 12 sets. In addition to rows, columns, and diagonals, there are sets that form broken diagonals. The picture below shows all the sets in a magic SET square.

There are more ways to win in this game than in a regular tic-tac-toe game. My students proved that ties are impossible in this game. They also showed, that, if played correctly, the first player always wins.

Suppose we want to pack a unit square with non-overlapping rectangles that have sides parallel to the axes. The catch is that the lower left corners of all the rectangles are given. By the way, such rectangles are called anchored. Now, given some points in the unit square, aka the lower left corners, we want to find anchored rectangles with the maximum total area.

When the given points are close to the right upper corner of the square, the total area is small. When a single point is in the bottom left corner of the square, we can cover the whole square. The problem becomes more interesting if we add one extra assumption: one of the given points has to be the bottom left corner of the square. In the 1960’s, it was conjectured by Allen Freedman that any set of points has an anchored rectangle packing with the area of at least one half. The problem is quite resistant. In 2011, Dumitrescu and Tóth showed that every set of points has a packing of area at least 0.09, which was the first constant bound found, and is the best bound currently known.

I gave this problem to my PRIMES student Vincent Bian. He wrote a paper, Special Configurations in Anchored Rectangle Packings, that is now available at the arxiv. When you look at this problem you see that the number of ways to pack depends on the relative coordinates of the points. That means you can view the points as a permutation. Vincent showed that the conjecture is true for several different configurations of points: increasing, decreasing, mountain, split layer, cliff, and sparse decreasing permutations.

An increasing permutation is easy. There are two natural ways to pack the rectangles. One way, when rectangles are horizontal and each rectangle reaches to the right side of the square (see picture above). Another way, when rectangles are vertical. When you take the union of both cases, the square is completely covered, which means at least one of the cases covers at least half of the square. The worst case scenario, that is, the case when the maximum possible area is the smallest is when your points are placed equidistantly on the diagonal.

Other cases are more difficult. For example, Vincent showed that for a decreasing permutation with n points, the worst case scenario is when the points are arranged equidistantly on a hyperbola xy = (1-1/n)ⁿ. The picture shows the configuration for 15 points. The total area is more than one half.

Here is a logic puzzle.

Puzzle. You are visiting an island where all people know each other. The islanders are of two types: truth-tellers who always tell the truth and liars who always lie. You meet three islanders—Alice, Bob, and Charlie—and ask each of them, “Of the two other islanders here, how many are truth-tellers?” Alice replies, “Zero.” Bob replies, “One.” What will Charlie’s reply be?

The solution proceeds as follows. Suppose Alice is a truth-teller. Then Bob and Charlie are liars. In this situation Bob’s statement is true, which is a contradiction. Hence, Alice is a liar. It follows, that there is at least one truth-teller between Bob and Charlie. Suppose Bob is a liar. Then the statement that there is one truth-teller between Alice and Charlie is wrong. It follows that Charlie is a liar. We have a contradiction again. Thus, Alice is a liar and Bob is a truth-teller. From Bob’s statement, we know that Charlie must be a truth-teller. That means, Charlie says “One.”

But here is another solution suggested by my students that uses meta considerations. A truth-teller has only one possibility for the answer, while a liar can choose between any numbers that are not true. Even if we assume that the answer is only one of three numbers—0, 1, or 2—then the liar still has two options for the answer. If Charlie is a liar, there can’t be a unique answer to this puzzle. Thus, the puzzle question implies that Charlie is a truth-teller. It follows that Alice must be lying and Bob must be telling the truth. And the answer is the same: Charlie says, “One.”

The beautiful Pascal triangle has been around for many years. Can you say something new about it?

Of course you can. Mathematicians always find new way to look at things. In 2012 RSI student, Kevin Garbe, did some new and cool research related to the triangle. Consider Pascal’s triangle modulo 2, see picture which was copied from a stackexchange discussion.

A consecutive block of m digits in one row of the triangle modulo 2 is called an m-block. If you search the triangle you will find that all possible binary strings of length 2 are m-blocks. Will this trend continue? Yes, you can find any possible string of length 3, but it stops there. The blocks you can find are called accessible blocks. So, which blocks of length 4 are not accessible?

There are only two strings that are not accessible: 1101 and 1011. It is not surprising that they are reflections of each other. Pascal’s triangle respects mirror symmetry and the answer should be symmetric with respect to reflection.

You can’t find these blocks on the picture, but how do we prove that they are not accessible, that is, that you can’t ever find them? The following amazing property of the triangle can help. We call a row odd/even, if it corresponds to binomial coefficients of n choose something, where n is an odd/even number. Every odd row has every digit doubled. Moreover, if we take odd rows and replace every double digit with its single self we get back Pascal’s triangle. Obviously the two strings 1101 and 1011 can’t be parts of odd rows.

What about even rows? The even rows have a similar property: every even-indexed digit is a zero. If you remove these zeros you get back Pascal’s triangle. The two strings 1101 and 1011 can’t be part of even rows. Therefore, they are not accessible.

The next question is to count the number of inaccessible blocks of a given length: a(n). This and much more was done by Kevin Garbe for his RSI 2012 project. (I was the head mentor of the math projects.) His paper is published on the arxiv. The answer to the question can be found by constructing recurrence relations for odd/even rows. It can be shown that a(2r) = 3a(r) + a(r+1) − 6 and a(2r+1) = 3a(r) + 2a(r+1) − 6. As a result the number of inaccessible blocks of length n is n² − n + 2. I wonder if there exists a direct proof of this formula without considering odd and even rows separately.

This RSI result was so pretty that it became a question at our entrance PRIMES test for the year 2013. In the test we changed the word accessible to admissible, so that it would be more difficult for applicants to find the research. Besides, Garbe’s paper wasn’t arxived yet.

The pretty picture above is from the stackexchange, where one of our PRIMES applicants tried to solicit help in solving the test question. What a shame.Share:

The following problem was at a 2016 entrance test for the MIT PRIMES STEP program.

I drew several triangles on a piece of paper. First I showed the paper to Lev and asked him how many triangles there were. Lev said 5 and he was right. Then I showed the paper to Sasha and asked him how many triangles there were. Sasha said 3 and he was right. How many triangles are there on the paper? Explain.

The intended answer was 8: there were 5 triangles on one side of the paper and 3 on the other.

Most of the students didn’t think that the paper might be two-sided, but they came up with other inventive ideas. Below are some of their pictures, and I leave it to you to explain why they work. All the students who submitted these pictures got a full credit for this problem on the test.

Share:

If you are a high-school student who wants to conduct research in mathematics, you should check out the MIT PRIMES program. If you enjoy solving the problems in our entrance test, that’s the first indication that you might want to apply. But to determine if the program is right for you, and you are right for the program, please read the following questions and answers which have been prepared for you by Tanya Khovanova, the PRIMES Head Mentor. (This only addresses applications to PRIMES Math, and only to the research track)

Question: I do not like math competitions. Should I apply?
Answer: Math competitions are completely separate from research in mathematics. If you enjoy thinking about mathematics for long periods of time and are fascinated by our test questions, you should apply.

Question: I am good at math, but I really want to be a doctor. Should I apply?
Answer: No. PRIMES requires a huge time commitment, so math should really be your most significant interest.

Question: I want to get into Harvard, and PRIMES looks good on a resume. Should I apply?
Answer: PRIMES does look good on a resume. But if you are more passionate about, say, climate change than math, what would Harvard’s admission committee see? Our experience in the program is that if math isn’t your top interest, your math student may not be sufficiently impressive to be accepted at Harvard as a math researcher. At the same time, you will not be accepted as the top climate change student as you didn’t invest your time in that. Math research is a hard way to earn points for college. See also, the essay, Thoughts on research by Simon Rubinstein-Salzedo.

Question: My parents want me to apply. Should I apply?
Answer: Your parents will not be accepted to the program. Do not apply if you do not really, really want to.

Question: Your website suggests that I should spend ten hours a week on the PRIMES project. I can only spend five. But I am a genius and faster than other people.
Answer: We already assume that you are a genius and faster than anyone else you know. Five hours a week are not enough for a successful project.

Question: I looked at the past PRIMES projects and nothing excites me as much as my current interest in Pascal’s triangle. I doubt I should apply.
Answer: When you start working on a project, you will learn a lot about it. You will understand why, for example, Cherednik algebras are cool. The excitement comes with knowledge and invested time. Not yet being excited about Cherednik algebras is not a good reason not to apply. Besides a lot of exciting mathematics is done between several different fields.

Question: I really want to do nothing else than study Pascal’s triangle.
Answer: We try to match our projects to students’ interests as much as we can. But we almost never can fulfill a specific request as above. You might get a project related to Young diagrams, which are connected to quantum Pascal’s triangle. If this connection doesn’t excite you, you shouldn’t apply.

Question: I think I will be better positioned for research if I spend five more years studying.
Answer: There is nothing wrong with this approach. For many years the standard was to start research in graduate school. Our program is innovative. At PRIMES we are trying a different model. It may sound scary, but you will learn everything you need to know in order to do your project. If the project is in representation theory, for example, you will only learn what you need—not the whole theory. Our hope is that eventually you will take a course in representation theory and expand your grasp of it and see the bigger picture behind your project. We have a reading track for people like you who reside in Boston area.

Question: I love math, but I am not sure that I want to be a mathematician. Should I apply?
Answer: Many people start loving math early in life and then discover that there are many other things that require a similar kind of brain: computer science, cryptography, finance, and so on. We do not require from our students a commitment to become mathematicians. If you want to try research in math, you should apply. If students decide that they do not want to do research in math after finishing our program, we do not consider that a negative result. One way or another, the experience of PRIMES will help you understand better what you want to do with your life.

Question: I want to get to the International Math Olympiad. I am afraid that the time the research project takes prevents me from preparing for competitions. Should I apply?
Answer: People who are good at Olympiads often have fantastic brain power that helps in research. On the other hand, research requires a different mind set and the transition might be painful. It is possible, but not trivial to succeed in both. It is up to you to decide how you want to spend your time.

Question: I like number theory, but I do not see past PRIMES projects in number theory.
Answer: Doable number theory projects are hard to come by and we have fewer number theory projects than students who want to do number theory. There are many high-school programs that teach number theory including PROMYS and Ross programs. Our applicants like number theory because they were exposed to it. During PRIMES you will be exposed to something else and might like it as much.

Question: I found a local professor to work with on a research project. Should I apply to PRIMES?
Answer: PRIMES requires that you devote 10 hours a week to research for a year. It is unrealistic to do two research projects in parallel. Choose one. Working with someone in person may be better than by Skype at PRIMES. Also, usually our mentors are not professors, but rather graduate students. On the other hand, they are MIT grad students and projects are often suggested by professors. Our program is well structured. We guarantee weekly meetings in the Spring, we give extra help with your paper, and we have a conference. It is up to you to decide.Share:

Why are manhole covers round? The manhole covers are round because the manholes are round. Duh! But the cute mathematical answer is that the round shapes are better than many other shapes because a round cover can’t fall into a round hole. If we assume that the hole is the same shape as the cover but slightly smaller, then it is true that circular covers can’t fall into their holes. But there are many other shapes with this property. They are called the shapes of constant width.

Given the width, the shape with the largest area is not surprisingly a circle. The shape with the smallest area and a given constant width is a Reuleaux Triangle. Here is how to draw a Reuleaux triangle. Draw three points that are equidistant from each other at distance d. Then draw three circles of radius d with the centers at given points. The Reuleaux triangle is the intersection of these three circles.

Can we generalize this to 3d? What would be an analogue of a Reuleaux Triangle in 3d? Of course, it is a Reuleaux Tetrahedron: Take four points at the vertices of a regular tetrahedron; take a sphere at each vertex with the radius equal to the edge of the tetrahedron; intersect the four spheres.

Is this a shape of the constant width? Many people mistakenly think that this is the case. Indeed, if you squeeze the Reuleaux tetrahedron between two planes, one of which touches a vertex and another touches the opposite face of the curvy tetrahedron, then the distance between them is equal to d: the radius of the circle. This might give you the impression that this distance is always d. Not so. If you squeeze the Reuleaux tetrahedron between two planes that touch the opposite curvy edges, the distance between these planes will be slightly more than d. To create a shape of constant width you need to shave off the edges a bit.

Theoretically you can shave the same amount off every edge to get to a surface of constant width. But this is not the cool way to do it. The cool way is to shave a bit more but only from one edge of the pair of opposite edges. You can get two different figures this way: one that has three shaved edges forming a triangle, and the other, where three shaved edges share a vertex. These two bodies are called Meissner bodies and they are conjectured to be shapes of the constant width with the smallest volume.

On the picture I have two copies of a pair of Meissner bodies. The two left ones have three edges that share a vertex shaved off. The very left shape gives a top view of this vertex and the solid next to it has its bottom with holes looking forward. The two shapes on the right show the second Meissner body in two different positions.

I recently discovered a TED-Ed video about manhole covers. It falsely claims that the Reuleaux tetrahedron has constant width. I wrote to TED-Ed, to the author, and posted a comment on the discussion page. There was no reaction. They either should remove the video or have an errata page for it. Knowingly keeping a video with an error that is being viewed by thousands of people is irresponsible.Share:

I am running a PRIMES-STEP program for middle school students, where we try to do research in mathematics. In the fall of 2015 we decided to study the following topic in logic.

Suppose there is an island where the following four types of people live:

• Absolute truth-tellers always tell the truth.
• Partial truth-tellers tell the truth with one exception: if they are guilty, they will say that they are innocent.
• Absolute liars always lie.
• Responsible liars lie with one exception: if they are guilty, they will say that they are guilty.

See if you can solve this simple logic puzzle about people on this island.

It is known that exactly one person stole an expensive painting from an apartment. It is also known that only Alice or Bob could have done it. Here are their statements:
Alice: I am guilty. Bob is a truth-teller.
Bob: I am guilty. Alice stole it. Alice is the same type as me.
Who stole the painting and what types are Alice and Bob?

My students and I discovered a lot of interesting things about these four types of people and wrote a paper: Who Is Guilty?. This paper contains 11 cute logic puzzles designed by each of my 11 students.

I envied my students and decided to create two puzzles of my own. You have already solved the one above, so here is another, more difficult, puzzle:

A bank was robbed and a witness said that there was exactly one person who committed the robbery. Three suspects were apprehended. No one else could have participated in the robbery.
Alice: I am innocent. Bob committed the crime. Bob is a truth-teller.
Bob: I am innocent. Alice is guilty. Carol is a different type than me.
Carol: I am innocent. Alice is guilty.
Who robbed the bank and what types are the suspects?

Share:

I have solved too many puzzles in my life. When I see a new one, my solution is always the intended one. But my students invent other ideas from time to time and teach me to think creatively. For example, I gave them this puzzle:

Two boys wish to cross a river, but there is a single boat that can take only one boy at a time. The boat cannot return on its own; there are no ropes or similar tricks; yet both boys manage to cross the river. How?

Here is what my inventive students came up with:

• There was another person on the other side of the river who brought the boat back.
• There was a bridge.
• The boys can swim.
• They just wanted to cross the river and come back, so they did it in turns.

And here is my standard solution: They started on different sides of the river.

I gave a talk about thinking inside and outside the box at the Gathering for Gardner conference. I mentioned this puzzle and the inventiveness of my students. After the conference a guy approached me with another answer which is now my favorite:

• They wait until the river freezes over and walk to the other side.

Share: