Tanya Khovanova's Math Blog

I want the world to be a better place. My contribution is teaching people to think. People who think make better decisions, whether they want to buy a house or vote for a president.

When I started my blog, I posted a lot of puzzles. I was passionate about not posting solutions. I do want people to think, not just consume puzzles. Regrettably, I feel a great push to post solutions. My readers ask about the answers, because they are accustomed to the other websites providing them.

I remember I once bought a metal brainteaser that needed untangling. The solution wasn’t included. Instead, there was a postcard that I needed to sign and send to get a solution. The text that needed my signature was, “I am an idiot. I can’t solve this puzzle.” I struggled with the puzzle for a while, but there was no way I would have signed such a postcard, so I solved it. In a long run I am glad that the brainteaser didn’t provide a solution.

That was a long time ago. Now I can just go on YouTube, where people post solutions to all possible puzzles.

I am not the only one who tries to encourage people to solve puzzles for themselves. Many Internet puzzle pages do not have solutions on the same page as the puzzle. They have a link to a solution. Although it is easy to access the solution, this separation between the puzzle and its solution is an encouragement to think first.

But the times are changing. My biggest newest disappointment is TED-Ed. They have videos with all my favorite puzzles, where you do not need to click to get to the solution. You need to click to STOP the solution from being fed to you. Their video Can you solve the prisoner hat riddle? uses my favorite hat puzzle. (To my knowledge, this puzzle first appeared at the 23-rd All-Russian Mathematical Olympiad in 1997.) Here is the standard version that I like:

A sultan decides to give 100 of his sages a test. He has the sages stand in line, one behind the other, so that the last person in line can see everyone else. The sultan puts either a black or a white hat on each sage. The sages can only see the colors of the hats on all the people in front of them. Then, in any order they want, each sage guesses the color of the hat on his own head. Each hears all previously made guesses, but other than that, the sages cannot speak. Each person who guesses the color wrong will have his head chopped off. The ones who guess correctly go free. The rules of the test are given to them one day before the test, at which point they have a chance to agree on a strategy that will minimize the number of people who die during this test. What should that strategy be?

The video is beautifully done, but sadly the puzzle is dumbed down in two ways. First, they explicitly say that it is possible for all but one person to guess the color and second, that people should start talking from the back of the line. I remember in the past I would give this puzzle to my students and they would initially estimate that half of the people would die. Their eyes would light up when they realized that it’s possible to save way more than half the people. They have another aha! moment when they discover that the sages should start talking from the back to the front. This way each person sees or hears everyone else before announcing their own color. Finally, my students would think about parity, and voilà, they would solve the puzzle.

In the simplified adapted video, there are no longer any discoveries. There is no joy. People consume the solution, without realizing why this puzzle is beautiful and counterintuitive.

Nowadays, I come to class and give a puzzle, but everyone has already heard the puzzle with its solution. How can I train my students to think?

One of my jobs is giving linear algebra recitations at MIT. The most unpleasant aspect of it is dealing with late homework. Students attempt to submit their homework late for lots of different reasons: a sick parent needing help, stress, a performance at Carnegie Hall, a broken printer, flu, and so on. How do I decide which excuse is sufficient, and which is not? I do not want to be a judge! Moreover, my assumption is that people tell the truth. In the case of linear algebra homework, this assumption is unwise. As soon as students discover that I trust everyone, there’s a sharp increase in the number of sick parents and broken printers. So I have the choice of being either a naive idiot or a suspicious cynic. I do not like either role.

Our linear algebra course often adopts a brilliant approach: We announce that late homework is not allowed for any reason. To compensate for emergencies, we drop everyone’s lowest score. That is, we allow the students to skip one homework out of ten. They are free to use this option for oversleeping the 4 pm deadline. If all their printers work properly and they do not get so sick that they have to skip their homework, they can forgo the last homework. Happily, this relieves me from being a judge.

Or does it? Unfortunately, this policy doesn’t completely resolve the problem. Some students continue trying to push their late homework on me, despite the rules. In order to be fair to other students and to follow the rules, I reject all late homework. The students who badger me nonetheless waste my time and drain my emotions. This is very unpleasant.

From the point of view of those students, such behavior makes sense. They have nothing to lose and they might get some points. There is no way to punish a person who tries to hand in homework late and from time to time they stumble onto a soft instructor who accepts the homework against the official rules. Because such behavior is occasionally rewarded, they continue doing it. I believe that wrong behavior shouldn’t be rewarded. As a responsible adult, I think it is my duty to counteract the rewards of this behavior. But I do not know how.

What should I do? Maybe I should…

1. Persuade our course leader, or MIT in general, to introduce a punishment for trying to hand in late homework. We might, for example, subtract points from their final score.
2. Promote the value of honorably following the rules through discussions with the students.
3. Growl at any student who submits their homework late.
4. Explain to them what other people think about them, when they do not follow the rules.

Maybe I should just do number 4 right now and explain what I feel. A student who persists in handing in homework late feels to me that s/he is entitled and is better than everyone else, and shows that s/he doesn’t care about the rules and honor. Again, this wastes my time, puts me in a disagreeable position, and reduces my respect for that student.

Earlier I suggested that students don’t have anything to lose by such behavior, but in fact, they do pay a price, even though they may not understand that.

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 explained to my AMSA students the idea of meta-solving multiple choice. Sometimes by looking at the choices without knowing what the problem is, it is possible to guess the correct answer. Suppose your choices are 2k, 2, 2/k, 10k, −2k. What is the most probable answer? There are several ideas to consider.

• A problem designer considers different potential mistakes and tries to include the answers corresponding to most common mistakes. That means the answers corresponding to the mistakes are variations of the right answer. Thus, the right answer is a common theme in all the answers.
• A problem designer tries not to allow the students to bypass the solution. So if only one of the choices is negative and the answer is negative, the students do not need to calculate the exact answer, they just need to see that it’s negative. That means the right answer cannot be the odd one out.

Both these considerations suggest a rule of thumb: the answers that are odd ones out are probably wrong. In the given example (2k, 2, 2/k, 10k, —2k), the second choice is an odd one out because it’s the only one that does not contain k. The third choice is an odd one out because it’s the only one in which we divide by k. The fourth choice is an odd one out because it’s the only one with 10 instead of 2. The last one is an odd one out because of the minus sign. Thus the most probable answer is 2k.

So I explained these ideas to my students and gave them a quiz, in which I took the 2003 AMC 10A test, but only gave them the choices without the problems. I was hoping they would do better than randomly guessing.

Luckily for me, I have six classes in a row doing the same thing, so I can make adjustments as I go along. Looking at the results of the first two groups of students, I discovered that they were worse than random. What was going on?

I took a closer look, and what do you know? Nobody marked the first or the last choice. The answers are in an increasing order, so the first is the smallest and the last is the largest. So these two numbers are odd ones out, in a way.

It is a good idea to consider 189 as an odd one out in the list 1, 2, 4, 5, 189. In many other cases, the fact that the number is either the smallest or largest is insufficient reason to consider it as the odd one out. For example, there is no reason to consider 1 to be an odd one out in the list 1, 2, 3, 4, 5. And the designers of AMC are good: a lot of problems have an arithmetic progression as a list of choices, where none of the numbers are obviously odd ones out.

To correct the situation of worse than random results, I discussed it with my students in my next classes. Problem designers cannot have a tradition in which the first answer is never the correct answer. If such a tradition existed, and people knew about it, that knowledge would help them guess. So the first answer should be correct approximately five times, which is a fifth of the total number of questions (25).

And we came up with a strategy. Use the odd one out method except for arithmetic progressions. Then add the choices to balance out the total number of the first answers, the second answers, etc.

That method worked. In my next four classes my students were better than random.

My post with Kvantik’s 2012 problems for middle school was a success. So I scanned the 2013 issues and found 7 more problems that I liked. Here are two cute problems I’ve seen before:

Problem 1. In the equation 30 − 33 = 3 move one digit to make it correct.

Problem 2. A patient got two pills for his headache and two pills for his cough. He was supposed to use one of each type of pill today and do the same tomorrow. The pills all looked the same. By mistake, the patient mixed up the pills. How should he use them so that he follows the prescription exactly?

Now logic and information-theoretical problems:

Problem 3. One strange boy always tells the truth on Wednesdays and Fridays and always lies on Tuesday. On other days of the week he can lie or tell the truth. He was asked his name seven days in a row. The first six answers in order are Eugene, Boris, Vasiliy, Vasiliy, Pete, Boris. What was his answer on the seventh day?

Problem 4. Ten people are suspected of a crime. It is known that two of them are guilty and eight are innocent. Suspects are shown to a psychic in groups of three. If there is a guilty person in the group the psychic points him out. If there are two guilty people in the group, the psychic points to one of them. If all of them are innocent, the psychic points at one of the three.

1. How would you find at least one guilty person in four séances?
2. How would you find both criminals in six séances?

Problem 5. There are four balloons: red, blue, green and black. Some of the balloons might be magical. There is also a detector box that can say how many balloons out of the ones put inside are magical. How can you find all the magical balloons using the detector box not more than three times?

I conclude with two miscellaneous problems.

Problem 6. Three runners started their loops at the same time at the same place on the same track. After some time they ended at their starting point together. The fastest runner passed the slowest runner 23 times. Assuming each runner has a constant speed, how many times was one runner passed by another runner in total?

Problem 7. Given a point inside a circular disk, cut the disk into two parts so that you can put them back together into a new disk such that the given point is the center.

Kvant was a very popular science magazine in Soviet Russia. It was targeted to high-school children and I was a subscriber. Recently I discovered that a new magazine appeared in Russia. It is called Kvantik, which means Little Kvant. It is a science magazine for middle-school children. The previous years’ archives are available online in Russian. I looked at 2012, the first publication year, and loved it. Here is the list of the math puzzles that caught my attention.

The first three problems are well known, but I still like them.

Problem 1. There are 6 glasses on the table in a row. The first three are empty, and the last three are filled with water. How can you make it so that the empty and full glasses alternate, if you are allowed to touch only one of the glasses? (You can’t push one glass with another.)

Problem 2. If it is raining at midnight, with what probability will there be sunshine in 144 hours?

Problem 3. How can you fill a cylindrical pan exactly half-full of water?

I like logic puzzles, and the next two seem especially cute. I like the Parrot character who repeats the previous answer: very appropriate.

Problem 4. The Jackal always lies; the Lion always tells the truth. The Parrot repeats the previous answer—unless he is the first to answer, in which case he babbles randomly. The Giraffe replies truthfully, but to the previous question directed to him—his first answer he chooses randomly.
The Wise Hedgehog in the fog stumbled upon the Jackal, the Lion, the Parrot, and the Giraffe, although the fog prevented him from seeing them clearly. He decided to figure out the order in which they were standing. After he asked everyone in order, “Are you the Jackal?” he was only able to figure out where the Giraffe was. After that he asked everyone, “Are you the Giraffe?” in the same order, and figured out where the Jackal was. But he still didn’t have the full picture. He started the next round of questions, asking everyone, “Are you the Parrot?” After the first one answered “Yes”, the Hedgehog understood the order. What is the order?

Problem 5. There are 12 cards with the statements “There is exactly one false statement to the left of me,” “There are exactly two false statements to the left of me.” …, “There are 12 false statements to the left of me.” Pete put the cards in a row from left to right in some order. What is the largest number of statements that might be true?

The next three problems are a mixture of puzzles.

Problem 6. Olga Smirnov has exactly one brother, Mikhail, and one sister, Sveta. How many children are there in the Smirnov family?

Problem 7. Every next digit of number N is strictly greater than the previous one. What is the sum of the digits of 9N?

Problem 8. Nine gnomes stood in the cells of a three-by-three square. The gnomes who were in neighboring cells greeted each other. Then they re-arranged themselves in the square, and greeted each other again. They did this one more time. Prove that there is at least one pair of gnomes who didn’t get a chance to greet each other.

I was afraid of my advisor Israel Gelfand. He used to place unrealistic demands on me. After each seminar he would ask his students to prove by the next week any open problems mentioned by the speaker. So I got used to ignoring his requests.

He also had an idea that it is good to learn mathematics through problem solving. So he asked different mathematicians to compile a list of math problems that are important for undergraduate students to think through and solve by themselves. I still have several lists of these problems.

Here I would like to post the list by Andrei Zelevinsky. This is my favorite list, partially because it is the shortest one. Andrei was a combinatorialist, and it is surprising that the problems he chose are not combinatorics problems at all. This list was compiled many years ago, but I think it is still useful, just keep in mind that by calculating, he meant calculating by hand.

Problem 1. Let G be a finite group of order |G|. Let H be its subgroup, such that the index (G:H) is the smallest prime factor of |G|. Prove that H is a normal subgroup.

Problem 2. Consider a procedure: Given a polygon in a plane, the next polygon is formed by the centers of its edges. Prove that if we start with a polygon and perform the procedure infinitely many times, the resulting polygon will converge to a point. In the next variation, instead of using the centers of edges to construct the next polygon, use the centers of gravity of k consecutive vertices.

Problem 3. Find numbers a_n such that 1 + 1/2 + 1/3 + … + 1/k = ln k + γ + a₁/k + … + a_n/kⁿ + …

Problem 4. Let x₁ not equal to zero, and x_k = sin x_k-1. Find the asymptotic behavior of x_k.

Problem 5. Calculate the integral from 0 to 1 of x^−x over x with the precision 0.001.

I regret that I ignored Gelfand’s request and didn’t even try to solve these problems back then.

I didn’t have any photo of Andrei, so his widow, Galina, sent me one. This is how I remember him.

The 2015 Intel Science Talent Search results are out. This year they divided the prizes into three categories: basic research, global good, and innovation. All three top prizes in basic research were awarded to our PRIMES students:

• First place: Noah Golowich, Resolving a Conjecture on Degree of Regularity, with some Novel Structural Results
• Second place: Brice Huang, Monomization of Power Ideals and Generalized Parking Functions
• Third place: Shashwat Kishore, Multiplicity Space Signatures and Applications in Tensor Products of sl₂ Representations

PRIMES’ success in this year’s Siemens competition is even more impressive. Unlike Intel, Siemens didn’t divide the projects into three groups. We took the first and second overall individual prizes.

• First place: Peter Tian, Extremal Functions of Forbidden Multidimensional Matrices
• Second place: Zoseph Zurier, Generalizations of the Joints Problem

PRIMES is the place for high school math research. Congratulations to all our students—and to me (and my colleagues) for a job well done!

I mentor three PRIMES projects. One of them, with Joshua Xiong from Acton-Boxborough Regional High School, is devoted to impartial combinatorial games. We recently found a connection between these games and cellular automata. But first I need to remind you of the rules of Nim.

In the game of Nim there are several piles with counters. Two players take turns choosing a pile and removing several counters from it. A player loses when he or she who doesn’t have a turn. Nim is the most famous impartial combinatorial game and its strategy is well known. To win, you need to finish your move in a so called P-position. Nim P-positions are easy to calculate: Bitwise XOR the number of counters in all the piles, and if the result is zero then it’s a P-position.

The total number of counters in a P-position is even. So we calculated the sequence a(n): the number of P-positions in the game of Nim with three piles with the total number of counters equal to 2n. As soon as we got the sequence we plugged it into the OEIS, and voilà it was there: The sequence A130665 described the growth of the three branches of the Ulam-Warburton cellular automaton.

The first picture shows the automaton after 6 generations. The automaton consists of cells that never die and it grows like this: start with a square on a square grid. In the next generation the squares that share exactly one side with the living squares are born. At the end remove the Southern branch.

Everything fell into place. We immediately realized that the language of the automata gives us the right words to describe what we know about the game of Nim.

Now we want to describe the automaton related to any impartial combinatorial game. Again, the cells never die and the initial cells correspond to terminal P-positions. People who write programs for calculating P-positions will find a notion of the next generation very natural. Indeed, the program usually starts with the terminal P-positions: they are generation 0. Then we can proceed by induction. Suppose we have found P-positions up to generation i. Denote the positions that are one move away from generation i and earlier as N_i. Then the P-positions that do not belong to generation i and earlier and from which all moves belong to N_i are the P-positions from generation i + 1.

This description explains the generations, but it doesn’t explain who is the parent of a particular P-position. The parent-child relations are depicted as edges on the cellular automaton graph. The parent of position P₁ from generation i + 1 is a P-position P₂ in generation i that can be reached from P₁ in the game.

The parent-child relationship in the game of Nim is especially easy to explain. A P-position P₁ is a parent of a P-position P₂ if P₁ differs from P₂ in exactly two piles and it has one fewer counter in each of these piles. For example, a P-position (1,3,5,7) has six parents, one of them is (1,3,4,6). In the game with thee piles a P-position always has exactly one parent.

A position in the game of Nim with three piles is naturally depicted as a triple of numbers, that is as a point in 3D. The picture below shows the Nim automaton in 3D at generation 6.

Our paper, Nim Fractals, about sequences enumerating P-positions and describing the automaton connection in more detail is posted at the arXiv:1405.5942. We give a different, but equivalent definition of a parent-child relationship there. A P-position P₁ is a parent of P₂ if there exists an optimal game such that P₁ is achieved from P₂ in exactly two moves in a game which takes the longest number of possible moves.

PRIMES-USA: A new MIT program for talented math students from across the country.

I’ve been working as a math coordinator for RSI, the most competitive summer program for high school juniors. RSI arranges for these select students to do scientific research. I only work with kids who do math, and usually we have a dozen of them. Every student has an individual mentor, usually a graduate student, with whom they meet daily. I supervise all the projects and meet with each high school student about once a week. My job was described as “going for the biggest impact”: when the project is in trouble, I jump in to sort it out; when the project is doing well, I push it to further limits.

RSI is a great program: kids enjoy it and we produce interesting research. My biggest concern is that the program is too short. The kids do math for five weeks and they usually approach a good result, but at the end of RSI we generally see just a hint of what they could truly achieve. Kids who continue to work on their own after the program ends are more successful. Unfortunately most of the students stop working at the end of the program just as they are approaching a big theorem.

I discussed this dissatisfying trend with Pavel Etingof and Slava Gerovitch and we decided to do something about it. Pavel and Slava conceived and found funding for a new program called PRIMES that is similar to RSI, but runs for a year. From February through May, PRIMES students meet with their mentors weekly. In fact, we require on the application that the students commit to coming to MIT once a week, thereby limiting us to local students. Theoretically, someone from Detroit with a private jet who can fly to MIT weekly would be welcomed.

Before the first year, we wondered whether the smaller pool of local students would be weaker than national and international RSI students. To our delight, that wasn’t the case. In the first year we got fantastic students. One explanation is that PRIMES is much more flexible. We do not mind when our students go to IMO in the summer or to math camps or when they go away on vacation with their parents. As a result, we get students who would never apply to RSI because of their summer schedules. Our PRIMES students have won so many prizes that I do not remember them all. We post our successes on the website.

Our success in PRIMES suggests that there are likely many talented kids in other states who never even apply to RSI because of a scheduling conflict. This led us to try to adapt PRIMES to national needs. So we created a new program called PRIMES-USA that will accept students from across the country. We will work with them through Skype. These students must commit to travel to MIT for a PRIMES conference in May. Because this is our pilot program, we will only accept five students.