Tanya Khovanova's Math Blog

I recently stumbled upon some notes (in Russian) of a public lecture given by Vladimir Arnold in 2006. In this lecture Arnold defines a notion of complexity for finite binary strings.

Consider a set of binary strings of length n. Let us first define the Ducci map acting on this set. The result of this operator acting on a string a₁a₂…a_n is a string of length n such that its i-th character is |a_i − a_(i+1)| for i < n, and the n-th character is |a_n − a₁|. We can view this as a difference operator in the field F₂, and we consider strings wrapped around. Or we can say that strings are periodic and infinite in both directions.

Let’s consider as an example the action of the Ducci map on strings of length 6. Since the Ducci map respects cyclic permutation as well as reflection, I will only check strings up to cyclic permutation and reflection. If I denote the Ducci map as D, then the Ducci operator is determined by its action on the following 13 strings, which represent all 64 strings up to cyclic permutation and reflection: D(000000) = 000000, D(000001) = 000011, D(000011) = 000101, D(000101) = 001111, D(000111) = 001001, D(001001) = 011011, D(001011) = 011101, D(001111) = 010001, D(010101) = 111111, D(010111) = 111101, D(011011) = 101101, D(011111) = 100001, D(111111) = 000000.

Now suppose we take a string and apply the Ducci map several times. Because of the pigeonhole principle, this procedure is eventually periodic. On strings of length 6, there are 4 cycles. One cycle of length 1 consists of the string 000000. One cycle of length 3 consists of the strings 011011, 101101 and 110110. Finally, there are two cycles of length 6: the first one is 000101, 001111, 010001, 110011, 010100, 111100, and the second one is shifted by one character.

We can represent the strings as vertices and the Ducci map as a collection of directed edges between vertices. All 64 vertices corresponding to strings of length 6 generate a graph with 4 connected components, each of which contains a unique cycle.

The Ducci map is similar to a differential operator. Hence, sequences that end up at the point 000000 are similar to polynomials. Arnold decided that polynomials should have lower complexity than other functions. I do not completely agree with that decision; I don’t have a good explanation for it. In any case, he proposes the following notion of complexity for such strings.

Strings that end up at cycles of longer length should be considered more complex than strings that end up at cycles with shorter length. Within the connected component, the strings that are further away from the cycle should have greater complexity. Thus the string 000000 has the lowest complexity, followed by the string 111111, as D(111111) = 000000. Next in increasing complexity are the strings 010101 and 101010. At this point the strings that represent polynomials are exhausted and the next more complex strings would be the three strings that form a cycle of length three: 011011, 101101 and 110110. If we assign 000000 a complexity of 1, then we can assign a number representing complexity to any other string. For example, the string 111111 would have complexity 2, and strings 010101 and 101010 would have complexity 3.

I am not completely satisfied with Arnold’s notion of complexity. First, as I mentioned before, I think that some high-degree polynomials are so much uglier than other functions that there is no reason to consider them having lower complexity. Second, I want to give a definition of complexity for periodic strings. There is a slight difference between periodic strings and finite strings that are wrapped around. Indeed, the string 110 of length 3 and the string 110110 of length 6 correspond to the same periodic string, but as finite strings it might make sense to think of string 110110 as more complex than string 110. As I want to define complexity for periodic strings, I want the complexity of the periodic strings corresponding to 110 and 110110 to be the same. So this is my definition of complexity for periodic strings: let’s call the complexity of the string the number of edges we need to traverse in the Ducci graph until we get to a string we saw before. For example, let us start with string 011010. Arrows represent the Ducci map: 011010 → 101110 → 110011 → 010100 → 111100 → 000101 → 001111 → 010001 → 110011. We saw 110011 before, so the number of edges, and thus the complexity, is 8.

The table below describes the complexity of the binary strings of length 6. The first column shows one string in a class up to a rotation or reflections. The second column shows the number of strings in a class. The next column provides the Ducci map of the given string, followed by the length of the cycle. The last two columns show Arnold’s complexity and my complexity.

As you can see, for examples of length six my complexity doesn’t differ much from Arnold’s complexity, but for longer strings the difference will be more significant. Also, I am pleased to see that the sequence 011010, the one that I called The Random Sequence in one of my previous essays, has the highest complexity.

I know that my definition of complexity is only for periodic sequences. For example, the binary expansion of pi will have a very high complexity, though it can be represented by one Greek letter. But for periodic strings it always gives a number that can be used as a measure of complexity.

I met Leon Vaserstein at a party. What do you think I do at parties? I bug people for their favorite problems, of course. The first riddle Leon gave me is a variation on a famous problem I had already written about. Here’s his version:

The hypotenuse of a right triangle is 10 inches, and one of the altitudes is 6 inches. What is the area?

When Leon told me that he had designed some problems for the Soviet Olympiads, naturally I wanted to hear his favorite:

A closed polygonal chain has its vertices on the vertices of a square grid and all the segments are the same length. Prove that the number of segments is even.

* * * A Generic Limerick (submitted by Michael Chepovetsky)

There once was an X from place B,
Who satisfied predicate P,
The X did thing A,
In a specified way,
Resulting in circumstance C.

* * *

I just learned that 4,416,237 people got married in the US in 2010. Not to nitpick, but shouldn’t it be an even number?

* * *

We are happy to announce that 100% of Russian citizens are computer-savvy and use the Internet on a regular basis (according to a recent Internet survey).

* * *

Two math teachers had a fight. It seems they couldn’t divide something.

* * *

Do you know that if you start counting seconds, once you reach 31,556,926 you discover that you have wasted a whole year?

* * *

What I need after a visit to the hairdresser is a “Save” button.

* * *

— Hello! Is this a fax machine?
— Yes.

* * *

— I am not fat at all! My girlfriend tells me that I have a perfect figure.
— Your girlfriend is a mathematician. For her a perfect figure is a sphere.

* * *

A: Hi, how are you?
B: +
A: Will you come to classes today?
B: –
A: You will be kicked out!
B: =
A: Are you using your calculator to chat?

I wonder what the largest number is that can be represented with one character. Probably 9. How about two characters? Is it 9⁹? What about three or four?

I guess I should define a character. Let’s have two separate cases. In
the first one you can only use keyboard characters. In the second one
you can use any Unicode characters.

I’m awaiting your answers to this.

The last time I talked to John H. Conway, he taught me to walk up the stairs. It’s not that I didn’t know how to do that, but he reminded me that a nerd’s goal in climbing the steps is to establish the number of steps at the end of the flight. Since it is boring to just count the stairs, we’re lucky to have John’s fun system.

His invention is simple. Your steps should be in a cycle: short, long, long. Long in this case means a double step. Thus, you will cover five stairs in one short-long-long cycle. In addition, you should always start the first cycle on the same foot. Suppose you start on the left foot, then after two cycles you are back on the left foot, having covered ten stairs. While you are walking the stairs in this way, it is clear where you are in the cycle. By the end of the staircase, you will know the number of stairs modulo ten. Usually there are not a lot of stairs in a staircase, so you can easily estimate the total if you know the last digit of that number.

I guess I am not a true nerd. I have lived in my apartment for eight years and have never bothered to count the number of steps. That is, until now. Having climbed my staircase using John’s method, I now know that the ominous total is 13. Oh dear.

The Moscow Math Olympiad has a different set of problems for every grade. Students need to write a proof for every problem. These are the 8th grade problems from this year’s Olympiad:

Problem 1. There were 6 seemingly identical balls lying at the vertices of the hexagon ABCDEF: at A — with a mass of 1 gram, at B — with a mass of 2 grams, …, at F — with a mass of 6 grams. A hacker switched two balls that were at opposite vertices of the hexagon. There is a balance scale that allows you to say in which pan the weight of the balls is greater. How can you decide which pair of balls was switched, using the scale just once?

Problem 2. Peter was born in the 19th century, while his brother Paul was born in the 20th. Once the brothers met at a party celebrating both birthdays. Peter said, “My age is equal to the sum of the digits of my birth year.” “Mine too,” replied Paul. By how many years is Paul younger than Peter?

Problem 3. Does there exist a hexagon which can be divided into four congruent triangles by a single line?

Problem 4. Every straight segment of a non-self-intersecting path contains an odd number of sides of cells of a 100 by 100 square grid. Any two consecutive segments are perpendicular to each other. Can the path pass through all the grid vertices inside and on the border of the square?

Problem 5. Denote the midpoints of the non-parallel sides AB and CD of the trapezoid ABCD by M and N respectively. The perpendicular from the point M to the diagonal AC and the perpendicular from the point N to the diagonal BD intersect at the point P. Prove that PA = PD.

Problem 6. Each cell in a square table contains a number. The sum of the two greatest numbers in each row is a, and the sum of the two greatest numbers in each column is b. Prove that a = b.

A mathematician is someone who pauses when asked “How much is two and two?”

Indeed, the answer might be:

• 0 — modulo 4.
• 1 — in characteristic 3.
• 2 — if AND is considered as a logical operation.
• 4 ± ε — for approximate values of 2.
• 4 — (almost forgot this case).
• 10 — in base 4.
• 11 — in base 3.
• 22 — for string concatenations.
• MSC — (this one is your homework).