Tanya Khovanova's Math Blog

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.

Imagine a magician who comes on stage and performs the following magic trick:

He asks someone in the audience to think of a two-digit number, then subtract the sum of its digits. He waves his wand and guesses that the result is divisible by nine. Ta-Da!

This is not magic. This is a theorem. To make it magical we need to disguise the theorem.

First, there are many ways to hide the fact that we subtract the sum of the digits. For example, we can ask to subtract the digits one by one, while chatting in between. It is better to start with subtracting the first digit. Indeed, if we start with subtracting the second digit, the audience might notice that the result is divisible by 10 and start suspecting that some math is involved here. You can be more elaborate in how you achieve the subtraction of the sum of digits. For example, subtract twice the first digit, then the second, then add back the original number divided by 10.

Second, we need to disguise that the result is divisible by 9. A nice way to do this is implemented in the online version of this trick. The website matches the resulting number to a gift that is described on the page in pale letters. Paleness of letters is important as it is difficult to see that the same gift reappears in a pattern. In my work with students I use the picture on the left. At the end I tell them, “Ta-Da! the resulting number is blue.” Here is the full sized version of the same picture that you can download.

My students are too smart. They see through me and guess what is going on. Then I ask them the real question, “Why do I have some cells with question marks and other symbols?” To give you a hint, I can tell you that the symbols are there for the same reason some blue numbers are not divisible by 9.

I have two admirers, Alex and Mike. Alex lives next to my home and Mike lives next to my MIT office. I have a lousy memory, so I invented the following system to guarantee that I see both of my friends and also manage to come to my office from time to time. I have a sign hanging on the inside of my home door that says Office on one side and Alex on the other. When I approach the door, I can see right away where I went last time. So I flip the sign and that tells me where next to go. I have a similar sign inside my office door that tells me to go either to home or to Mike. Every evening I spend with one of my admirers discussing puzzles or having coffee. Late at night I come home to sleep in my own bed. Now let’s see what happens if today my home sign shows Office and the office sign shows Mike:

• Today. I flip the home sign to Alex and spend the evening with Alex.
• Tomorrow. I flip the home sign to Office and go to MIT. Later I flip the office sign to Home and return home. As I cannot stand to spend the evening at home alone, I go out again. I flip the home sign to Alex and spend the evening with Alex.
• The day after tomorrow. I flip the home sign to Office and go there. Later I flip the office sign to Mike and spend the evening with Mike.

After three days the signs return to their original positions, meaning that the situation is periodic and I will repeat this three-day pattern forever.

Let’s get back to reality. I am neither memory-challenged nor addicted to coffee. I invented Alex and Mike to illustrate a rotor-router network. In general my home is called a source: the place where I wake up and start the day. There can only be one source in the network. My admirers are called targets and I can have an infinite number of them. The network needs to be constructed in such a way that I always end up with a friend by the end of the day. There could be many other places that I can visit, other than my office: for example, the library, the gym, opera and so on. These places are other vertices of a network that could be very elaborate. Any place where I go, there is a sign that describes a pattern of where I go from there. The sign is called a rotor.

The patterns at every rotor might be more complicated than a simple sign. Those patterns are called rotor types. My sign is called 12 rotor type as it switches between the first and the second directions at every non-friend place I visit.

The sequence of admirers that I visit is called a hitting sequence and it can be proved that the sequence is eventually periodic. Surprisingly, the stronger result is also true: the hitting sequence is purely periodic.

The simple 12 rotor is universal. That means that given a set of friends and a fancy periodic schedule that designates the order I want to visit them in, I can create a network of my activities where every place has a sign of this type 12 and where I will end up visiting my friends according to my pre-determined periodic schedule.

It is possible to see that not every rotor type is universal. For example, palindromic rotor types generate only palindromic hitting sequences, thus they are not universal. The smallest such example, is rotor type 121. Also, block-repetitive rotor types, like 1122, generate block-repetitive hitting sequences.

It is a difficult and an interesting question to describe universal rotor types. My PRIMES student Xiaoyu He was given a project, suggested by James Propp, to prove or disprove the universality of the 11122 rotor type. This was the smallest rotor type the universality of which was not known. Xiaoyu He proved that 11122 is universal and discovered many other universal rotor types. His calculations support the conjecture that only palindromic or block-repetitive types are not universal. You can find these results and many more in his paper: On the Classification of Universal Rotor-Routers.

Once I talked to my friend Michael Plotkin about IQ tests, which we both do not like. Michael suggested that I run an experiment and send a standard IQ question for children to my highly-educated friends. So I sent a mass email asking:

What’s common between an apple and an orange?

I believe that the expected answer is that both are fruits.

Less than half of my friends would have passed the IQ test. They gave four types of answer. The largest group chose the expected answer.

The second group related the answer to language. For example, apples and oranges both start with a vowel and they both have the letters A and E in common.

The third group connected the answer to what was on their minds at the time:

• Apples and oranges are both healthy foods that I enjoy, but do not eat as often as I should.
• They have the same thing in common as do a saxophone and a guitar.
• You can’t shave with either one.
• They both are much worse than a cucumber in the bedroom.

And the last group were people who just tried to impress me:

• One should not decide that n apples is better than m oranges just because n > m.
• They both can provoke the discovery of gravity.
• You can’t compare apples and oranges.
• Existence.
• They both have fundamental meaning in food tongue.
• They’re topologically homeomorphic.

If my friends with high IQs have given so many different answers, I would expect children to do the same. The variety of answers is so big that no particular one should define IQ. By the way, my own well-educated kids’ answers are quoted above — and they didn’t go with the standard answer. I’m glad they never had IQ tests as children: I’m sure they would never have passed.

My e-friend and coauthor, Konstantin Knop, designed the following problem for the 2011 All-Russia Olympiad:

Some cells of a 100 by 100 board have one chip placed on them. We call a cell pretty if it has an even number of neighboring cells with chips. Neighbors are the cells that share a side. Is it possible for exactly one cell to be pretty?

The problem is not easy. Only one person at the Olympiad received full credit for it.