Tanya Khovanova's Math Blog

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.

My co-author Konstantin Knop wrote a charming book, Weighings and Algorithms: from Puzzles to Problems. The book contains more than one hundred problems. Here are a couple of my favorites that I translated for you:

There is one gold medal, three silver medals and five bronze medals. It is known that one of the medals is fake and weighs less than the corresponding genuine one. Real medals made of the same metal weigh the same and from different metals do not. How can you use a balance scale to find the fake medal in two weighings?

There are 15 coins, out of which not more than seven are fake. All genuine coins weigh the same. Fake coins might not weigh the same, but they differ in weight from genuine coins. Can you find one genuine coin using a balance scale 14 times? Can you do it using fewer weighings?

You might get the impression that the latter problem depends on two parameters. Think about it: It is necessary that the majority of the coins are genuine in order to be able to solve the problem. In fact, the number of weighings depends on just one parameter: the total number of coins. Denote a(n) the optimal number of weighings needed to find a genuine coin out of n coins, where more than half of the coins are genuine. Can you calculate this sequence?

Hint. I can prove that a(n) ≤ A011371(n-1); that is, the optimal number of weighings doesn’t exceed n − 1 − (number of ones in the binary expansion of n−1).

Tanya Khovanova and Alexey Radul

We all heard this paradoxical statement:

This statement is false.

Or a variation:

True or False: The correct answer to this question is ‘False’.

Recently we received a link to the following puzzle, which is similar to the statement above, but has a cute probabilistic twist:

If you choose an answer to this question at random, what is the chance you will be correct?

1. 25%
2. 50%
3. 60%
4. 25%

There are four answers, so you can choose a given answer with probability 25%. But oops, this answer appears twice. Is the correct answer 50%? No, it is not, because there is only one answer 50%. You can see that none of the answers are correct, hence, the answer to the question—the chance to be correct—is 0. Now is the time to introduce our new puzzle:

If you choose an answer to this question at random, what is the chance you will be correct?

1. 25%
2. 50%
3. 0%
4. 25%

This fractal was designed by Ross Hilbert and is named “Weathered Steel Weave.” You can find many other beautiful pictures in his fractal gallery.

The fractal is based on iterations of the following fractal formula z_new = cos(c z_old), where the Julia Constant c is equal to −0.364444444444444+0.995555555555556i. To produce the image, you need to start with a complex value of z and iterate it many times using the formula above. The color is chosen based on how close the iteration results are to the border of the unit circle.

I found a new Russian Olympiad for high schools related to universities. I translated my favorite problems from last year’s final round. These are the math problems:

8th grade. In a certain family everyone likes their coffee with milk. At breakfast everyone had a full cup of coffee. Given that Alex consumed a quarter of all consumed milk and one sixth of all coffee, how many people are there in the family?

8th grade. How many negative roots does the equation x⁴ − 5x³ − 4x² − 7x + 4 = 0 have?

10th grade. Find a real-valued function f(x) that satisfies the following inequalities for any real x and y: f(x) ≤ x and f(x+y) ≤ f(x) + f(y).

I liked the physics problems even more:

8th grade. Winnie-the-Pooh weighs 1 kg. He hangs in the air with density 1.2kg/m³ next to a bee hive. He is holding a rope connected to a balloon. Estimate the smallest possible diameter of the balloon, assuming that this happens on Earth.

10th grade. Two containers shaped like vertical cylinders are connected by a pipe underneath them. Their heights are the same and they are on the same level. The cross-sectional area of the right container is twice bigger than the left’s. The containers are partially filled with water of room temperature. Someone put ice into both containers: three times more ice into the right one than into the left one. After that, the containers are closed hermetically. How will the water level will change after the ice melts completely:

• The levels will not change.
• The level on the left will be higher than on the right.
• The level on the left will be lower than on the right.
• The answer depends on the initial volume of water in the containers.

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.