Tanya Khovanova's Math Blog

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.

I wrote how the written entrance exam was used to keep Jewish students from studying at Moscow State University, but the real brutality happened at the oral exam. Undesirable students were given very difficult problems. Here is a sample “Jewish” problem:

Solve the following equation for real y:

Here is how my compatriots who studied algebra in Soviet high schools would have approached this problem. First, cube it and get a 9th degree equation. Then, try to use the Rational Root Theorem and find that y = 1 is a root. Factoring out y − 1 gives an 8th degree equation too messy to deal with.

The most advanced students would have checked if the polynomial in question had multiple roots by GCDing it with its derivative, but in vain.

We didn’t study any other methods. So the students given that problem would have failed it and the exam.

Unfortunately, this problem is impossible to appeal, because it has an elementary solution that any applicant could have understood. It goes like this:

Let us introduce a new variable: x = (y³ + 1)/2. Now we need to solve a system of equations:

This system has a symmetry which we can exploit. The graphs of the functions x = (y³ + 1)/2 and y = (x³ + 1)/2 are reflections of each other across the line x = y. As both functions are increasing, the solution to the system of equations should lie on the line x = y. Hence, we need to solve the cubic y = (y³ + 1)/2, one of whose roots we already know.

Now I offer you another problem without telling you the solution:

Four points on a plane used to belong to four different sides of a square. Reconstruct the square by compass and straightedge.

Recently I asked my readers to look at the 1976 written math exam that was given to applicants wishing to study at the math department of Moscow State University. Now it’s time to reveal the hidden agenda. My readers noticed that problems 1, 2, and 3 were relatively simple, problem 4 was very hard, and problem 5 was extremely hard. It seems unfair and strange that problems of such different difficulty were worth the same. It is also suspicious that the difficult problems had no opportunity for partial credit. As a result of these characteristics of the exam, almost every applicant would get 3 points, the lowest passing score. The same situation persisted for many years in a row. Why would the best place to study math in Soviet Russia not differentiate the math abilities of its applicants?

In those years the math department of Moscow State University was infamous for its antisemitism and its efforts to exclude all Jewish students from the University. The strange structure of the exam accomplished three objectives toward that goal.

1. Protect the fast track. There was a fast track for students with a gold medal from their high school who got 5 points on the written exam. The structure of the exam guaranteed that very few students could solve all 5 problems. If by chance a Jewish student solved all 5 problems, it was not much work to find some minor stylistic mistake and not count the solution.

2. Avoid raising suspicion at the next exams. The second math entrance exam was oral. At such an exam different students would talk one-on-one with professors and would have to answer different questions. It was much easier to arrange difficult questions for undesirable students and fail all the Jewish students during the oral exam than during the written exam. But if many students with perfect scores on the written exam had failed the oral exam, it might have raised a lot of questions.

3. Protect appeals. Despite these gigantic efforts, there were cases when Jewish students with a failing score of 2 points were able to appeal and earn the minimum passing score of 3. If undesirable students managed to appeal all the exams, they would only get a half-passing grade at the end and would not be accepted because the department was allowed to choose from the many students that the exams guaranteed would have half-passing scores.

I have only heard about one faculty member who tried to publicly fight the written exam system. It was Vladimir Arnold, and I will tell the story some other time.

In 1976 I was about to become a student in the math department at Moscow State University. As an IMO team member I was accepted without entrance exams, but all of my other classmates had to take the exams. There were four exams: written math, oral math, physics, and an essay.

The written math exam was the first, and here are the problems. I want my non-Russian readers to see if they notice anything peculiar about this exam. Can you explain what is peculiar, and what might be the hidden agenda?

Problem 1. Solve the equation

Problem 2. Solve the inequality

Problem 3. Consider a right triangle ABC with right angle C. Angle B is 30° and leg CA is equal to 1. Let D be the midpoint of the hypotenuse AB, so that CD is a median. Choose F on the segment BC so that the angle between the hypotenuse and the line DF is 15°. Find the area of CDF. Calculate its numeric value with 0.001 precision.

Problem 4. Three balls, two of which are the same size, are tangent to the plane P, as well as to each other. In addition, the base of a circular cone lies on the plane P, and its axis is perpendicular to the plane. All three balls touch the cone from the outside. Find the angle between a generatrix of the cone and the plane P, given that the triangle formed by the points of tangency of the balls and the plane has one angle equal to 150°.

Problem 5. Let r < s < t be real numbers. If you set y equal to any of the numbers r, s or t in the equation x² − (9 − y)x + y² − 9y + 15 = 0, then at least one of the other two numbers will be a root of the resulting quadratic equation. Prove that −1 < r < 1.

Let me describe some background to this exam. Applicants who solve fewer than two problems fail the exam and are immediately rejected. People who solve two or three problems are given 3 points. Four problems earn 4 points, and five problems earn 5 points.

If you still do not see the hidden agenda, here is another clue. People who get 5 points on the first exam and, in addition, have a gold medal from their high school (that means all As) are admitted right after the first exam. For the others, if they do not fail any of the exams, points are summed up with their GPAs to compute their scores. The so-called half-passing score is then calculated. Scores strictly higher than the half-passing score qualify applicants for admission. However, there are too many applicants for the available openings with at least the half-passing score. As a result only some people with exactly the half-passing score are accepted, at the discretion of the department.

Now my readers have enough information to figure out the hidden agenda behind that particular exam.

by Pavel Etingof and Tanya Khovanova

We worked for several years with RSI where we supervised summer math research projects by high school students. Now, we’ve started an additional program at MIT’s math department called PRIMES, where local high school students do math research during the academic year. In this essay we would like to discuss what makes a good math research project for a high school student.

A doable project. The project should not be believed to be extremely difficult to yield at least results. It is very discouraging for an aspiring mathematician not to produce anything during their first project.

An accessible beginning. The student should be able to start doing something original soon after the start of the project. After all, they don’t come to us for coursework, but for research.

Flexibility. It is extremely important to offer them a project that is adjustable; it should go in many directions with many different potential kinds of results. Since we do not know the strength of incoming students in advance, it is useful to have in mind both easier and harder versions of the project.

Motivation. It is important for the project to be well motivated, which means related to other things that have been studied and known to be interesting, to research of other people, etc. Students get more excited when they see that other people are excited about their results.

A computer component. This is not a must for a good project. But modern mathematics involves a lot of computation and young students are better at it than many older professors. Such a project gives young students the opportunity to tackle something more senior people are interested in but might not have enough computer skills to solve. In addition, through computer experiments students get exposed to abstract notions (groups, rings, Lie algebras, representations, etc.) in a more “hands-on” way than when taking standard courses, and as a result are less scared of them.

A learning component. It is always good when a project exposes students to more advanced notions.

The student should like their project. This is very difficult to accomplish when projects are chosen in advance before we meet the students. However, we try to match them to great projects by using the descriptions they give of their interests on their applications. It goes without saying that mentors should like their project too.

Having stated the desired properties of a good project, let us move on to giving examples: bad projects and good projects. We start with a bad one:

Prove that the largest power of 2 that doesn’t contain 0 is 2⁸⁶.

The project satisfies only one requirement: it contains a computer component. Otherwise, it doesn’t have an accessible beginning. It is not very flexible: if the student succeeds, the long-standing conjecture will be proven; if s/he doesn’t, there is not much value in intermediate results. The question is not very interesting. The only motivation is that it has been open for a long time. Also, there is not much to learn. Though, almost any theoretical question can be made flexible. We can start with the question above and change its direction to make it more promising and enticing.

Another bad example is a project where the research happens after the programs are written. This is bad because it is difficult to estimate the programming abilities of incoming students. It doesn’t have an accessible beginning and there is no flexibility until the programming part is finished. If the student can’t finish the programming quickly, s/he will not have time to look at the results and produce conjectures. For example, almost any project in studying social networks may fall into this category:

Study an acquaintance graph for some epic movies or fiction, for example Star Wars or The Lord of the Rings. In this graph people are vertices and two people are connected by an edge if they know each other. The project is to compare properties of such graphs to known properties of other social networks.

Though the networks in movies are much smaller than other networks that people study, the amount of programming might be substantial. This project can be a good project for a person with a flexible time frame or a person who is sure in advance that there will be enough time for him/her to look at the data.

Now on to an example of a good project. Lynnelle Ye and her mentor, Tirasan Khandhawit, chose to analyze the game of Chomp on graphs during RSI 2009.

Given a graph, on each turn a player can remove an edge or a vertex together with all adjacent edges. The player who doesn’t have a move loses. This game was previously solved for complete graphs and forest graphs, so the project was to analyze the game for other types of graphs.

It is clear how to analyze the game for any particular new graph. So that could be a starting point providing an accessible beginning. After that the next step could be to analyze other interesting sets of graphs. The flexibility is guaranteed by the fact that there are many sets of graphs that can be used. In addition, the project entails learning some graph theory and game theory. And the project has a computational component.

Lynnelle Ye successfully implemented this project and provided a complete analysis of complete n-partite graphs for arbitrary n and all bipartite graphs. She also gave partial results for odd-cycle pseudotrees. The paper is available at the arxiv. Not surprisingly, Lynelle got fourth place in the Intel Science Talent Search and second place in the Siemens Competition.

Two days ago I threw at my readers the following problem:

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

The purpose of throwing this problem was to discuss the nature of the implicit assumptions that we are asked to make when solving math problems, and the implicit assumptions we teach our children to make when we teach them to solve math problems. This is especially important for problems like this, that are phrased in terms of a situation in the real world. The real world is too complex to model all of; the great power of mathematics is that sufficiently idealized situations are predictable. But which idealizations are appropriate? How does one choose? How does one teach youngsters what to choose?

Before I get to the actual discussion, however, I want to re-throw this problem at my readers, in an effort to highlight what originally jumped out at me as being wrong with it.

Neglecting the effects of altitude, differential wind, acceleration, relativity, measurement error, finite size and non-superimposability of the planes, and the Earth’s deviations from perfect sphericity,

1. Find how much time it takes them to become 2000 miles apart, assuming that the planes are starting from Boston and the distance is measured as
   1. a straight line in 3-space.
   2. the shortest surface distance.
2. How far from the closest pole may the starting point be located, so that the answer to the problem is “never”? Solve separately for
   1. the 3D distance.
   2. the shortest surface distance.
3. What portion of the Earth’s surface do the “never”-locations of the previous question occupy?
   1. under the 3D distance?
   2. under the shortest surface distance?

Hint: The easiest question is 2b.

I stumbled upon the following problem in Mathematics Teacher v.73 (September 1980):

A plane takes off and goes east at a rate of 350 mph. At the same time, a second plane takes off from the same place and goes west at a rate of 400 mph. When will they be 2000 miles apart?

Ooh, boy!

Question for my readers: explain my reaction.