Tanya Khovanova's Math Blog

Let’s call a projection of a body L onto a hyperplane a shadow. Here is a mathematical way to hide behind. An object K can hide behind an object L if in any direction the shadow of K can be moved by a translation to be inside the corresponding shadow of L. If K can hide inside L, then obviously K can hide behind L. Dan Klain drew my interest to the following questions. Is the converse true? If K can hide behind L can it hide inside L? If not, then if K can hide behind L, does it follow that the volume of K is smaller than that of L?

We can answer both questions for 2D bodies by using objects with constant width. Objects with constant width are ones that have the same segment as their shadow in every direction. The two most famous examples are a circle and a Reuleaux triangle:

Let’s consider a circle and a Reuleaux triangle of the same width. They can hide behind each other. Barbier’s Theorem states that all objects of the same constant width have the same perimeter. We all know that given a fixed perimeter, the circle has the largest area. Thus, the circle can hide behind the Reuleaux triangle which has smaller area and, consequently, the circle can’t hide inside the Reuleaux triangle. By the way, the Reuleaux triangle has the smallest area of all the objects with the given constant width.

To digress. You might have heard the most famous Microsoft interview question: Why are manhole covers round? Presumably because round manhole covers can’t fall into slightly smaller round holes. The same property is true for manhole covers of any shape of constant width. On the picture below (Flickr original) you can see Reuleaux-triangle-shaped covers.

Let’s move the dimensions up. Dan’s questions become both more difficult and more interesting, because the shadows are not as simple as segments any more.

Before continuing, I need to introduce the concept of “Minkowski sums.” Suppose we have two convex bodies in space. Let’s designate the origin. Then a body can be represented as a set of vectors from the origin to the points in the body. The Minkowski sum of two bodies are all possible sums of two vectors corresponding to the first body and the second body.

Another way to picture the Minkowski sum is like this: Choose a point in the second body. Then move the second body around by translations so that the chosen point covers the first body. Then the area swept by the second body is the Minkowski sum of both of them.

Suppose we have two convex bodies K and L. Their Minkowski interpolation is the body tK + (1-t)L, where 0 ≤ t ≤ 1 is a scaling coefficient. The picture below made by Christina Chen illustrates the Minkowski interpolation of a triangle and an inverted triangle.

If two bodies can hide behind L, then their Minkowski interpolation can hide behind L for any value of parameter t. In particular if K can hide behind L, then the Minkowski interpolation tK + (1-t)L can hide behind L, for any t.

In my paper co-authored with Christina Chen and Daniel Klain “Volume bounds for shadow covering”, we found the following connection between hiding inside and volumes. If L is a simplex, and K can hide behind it, but can’t hide inside L, then there exists t such that the Minkowski interpolation tK + (1-t)L has a larger volume than the volume of L.

In the paper we conjecture that the largest volume ratio V(K)/V(L) for a body K that can hide behind another body L is achieved if L is a simplex and K is a Minkowski interpolation of L and an inverted simplex. The 3D object that can hide behind a tetrahedron and has 16% more volume than the tetrahedron was found by Christina Chen. See her picture below.

The main result of the paper is a universal constant bound: if K can hide behind L, then V(K) ≤ 2.942 V(L), independent of the dimension of the ambient space.

Recently I stumbled on a cute xkcd comic with the hidden message:

Wikipedia trivia: if you take any article, click on the first link in the article text not in parentheses or italics, and then repeat, you will eventually end up at “Philosophy”.

Naturally, I started to experiment. The first thing I tried was mathematics. Here is the path: Mathematics — Quantity — Property — Modern philosophy — Philosophy.

Then I tried physics, which led me to mathematics: Physics — Natural science — Science — Knowledge — Fact — Information — Sequence — Mathematics.

Then I tried Pierre de Fermat, who for some strange reason led to physics first: Pierre de Fermat — French — France — Unitary state — Sovereign state — State — Social sciences — List of academic disciplines — Academia — Community — Living — Life — Objects — Physics.

The natural question is: what about philosophy? Yes, philosophy goes in a cycle: Philosophy — Reason — Rationality — philosophy.

The original comic talks about spark plugs. So I tried that and arrived at physics: Spark plug — Cylinder head — Internal combustion engine — Engine — Machine — Machine (mechanical) — Mechanical system — Power — Physics.

Then I tried to get far away from philosophy and attempted sex, unsuccessfully: Sex — Biology — Natural science. Then I tried dance: Dance — Art — Sense — Physiology — Science.

It is interesting to see how many steps it takes to get to philosophy. Here is the table for the words I tried:

Mathematics wins. It thoroughly beats all the other words I tried. For now. Fans of sex might be disappointed by these results, and tomorrow they might change the wiki essay about sex to start as:

Modern philosophy considers sex …

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.

As you might have guessed from the title, this essay is about domino tilings.

Suppose a subset of a square grid has area N, and the number of possible domino tilings is T. Let’s imagine that each cell is contributing a factor of x tilings to the total independently of the others. Then we get that x^N = T. This mental exercise suggests a definition: we call the nth root of T the degree of freedom per square for a given region.

Let’s consider a 1 by 2k rectangle. There is exactly one way to tile it with dominoes. So the degree of freedom per square of such a rectangle is 1. Now consider a 2 by k rectangle. It has the same area as before, and we know that there should be more than one tiling. Hence, we expect the degree of freedom to be larger than the one in the previous example. The number of tilings of a 2 by k rectangle is F_k-2, where F_k is k^th Fibonacci number. So the degree of freedom for large k will be approximately the square root of the golden ratio, which is about 1.272.

You might expect that squares should give larger degrees of freedom than rectangles of the same area. The degree of freedom for a large square is about 1.3385. You can find more information in the beautiful paper Tilings by Federico Ardila and Richard P. Stanley.

Let’s move from rectangles to Aztec diamonds. They are almost like squares but the side of the diamond is aligned with diagonals of the dominoes rather than with their sides. See the sample diamonds in the picture above, which Richard Stanley kindly sent to me for this essay.

It is easier to calculate the degree of freedom for Aztec diamonds than for regular squares. The degree is the fourth root of 2, or 1.1892…. In the picture below created by James Propp’s tiling group you can see a random tiling of a large Aztec diamond.

Look at its colors: horizontal dominoes are yellow and blue; vertical ones are red and aquamarine. You might wonder what rule decides which of the horizontal dominoes are yellow and which are blue. I will not tell you the rule; I will just hint that it is simple.

Back to freedom. As you can see from the picture, freedom is highly non-uniform and depends on where you live. Freedom is concentrated inside a circle called the arctic circle, perhaps because the areas outside it are frozen for lack of freedom.

Now I would like to expand the notion of freedom to give each cell its own freedom. For a large Aztec diamond, I will approximate freedom with a function that is one outside the arctic circle and is uniform inside. The Aztec diamond AZ(n) consists of 2n(n+1) squares, shaped like a square with side-length n√2. So the area of the circle is πn²/2. Hence we can calculate the freedom inside the circle as the π^th root of 2, which is about 1.247. This number is still much less than the degree of freedom of a cell in a large square.

Tanya Khovanova, Alexey Radul

Perfidy is to parity as odious is to odd and evil is to even. As a reminder, odious numbers are numbers with an odd number of ones in their binary expansions. From here you can extrapolate what the evil numbers are and the fact that the perfidy of an integer is the parity of the number of ones in its binary expansion. We live in a terrible world: all numbers are perfidious.

So why are we writing about the perfidy of negative numbers? One would expect it to be a natural extension of the perfidy of positive numbers, but it turns out that the naive way of defining it doesn’t work at all. Is there hope? Could negative numbers be innocent of evil and free of odiousness? Is zero an impenetrable bulwark against perfidy? Not quite, but something interesting does happen to evil as it tries to cross zero. Read on.

To define perfidy for negative numbers, let us study how perfidy behaves for positive numbers. It is easiest to think about the perfidies of power-of-two-sized chunks of non-negative integers at a time. Let us denote by T_n the string of perfidies of the integers from 0 to 2ⁿ−1, with evil being zero and odious being 1. So T₀ = 0, T₁ = 01, T₂ = 0110, T₃ = 01101001, …. The recurrence relation governing the T_n is T_n+1 = T_nT_n, where T is the bitwise negation of the string T, and juxtaposition is concatenation. The limit of this as n tends to infinity is the (infinite) sequence of perfidies of non-negative integers. This sequence is called the Thue-Morse sequence: 0,1,1,0,1,0,0,1,1,0,0,1,0,1,1,0,1,0,0,….

So defining the perfidy of negative numbers is equivalent to extending the Thue-Morse sequence to the left. If we are to define “the” perfidy of negative numbers, that definition should preserve most of the properties of the Thue-Morse sequence after extension.

So, let’s see. We asked around, and most people said that the binary expansion of a negative integer should be the binary expansion of its absolute value, but with a minus sign. Defining perfidy as parity of number of ones in this binary expansion corresponds to the following extended Thue-Morse sequence in which we mark values corresponding to negative indices with bold font: … 0, 1, 1, 0, 1, 1, 0, ….

One of the major properties of the Thue-Morse sequence is its fractal property: if you replace every zero of the Thue-Morse sequence by 0,1 and every one by 1,0, you will get the Thue-Morse sequence back. Clearly, our new extended sequence doesn’t have this property.

Another set of properties for the Thue-Morse sequence, called avoidance properties, is a long list of patterns that the sequence avoids. For example, the Thue-Morse sequence doesn’t contain any overlapping squares — patterns axaxa, where a is a character and x is a word. But you can see above, our first extension contains it. So this definition is wrong, not just once but twice (and two wrongs only make a right under very unusual circumstances). Perfidy is stymied by the cross-over from zero to minus one. Are negative numbers protected from the ravages of evil? (and odiousness?)

Unfortunately, there are many people, for example John Conway, who inadvertently extend the reach of perfidy by arguing that the binary expansion of a negative integer should be different. Indulge in a flight of fancy and imagine the binary expansion that consists of infinitely many ones to the left: …1111. What happens when you add 1 to it? The carry gets pushed infinitely far away, and you get …000000 — zero. So it is quite reasonable to let …1111 be the binary expansion of −1. Similarly, the string …1110 represents −2, …1101 represents −3, etc. Continuing this we see that the binary expansion of a negative integer −n is the bitwise negation of the binary expansion of n − 1 (including the leading zeros). This is called the Two’s complement representation.

Why is two’s complement a reasonable representation? Suppose you were trying to invent a binary notation for negative numbers, but you wanted to pursue uniformity by not using a minus sign. The problem is that the standard definition of the binary representation allows you to represent only positive numbers. But you can solve this problem with modular arithmetic: modulo any fixed N, every negative number is equivalent to some positive number (by adding enough multiples of N), so you can just represent it by representing that positive number. If you choose N to be a power of two, modding out by it is just truncation of the binary representation. If you let those powers of two tend to infinity, you get the two’s complement representation described above.

Aside: When you are building a computer, uniformity is money, because special cases cost special transistors. The two’s complement idea lets one build arithmetic units that just operate on positive numbers with some number of bits (effectively doing arithmetic modulo 2^k), and leave the question of negativeness to the choice of representatives of those equivalence classes.

If we take two’s complement as the binary expansion of negative numbers, how will we define the perfidy? Is the number of ones in the infinite string …1111 corresponding to −1 even or odd?

We can’t answer that question, but we know for every binary expansion of negative numbers the parity of the number of zeroes. Thus we can divide all negative integers in two classes with different perfidy. We just do not know which one is which.

Let us consider two cases. In the first case we consider a negative number odious if the number of zeroes in its binary expansion is odd. The corresponding extended Thue-Morse sequence is: … 0, 1, 1, 0, 0, 1, 1, 0, …. The negative half is the reflection of the classical Thue-Morse sequence. In the second case we consider a negative number odious if the number of zeroes in its binary expansion is even. The corresponding extended Thue-Morse sequence is: … 1, 0, 0, 1, 0, 1, 1, 0, …. The negative half is the bitwise negation of the reflection of the classical Thue-Morse sequence.

Can we say that one of the sequences is better than the other? Both of them respect the fractal property of the classical Thue-Morse sequence. Let us look at the avoidance properties. The avoidance properties are symmetric with respect to switching zeroes with ones and with respect to changing the direction of the sequence. Hence, the negation, the reflection, and the reflection of the negation of the Thue-Morse sequence will continue to respect these properties.

Thus, we only need to check the avoidance properties of the finite subsequences that span both negative and non-negative indices. We claim that for both definitions of perfidy, any finite middle subsequence of the extended Thue-Morse sequence occurs as a subsequence in the classical Thue-Morse sequence. So any avoidance properties that are true for the Thue-Morse sequence will also be true for both extensions.

Indeed, it is easy to show that the strings T_2n defined above are palindromes. So for the first definition of perfidy the string in the middle will be a substring of T_2nT_2n for some large n, and for the second definition a substring of T_2nT_2n. But the classical Thue-Morse sequence contains the subsequence T_2nT_2nT_2nT_2nT_2nT_2nT_2nT_2n. So whichever way we extend the Thue-Morse sequence to the left any finite middle part will always be a repetition of a piece in the classical Thue-Morse sequence. Thus, all the avoidance properties will hold.

We see that there are two logical ways to define perfidy for negative integers. There are two clear groups of numbers with the same perfidy, but which is called evil and which odious is interchangeable. So evil doesn’t stop at zero after all, but at least it gets an identity crisis.

Background and Definitions

I’ve heard about many mathematicians running polymath projects through their blogs. I wasn’t planning to do that. It just happened. In this essay, I describe the collaborative effort that was made to solve the following problem that appeared in my blog on July 2009:

Baron Münchhausen has n identical-looking coins weighing 1, 2, …, n grams. The Baron’s guests know that he has this set of coins, but do not know which one is which. The Baron knows which coin is which and wants to demonstrate to his guests that he is right. He plans to conduct weighings on a balance scale, so that the guests will be convinced about the weight of every of coin. What is the smallest number of weighings that the Baron must do in order to reveal the weights?

The sequence a(n) of the minimal number of weighings is called the Baron Münchhausen’s omni-sequence to distinguish it from the Existential Baron’s sequence where he needs the smallest amount of weighings to prove the weight of one coin of his choosing.

In this essay I will describe efforts to calculate a(n). The contributors are: Max Alekseyev, Ilya Bogdanov, Maxim Kalenkov, Konstantin Knop, Joel Lewis and Alexey Radul.

Starting Examples: n = 1, n = 2 and n = 3

The sequence starts as a(1) = 0, because there is nothing to demonstrate. Next, a(2) = 1, since with only one weighing you can find which coin is lighter.

Next, a(3) = 2. Indeed you can’t prove all the coins in one weighing, but in the first weighing you can show that the 1-gram coin is lighter than the 2-gram coin. In the second weighing you can show that the 2-gram coin is lighter than the 3-gram coin. Thus, in two weighings you can establish an order of weights and prove the weight of all three coins.

n = 4 and the Tightness Conjecture

As you can see in the case of n = 3, you can compare coins in order and prove the weight of all the coins in n − 1 weighings. But this is not at all the optimal number. Let us see why a(4) = 2. In his first weighing the Baron can put the 1- and the 2-gram coins on the left pan of the balance and the 4-gram coin on the right pan. In the future, I will just describe that weighing as 1 + 2 < 4. This way everyone agrees that the coin on the right pan is 4 grams, and the coin that is left out is 3 grams. The only thing that is left to do is to compare the 1-gram and the 2-gram coins in the second weighing.

Later Konstantin Knop sent me a different solution for n=4. His solution provides an interesting example. While looking for solutions, people usually try to have an unbalanced weighing to be “tight”. That is, they make it so that the heavier cup is exactly 1 gram heavier than the lighter cup. If you are trying to prove one coin in one weighing, “tightness” is a requirement. But it is not necessary when you have several weighings. Here is the first weighing in Konstantin’s solution: 1 + 3 = 4; and his second second weighing is: 1 + 2 < 3 + 4. We see that the second weighing has a weight difference of four between pans.

n = 5 and n = 6

Next, a(5) = 2. We can have the first weighing the same as before: 1 + 2 < 4, and the second weighing: 1 + 4 = 5. The second weighing confirms that the heavy coin on the right pan in the first weighing can’t be the heaviest one, thus it has to be the 4-gram coin. After that you can see that every coin is identified.

Next, a(6) = 2. The first weighing, 1 + 2 + 3 = 6, divides all coins into three groups: {1,2,3}, {4,5} and {6}. We know to which group each coin belongs, but we do not know which coin in the group is which. The second weighing: 1 + 6 < 3 + 5, identifies every coin. Indeed, the only possibility for the left side to weigh less than the right side is when the smallest weighing coin from the first group and 6 are on the left, and the two largest weighing coins from the first two groups are on the right.

The Lower Bound and n = 10, n = 11

When I was writing my essay I suspected that n = 6 is the largest number for which a solution can be established in two weighings, but I didn’t have any proof. So I was embarrassed to show my solutions of three weighings n equals 7, 8 and 9.

On the other hand I published the solutions suggested by my son, Alexey Radul, for n = 10 and n = 11. In these cases the theoretical lower bound of log₃(n) for a(n) is equal to 3, and finding solutions in three weighings was enough to establish the value of the sequence a(n) for n = 10 and n = 11.

So, a(10) = 3, and here are the weighings. The first weighing is 1 + 2 + 3 + 4 = 10. After this weighing, we can divide the coins into three groups {1,2,3,4}, {5,6,7,8,9} and {10}. The second weighing is 1 + 5 + 10 < 8 + 9. After the second weighing we can divide all coins into groups we know they belong to: {1}, {2,3,4}, {5}, {6,7}, {8,9} and {10}. The last weighing contains the lowest weighing coin from each non-single-coin group on the left and the largest weighing coin on the right, plus, in order to balance them, the coins whose weights we know. The last weighing is 2 + 6 + 8 + 5 = 4 + 7 + 9 + 1.

Similarly, a(11) = 3, and the weighings are: 1 + 2 + 3 + 4 < 11; 1 + 2 + 5 + 11 = 9 + 10; 6 + 9 + 1 + 3 = 8 + 4 + 2 + 5.

An Exhaustive Search and a Mystery Solution for n = 6

After publishing my blog I wrote a letter to the Sequence Fans mailing list asking them to expand the sequence. Max Alekseyev replied with the results of an exhaustive search program he wrote. First of all, he found a counter-intuitive solution for n=6. Namely, the following two weighings: 1 + 3 < 5 and 1 + 2+ 5 < 3 + 6. He also confirmed that it is not possible to identify the coins in two weighings for n=7, n=8 and n=9.

Many Interesting Examples for n = 7

So now I can stop being embarrassed and proudly present my solution for n=7 in three weighings. That is, a(7) = 3 and the first weighing is: 1+2+3 < 7, and it divides all the coins into three groups {1,2,3}, {4,5,6} and 7. The second weighing, 1 + 4 < 6, divides them even further. Now we know the identity of every coin except the group {2,3}, which we can disambiguate with the third weighing: 2 < 3.

In many solutions that I’ve seen, one of the weighings was very special: every coin on one cup was lighter than every coin on the other cup. I wondered if that was always the case. Konstantin Knop send me a counterexample for n=7. The first weighing is: 1 + 2 + 3 + 5 = 4 + 7. The second is: 1 + 2 + 4 < 3 + 5. The third is: 1 + 3 + 4 = 2 + 6.

Later Max Alekseyev sent me two more special solutions for n=7. The first one contains only equalities: 2 + 5 = 7; 1 + 2 + 4 = 7; 1 + 2 + 3 + 5 = 4 + 7. The second one contains only inequalities: 1 + 3 < 5; 1 + 2 + 5 < 3 + 6; 5 + 6 < 2 + 3 + 7.

n = 8

Moving to the next index, a(8) = 3 and the first weighing is: 1 + 2 + 3 + 4 + 5 < 7 + 8. The second weighing is: 1 + 2 + 5 < 4 + 6. After that we have identified all coins but two groups {1,2} and {3,4} that can be resolved by 2 + 4 = 6.

More Examples and a Paper

Meanwhile my blog received a comment from Konstantin Knop who claimed that he found solutions in three weighings for n in the range between 12 and 17 inclusive and four weighings for n = 53. I had already corresponded with Konstantin and knew that his claims are always well-founded, so I didn’t doubt that he had found the solutions.

Later I began to write a paper with Joel Lewis on the upper bound of the omni-sequence, where we prove that a(n) ≤ 2 ⌈log₂n⌉. For this paper, we wanted a comprehensive set of examples, so I emailed Konstantin asking him to write up his solutions. He promptly sent me the results and mentioned that he had found the weighings together with Ilya Bogdanov. They used several different ideas in the solutions. First I’ll describe their solutions based on ideas we’ve already seen, namely to compare the lightest coins in the range to the heaviest coins.

n = 13 and n = 15

Here is the proof that a(13) = 3. The first weighing is: 1 + … + 8 = 11 + 12 + 13, and it identifies the groups {1, 2, 3, 4, 5, 6, 7, 8}, {9, 10} and {11, 12, 13}. The second weighing is: (1 + 2 + 3) + 9 + (11 + 12) = (7 + 8) + 10 + 13, and it divides them further into groups {1, 2, 3}, {4, 5, 6}, {7, 8}, {9}, {10}, {11, 12}, {13}. And the last weighing identifies all the coins: 1 + 4 + 7 + 11 + 9 + 10 = 3 + 6 + 8 + 12 + 13.

Similarly, let us show that a(15) = 3. The first weighing is: 1 + … + 7 < 14 + 15, and it divides the coins into three groups {1, 2, 3, 4, 5, 6, 7}, {8, 9, 10, 11, 12, 13}, and {14, 15}. The second weighing is: (1 + 2 + 3) + 8 + (14 + 15) = (5 + 6 + 7) + (12 + 13), and this divides them further into groups {1, 2, 3}, {4}, {5, 6, 7}, {8}, {9, 10, 11}, {12, 13} and {14, 15}. The third weighing identifies every coin: 1 + 5 + 8 + 9 + 12 + 14 = 3 + 7 + 11 + 13 + 15.

n = 9 and n = 12: Heaviest vs Lightest. Almost, but not Quite

As I mentioned earlier it is not always possible to find the first weighing which will nicely divide the coins into groups. We already discussed an example, n = 5, in which neither of the two weighings divided the coins into groups. Likewise, the same thing happened in the second mysterious solution for n = 6. What these solutions have in common is that the first weighing nearly divides everything nicely. The left pan is almost the set of the lightest coins and the right pan is almost the set of the heaviest coins. But not quite.

That is not our only situation in which the first weighing does not quite divide the coins into groups. For example, here is Konstantin’s solution for a(9) = 3. For the first weighing, we put five coins on the left pan and two coins on the right pan. The left pan is lighter. This could happen in three different ways:

1. 1 + 2 + 3 + 4 + 5 < 8 + 9 (out 6 and 7)
2. 1 + 2 + 3 + 4 + 5 < 7 + 9 (out 6 and 8)
3. 1 + 2 + 3 + 4 + 6 < 8 + 9 (out 5 and 7)

The second weighing, 1 + 2 + 3 = 6, in which we took three coins from the left pan and balanced them against one coin – again from the left pan – could only happen in case “C.” After the two weighings, the following groups were identified: {1, 2, 3}, {4}, {5, 7}, {6}, {8, 9}. The third weighing, 1 + 4 + 5 + 8 < 3 + 7 + 9, identifies all the coins.

A similar technique is used in the solution that Konstantin sent to us to demonstrate that a(12) = 3. The first weighing is: 1 + 2 + 3 + 4 + 5 + 6 < 10 + 12. The audience which sees the results of the weighings understands that there are three possibilities for the distribution of coins:

1. 1 + 2 + 3 + 4 + 5 + 6 < 10 + 12
2. 1 + 2 + 3 + 4 + 5 + 6 < 11 + 12
3. 1 + 2 + 3 + 4 + 5 + 7 < 11 + 12

The second weighing, (1 + 2 + 3) + (7 + 8) + 10 < (9 + 11 ) + 12, convinces the audience that the left pan must weigh at least 31 if the first weighing was case “A” above (31 = 1 + 2 + 3 + 7 + 8 + 10) or “C” (31 = 1 + 2 + 3 + 6 + 8 + 11), and at least 32 (32 = 1 + 2 + 3 + 7 + 8 + 11) if the first weighing was case “B.” At the same time the right pan is not more than 12 + 9 + 11 = 32 for case “A” above, not more than 12 + 9 + 10 = 31 for case “B” and not more than 12 + 9 + 10 = 31 for case “C.”

Hence the inequality in the second weighing is only possible when the first weighing was indeed as described by case “A” above. Consequently, the first two weighings together identify groups: {1, 2, 3}, {4, 5, 6}, {7, 8}, {9}, {10}, {11} and {12}. The third weighing, 1 + 4 + 7 + 11 + 12 < 3 + 6 + 8 + 9 + 10, identifies all the coins.

Rearrangement Inequality: n = 6, n = 14, n = 16, n = 17 and n = 53

Other cases that Konstantin Knop sent me used a completely different technique. I would like to explain this technique using the mysterious solution for n = 6 found by Max Alekseyev. Suppose we have six coins labeled c₁, … c₆. The first weighing is: c₁ + c₃ < c₅. The second weighing is: c₁ + c₂ + c₅ < c₃ + c₆.

Let us prove that these two weighings identify all the coins. Let us replace the two inequalities above with the following: c₁ + c₃ − c₅ ≤ −1, and c₁ + c₂ + c₅ − c₃ − c₆ ≤ −1. Now we multiply the first inequality by 3 and the second by 2 and sum the results. We get: 5c₁ + 2c₂ + c₃ + 0c₄ − c₅ − 2c₆ ≤ −5. Note that the coefficients for labels are in a decreasing order. By the rearrangement inequality the smallest value the expression 5c₁ + 2c₂ + c₃ + 0c₄ − c₅ − 2c₆ reaches is when the labels on the coins match the indices. This smallest value is −5. Hence, the labels have to match the coins.

The technique that Konstantin and his collaborators are using is to search for appropriate coefficients to multiply the weighings by, rather than searching for the weighings themselves. In lieu of lengthy explanations, I will just list the weighings that he uses together with coefficients to multiply them by for their proof that the weighings differentiate coins.

We will start with showing that a(14) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 < 11 + 13 + 14, and: 1 + 2 + 3 + 8 + 11 + 13 = 7 + 9 + 10 + 12, followed by 1 + 4 + 7 + 10 = 3 + 6 + 13. The coefficients to multiply by are {9, 5, 2}.

Next we will show that a(16) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 8 < 14 + 16, and 1 + 2 + 3 + 7 + 9 + 14 = 8 + 13 + 15, followed by 1 + 4 + 7 + 10 + 13 < 3 + 6 + 12 + 15. The coefficients to multiply by are {11, 5, 2}.

Next we will show that a(17) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 9 + 10 < 15 + 16 + 17, and 1 + 2 + 3 + 8 + 11 + 15 + 16 < 7 + 9 + 10 + 14 + 17, and 1 + 4 + 7 + 8 + 12 + 14 = 3 + 6 + 10 + 11 + 16. The coefficients to multiply by are {11, 5, 2}.

Next we will show that a(53) = 4. The weighings are: (1 + 2 + … + 23) + 25 < 47 + (49 + … + 53), and (1 + … + 9) + 24 + (26+ … + 31) + 47 + (49 + … + 52) < (16 + … + 23) + 25 + (41 + … + 46) + 48 + (51 + 52), and (1 + 2 + 3) + (10 + 11) + (16 + 17 + 18) + 24 + (26 + 27) + (32 + 33 + 34) + (41 + 42 + 43) + 47 + 49 + 53 =(7 + 8 + 9) + 15 + (22 + 23) + 25 + (30 + 31) + (38 + 39) + 40 + (45 + 46) + 48 + (51 + 52), and the last one 1 + 4 + 7 + 10 + 12 + 16 + 19 + 22 + 24 + 28 + 30 + 32 + 35 + 38 + 41 + 45 + 47 + 51 + 53 < 3 + 6 + 9 + 11 + 14 + 18 + 21 + 25 + 27 + 29 + 34 + 37 + 40 + 43 + 48 + 49 + 50 + 52. The coefficients to multiply by are {43, 15, 5, 2}.

The Search Continues for n = 18 and n = 19

When I was working on the paper with Joel Lewis I re-established my email discussions about the Baron’s onmi-sequence with Konstantin Knop. At that time Konstantin’s colleague, Maxim Kalenkov, got interested in the subject and wrote a computer search program to find other solutions that can be proven with the rearrangement inequality. Thus, we know two more terms of this sequence.

The next known term is a(18) = 3. The weighings are: 1 + 2 + 4 + 5 + 7 + 10 + 12 = 9 + 15 + 17, and 1 + 3 + 4 + 6 + 9 + 11 + 17 = 7 + 12 + 14 + 18, and 2 + 3 + 7 + 8 + 9 + 14 + 15 = 4 + 10 + 11 + 16 + 17. The corresponding coefficients are: {8, 7, 5}.

Similarly, a(19) = 3. The weighings are: 1 + 2 + 3 + 4 + 5 + 7 + 8 + 10 + 13 = 16 + 18 + 19, and 1 + 2 + 3 + 6 + 9 + 11 + 16 = 8 + 10 + 13 + 17, and 1 + 4 + 6 + 8 + 12 + 18 = 3 + 7 + 11 + 13 + 15. The coefficients are {12, 7, 3}.

Solutions in Four Weighing for n from 20 to 58

Maxim Kalenkov continued his search. He didn’t find any new solutions in three weighings, but he found a lot of solutions in four weighings, namely for numbers from 20 to 58. Below are his solutions, with multiplier coefficients in front of every weighing:

a(20) ≤ 4
18: 1+2+3+4+5+10+14+16+18 = 6+7+11+12+17+20
19: 1+2+4+5+12+15+17+19 < 6+8+10+14+18+20
21: 2+6+11+17+18 = 4+9+10+15+16
26: 1+6+7+8+9+10+20 = 2+5+17+18+19

a(21) ≤ 4
18: 3+5+6+11+15+17+19 = 7+8+9+13+18+21
19: 4+6+9+13+16+18+20 = 1+7+11+12+15+19+21
21: 1+4+5+7+12+18+19 = 3+9+10+11+16+17
26: 1+2+3+7+8+9+10+11+21 = 4+5+6+18+19+20

a(22) ≤ 4
18: 3+5+6+12+15+17+20 = 7+8+10+13+18+22
19: 1+2+4+10+13+16+18+21 = 7+9+12+15+20+22
21: 1+6+7+18+19+20 = 2+3+10+11+12+16+17
26: 2+3+7+8+9+10+11+12+22 = 6+18+19+20+21

a(22) ≤ 4
18: 1+2+5+6+12+16+18+22 < 3+7+8+10+13+19+23
19: 1+3+4+6+10+17+19+21 = 7+9+12+14+16+23
21: 3+7+13+14+19+20 = 2+6+10+11+12+17+18
26: 2+7+8+9+10+11+12+23 = 19+20+21+22

a(24) ≤ 4
18: 1+3+6+12+17+19+21+23 < 2+4+7+8+10+13+15+20+24
19: 1+2+4+5+6+10+15+18+20+22 < 7+9+12+14+17+21+24
21: 4+7+13+14+20+21 = 3+6+10+11+12+18+19
26: 2+3+7+8+9+10+11+12+24 = 20+21+22+23

a(25) ≤ 4
18: 1+2+3+5+6+8+9+14+17+19+22 < 10+12+16+20+24+25
19: 2+6+7+9+12+16+18+20+23 = 10+11+14+15+17+22+24
21: 1+2+4+7+8+10+15+20+21+22 = 3+6+12+13+14+18+19+25
26: 3+10+11+12+13+14+24+25 = 2+7+8+9+20+21+22+23

a(26) ≤ 4
18: 1+2+3+5+6+8+9+14+18+20+23 = 10+12+15+21+25+26
19: 2+3+4+6+7+9+12+19+21+24 = 11+14+16+18+23+25
21: 7+8+15+16+21+22+23 = 2+6+12+13+14+19+20+26
26: 1+2+10+11+12+13+14+25+26 = 7+8+9+21+22+23+24

a(27) ≤ 4
18: 1+3+4+6+7+8+9+14+19+21+23+25 < 10+11+13+15+17+22+26+27
19: 1+2+3+5+7+9+13+17+20+22+24 < 4+10+12+14+16+19+23+26
21: 2+3+4+8+10+15+16+22+23 = 1+7+13+14+20+21+27
26: 1+10+11+12+13+14+26+27 = 3+8+9+22+23+24+25

a(28) = 4
18: 3+6+8+9+10+15+19+21+24+26 = 1+5+11+13+16+18+22+27+28
19: 1+4+5+7+9+10+13+18+20+22+25 = 3+6+11+12+15+17+19+24+27
21: 5+6+11+16+17+22+23+24 = 4+9+13+14+15+20+21+28
26: 1+2+3+4+11+12+13+14+15+27+28 = 10+22+23+24+25+26

a(29) = 4
18: 1+3+5+6+7+9+10+16+20+22+25+27 < 11+12+14+17+18+23+28+29
19: 4+8+10+14+18+21+23+26 = 2+3+6+11+13+16+20+25+28
21: 1+2+6+8+9+11+17+23+24+25 = 4+5+14+15+16+21+22+29
26: 2+3+4+5+11+12+13+14+15+16+28+29 = 8+9+10+23+24+25+26+27

a(30) = 4
18: 2+8+10+16+21+23+26+27+28 = 5+11+12+14+17+19+24+29+30
19: 2+4+5+7+9+14+19+22+24+28 = 11+13+16+18+21+26+29
21: 1+5+6+9+10+11+17+18+24+25+26 = 4+14+15+16+22+23+28+30
26: 1+3+4+11+12+13+14+15+16+29+30 < 9+10+24+25+26+27+28

a(31) = 4
18: 1+2+6+9+10+16+21+23+26+28+29 < 3+4+7+11+12+14+17+19+24+30+31
19: 1+2+4+7+14+19+22+24+27+29 < 6+9+11+13+16+18+21+26+30
21: 2+3+7+8+9+11+17+18+24+25+26 = 14+15+16+22+23+29+31
26: 1+3+4+5+6+11+12+13+14+15+16+30+31 = 2+24+25+26+27+28+29

a(32) = 4
18: 1+5+8+9+10+12+13+22+24+27+29 = 6+14+16+18+20+25+30+31
19: 4+6+10+11+13+16+20+23+25+28 = 1+2+8+15+19+22+27+30+32
21: 1+2+6+7+8+11+12+18+19+25+26+27 = 4+5+10+16+17+23+24+31+32
26: 1+2+3+4+5+14+15+16+17+30+31+32 < 11+12+13+25+26+27+28+29

a(33) = 4
18: 1+2+6+7+8+9+10+12+13+23+27+29+30 = 3+14+15+17+19+21+25+31+32
19: 1+2+10+11+13+17+21+24+25+28+30 = 4+6+8+14+16+20+23+27+31+33
21: 1+3+4+8+11+12+14+19+20+25+26+27 < 7+10+17+18+24+30+32+33
26: 3+4+5+6+7+14+15+16+17+18+31+32+33 = 11+12+13+25+26+27+28+29+30

a(34) = 4
18: 2+3+4+8+10+12+13+19+24+28+30+31 < 6+14+15+17+20+22+26+32+33
19: 1+2+3+5+6+9+11+13+17+22+25+26+29+31 = 4+8+14+16+19+21+24+28+32+34
21: 1+3+6+7+8+11+12+14+20+21+26+27+28 = 2+5+17+18+19+25+31+33+34
26: 1+2+4+5+14+15+16+17+18+19+32+33+34 = 3+11+12+13+26+27+28+29+30+31

a(35) = 4
18: 1+3+4+6+8+10+11+13+19+24+26+29+31+32 = 14+15+17+20+22+27+33+34+35
19: 1+4+7+9+11+12+17+22+25+27+30+32 = 6+14+16+19+21+24+29+33+35
21: 2+12+13+14+20+21+27+28+29+35 = 4+7+8+11+17+18+19+25+26+32+34
26: 1+2+3+4+5+6+7+8+14+15+16+17+18+19+33+34 = 12+13+27+28+29+30+31+32

a(36) = 4
18: 1+2+3+4+5+9+11+12+14+15+20+25+29+31+32 < 6+16+18+21+23+27+33+34+36
19: 1+2+4+5+6+8+10+12+13+15+18+23+26+27+30+32 < 16+17+20+22+25+29+33+35+36
21: 1+3+5+13+14+16+21+22+27+28+29+36 = 2+8+9+12+18+19+20+26+32+34+35
26: 2+6+7+8+9+16+17+18+19+20+33+34+35 = 5+13+14+15+27+28+29+30+31+32

a(37) = 4
18: 1+2+3+6+8+10+12+13+15+16+21+27+30+32+33 = 4+9+17+19+22+24+28+34+35+37
19: 1+2+3+7+9+11+13+14+16+19+24+26+28+31+33 = 5+6+10+17+18+21+23+30+34+36+37
21: 3+4+5+9+10+14+15+17+22+23+28+29+30+37 = 1+7+8+13+19+20+21+26+27+33+35+36
26: 1+4+5+6+7+8+17+18+19+20+21+34+35+36 = 3+14+15+16+28+29+30+31+32+33

a(38) = 4
18: 2+3+4+7+9+11+13+15+16+21+26+28+31+33+34 = 5+10+17+18+19+22+24+29+35+36+38
19: 1+3+4+8+10+12+13+14+16+19+24+27+29+32+34 = 7+11+17+21+23+26+31+35+37+38
21: 1+2+4+5+10+11+14+15+17+22+23+29+30+31+38 = 8+9+13+19+20+21+27+28+34+36+37
26: 5+6+7+8+9+17+18+19+20+21+35+36+37 = 4+14+15+16+29+30+31+32+33+34

a(39) = 4
18: 1+2+4+7+9+11+13+14+16+22+27+29+32+34+35 = 10+17+18+20+23+25+30+36+38+39
19: 2+3+4+8+10+12+14+15+20+25+28+30+33+35 = 5+7+11+17+19+22+24+27+32+37+38
21: 1+2+3+5+10+11+15+16+17+23+24+30+31+32+38 < 8+9+14+20+21+22+28+29+35+36+37
26: 1+5+6+7+8+9+17+18+19+20+21+22+36+37 = 15+16+30+31+32+33+34+35

a(40) = 4
18: 1+2+3+4+5+8+9+12+14+15+17+18+23+27+29+32+34+35 < 7+10+19+21+24+26+30+36+37+39+40
19: 1+3+4+5+7+10+13+15+16+18+21+26+28+30+33+35 < 6+8+12+20+23+25+27+32+36+38+39
21: 1+5+6+10+11+12+16+17+24+25+30+31+32+39 < 3+9+15+21+22+23+28+29+35+37+38
26: 2+3+6+7+8+9+19+20+21+22+23+36+37+38 = 5+16+17+18+30+31+32+33+34+35

a(41) = 4
18: 1+3+5+6+8+10+12+14+15+17+18+23+28+30+33+35+36 < 7+11+19+21+24+26+31+37+38+40+41
19: 1+2+4+5+6+7+9+11+13+15+16+18+21+26+29+31+34+36 = 8+12+19+20+23+25+28+33+37+39+40
21: 1+4+6+11+12+16+17+19+24+25+31+32+33+40 < 9+10+15+21+22+23+29+30+36+38+39
26: 2+3+7+8+9+10+19+20+21+22+23+37+38+39 = 6+16+17+18+31+32+33+34+35+36

a(42) = 4
18: 1+3+5+6+7+11+13+15+16+18+24+29+31+34+36+37 = 2+8+12+19+20+22+25+27+32+38+40+41
19: 1+2+4+6+7+10+12+14+16+17+18+22+27+30+32+35+37 = 3+13+19+21+24+26+29+34+39+40+42
21: 1+2+3+4+5+7+8+12+13+17+19+25+26+32+33+34+40 = 10+11+16+22+23+24+30+31+37+38+39
26: 2+3+8+9+10+11+19+20+21+22+23+24+38+39 = 7+17+18+32+33+34+35+36+37

a(43) = 4
18: 1+2+5+6+7+10+12+14+16+17+19+20+29+31+34+36+37 = 8+21+23+25+27+32+38+39+41+42
19: 2+4+5+6+7+8+11+15+17+18+20+23+27+30+32+35+37 = 10+14+22+26+29+34+38+40+41+43
21: 1+2+3+7+13+14+18+19+25+26+32+33+34+41 < 5+11+12+17+23+24+30+31+37+39+40
26: 1+3+4+5+8+9+10+11+12+21+22+23+24+38+39+40 < 7+18+19+20+32+33+34+35+36+37

a(44) = 4
18: 1+2+5+6+7+8+10+11+14+16+17+19+20+25+30+32+35+37+38 = 3+12+21+22+23+26+28+33+39+40+42+44
19: 1+2+3+7+8+12+15+17+18+20+23+28+31+33+36+38+44 = 9+10+14+21+25+27+30+35+39+41+42+43
21: 2+3+4+6+8+9+12+13+14+18+19+21+26+27+33+34+35+42 = 11+17+23+24+25+31+32+38+40+41+44
26: 1+3+4+5+9+10+11+21+22+23+24+25+39+40+41 = 8+18+19+20+33+34+35+36+37+38

a(45) = 4
18: 2+4+5+6+11+13+16+17+18+20+21+26+31+33+36+38+39 = 7+9+14+22+24+27+29+34+40+42+43+45
19: 1+2+4+6+9+12+14+18+19+21+24+29+32+34+37+39+45 = 8+11+16+23+26+28+31+36+40+41+42+44
21: 1+2+3+5+7+8+14+15+16+19+20+27+28+34+35+36+42 = 4+12+13+18+24+25+26+32+33+39+41+45
26: 1+3+4+7+8+9+10+11+12+13+22+23+24+25+26+40+41 = 19+20+21+34+35+36+37+38+39

a(46) = 4
18: 1+2+3+5+6+8+9+14+16+17+19+21+22+26+31+33+36+38+39 = 10+12+23+27+29+34+40+41+42+43+45
19: 2+4+6+7+8+9+12+15+18+20+22+29+32+34+37+39+45 = 3+11+14+17+23+24+26+28+31+36+40+42+44
21: 1+3+7+9+10+11+17+20+21+23+27+28+34+35+36+42 = 6+15+16+25+26+32+33+39+41+45+46
26: 1+2+3+4+5+6+10+11+12+13+14+15+16+23+24+25+26+40+41 = 9+20+21+22+34+35+36+37+38+39

a(47) = 4
18: 2+3+5+7+8+9+13+14+16+18+19+21+22+27+32+34+37+39+40 < 11+23+24+28+30+35+41+42+43+44+46
19: 1+3+6+7+8+9+11+17+19+20+22+30+33+35+38+40+46 < 5+10+13+16+23+25+27+29+32+37+41+43+45
21: 1+2+4+5+9+10+15+16+20+21+23+28+29+35+36+37+43 < 7+14+19+26+27+33+34+40+42+46+47
26: 1+2+3+4+5+6+7+10+11+12+13+14+23+24+25+26+27+41+42 < 9+20+21+22+35+36+37+38+39+40

a(48) = 4
18: 3+5+6+7+8+13+17+19+20+22+23+28+33+35+38+40+41 < 9+11+15+24+26+29+31+36+42+44+45+47
19: 1+4+6+8+11+14+15+18+20+21+23+26+31+34+36+39+41+47 < 3+10+13+17+24+25+28+30+33+38+42+43+44+46
21: 1+2+3+7+8+9+10+15+16+17+21+22+24+29+30+36+37+38+44 = 6+14+20+26+27+28+34+35+41+43+47+48
26: 1+2+3+4+5+6+9+10+11+12+13+14+24+25+26+27+28+42+43 = 8+21+22+23+36+37+38+39+40+41

a(49) = 4
18: 2+3+6+7+8+9+10+15+18+20+21+23+24+29+34+38+40+41+49 < 12+16+25+26+30+32+36+42+43+44+45+47
19: 1+3+5+7+9+10+12+14+16+19+21+22+24+32+35+36+39+41+47 < 11+18+25+27+29+31+34+38+42+44+46+49
21: 1+2+3+4+8+10+11+16+17+18+22+23+25+30+31+36+37+38+44 < 7+14+15+21+28+29+35+41+43+47+48+49
26: 1+2+4+5+6+7+11+12+13+14+15+25+26+27+28+29+42+43 = 10+22+23+24+36+37+38+39+40+41

a(50) = 4
18: 1+2+3+4+6+7+9+10+11+15+16+19+20+21+23+24+34+36+39+41+42+50 = 12+17+25+26+28+30+32+37+43+44+45+46+48
19: 2+3+5+7+8+10+11+17+21+22+24+28+32+35+37+40+42+48 = 4+13+15+19+25+27+31+34+39+43+45+47+50
21: 1+3+4+8+9+11+12+13+17+18+19+22+23+25+30+31+37+38+39+45 = 7+16+21+28+29+35+36+42+44+48+49+50
26: 1+2+4+5+6+7+12+13+14+15+16+25+26+27+28+29+43+44 = 11+22+23+24+37+38+39+40+41+42

a(51) = 4
18: 2+3+4+6+8+10+11+15+17+19+20+21+23+24+30+35+37+40+42+43+50 < 12+13+18+25+26+28+31+33+38+44+46+47+49+51
19: 1+3+4+7+9+11+13+16+18+21+22+24+28+33+36+38+41+43+49 < 6+15+19+25+27+30+32+35+40+45+46+48+50
21: 1+2+4+5+6+9+10+11+12+18+19+22+23+25+31+32+38+39+40+46+51 < 16+17+21+28+29+30+36+37+43+44+45+49+50
26: 1+2+3+5+6+7+8+12+13+14+15+16+17+25+26+27+28+29+30+44+45 < 11+22+23+24+38+39+40+41+42+43+51

a(52) = 4
18: 2+5+7+8+10+11+12+17+19+22+25+26+31+35+37+40+42+43+51 = 3+13+15+20+27+28+29+32+38+44+46+47+49+52
19: 1+2+3+6+8+9+11+12+15+18+20+23+24+26+29+36+38+41+43+49 = 5+14+17+22+27+31+33+35+40+45+46+48+51
21: 1+3+4+5+9+10+12+13+14+20+21+22+24+25+27+32+33+38+39+40+46+52 = 8+18+19+29+30+31+36+37+43+44+45+49+50+51
26: 1+2+3+4+5+6+7+8+13+14+15+16+17+18+19+27+28+29+30+31+44+45 = 12+24+25+26+38+39+40+41+42+43+52

a(53) = 4
18: 2+3+4+7+8+9+10+11+12+17+19+21+23+25+26+31+36+38+41+43+44+52 < 5+13+15+27+29+32+34+39+45+46+47+48+50+53
19: 1+3+4+5+9+11+12+15+18+22+23+24+26+29+34+37+39+42+44+50 = 7+14+17+21+27+28+31+33+36+41+45+47+49+52
21: 1+2+4+5+6+7+10+12+13+14+20+21+24+25+27+32+33+39+40+41+47+53 < 9+18+19+23+29+30+31+37+38+44+46+50+51+52
26: 1+2+3+5+6+7+8+9+13+14+15+16+17+18+19+27+28+29+30+31+45+46 = 12+24+25+26+39+40+41+42+43+44+53

a(54) = 4
18: 2+3+4+6+8+9+11+12+13+18+20+23+25+26+28+29+33+37+39+41+42+43+51 = 5+14+16+21+30+31+32+35+44+45+47+48+49+52+54
19: 1+3+4+5+7+9+10+12+13+16+19+21+24+26+27+29+32+35+38+43+49+54 < 6+15+18+23+30+33+34+37+41+44+46+47+51+53
21: 1+2+4+5+6+10+11+13+14+15+21+22+23+27+28+30+34+40+41+47+52+53 < 9+19+20+26+32+33+38+39+43+45+46+49+50+51
26: 1+2+3+5+6+7+8+9+14+15+16+17+18+19+20+30+31+32+33+44+45+46 < 13+27+28+29+40+41+42+43+52+53+54

a(55) = 4
18: 2+3+6+8+9+11+12+13+18+19+22+24+25+27+28+32+37+39+42+44+45+54 < 4+14+16+20+29+31+33+35+40+46+47+49+50+52+55
19: 1+2+3+4+7+9+10+12+13+16+20+23+25+26+28+31+35+38+40+43+45+52 < 6+15+18+22+30+32+34+37+42+46+48+49+51+54
21: 1+3+4+5+6+10+11+13+14+15+20+21+22+26+27+33+34+40+41+42+49+55 = 9+19+25+31+32+38+39+45+47+48+52+53+54
26: 1+2+4+5+6+7+8+9+14+15+16+17+18+19+29+30+31+32+46+47+48 = 13+26+27+28+40+41+42+43+44+45+55

a(56) = 4
18: 2+3+4+7+9+10+12+13+14+18+20+23+25+26+28+34+39+41+44+46+47+55 < 5+15+16+21+29+30+32+35+37+42+48+50+52+53+56
19: 1+3+4+5+8+10+11+13+14+16+19+21+24+26+27+28+32+37+40+42+45+47+52 < 7+18+23+29+31+34+36+39+44+49+51+54+55+56
21: 1+2+4+5+6+7+11+12+14+15+21+22+23+27+29+35+36+42+43+44+53+54 < 10+19+20+26+32+33+34+40+41+47+48+49+52+56
26: 1+2+3+5+6+7+8+9+10+15+16+17+18+19+20+29+30+31+32+33+34+48+49+56 = 14+27+28+42+43+44+45+46+47+53+54+55

a(57) = 4
18: 2+3+4+7+9+10+12+14+18+19+22+24+27+32+35+36+39+43+45+49+51 < 5+13+16+21+26+28+31+34+38+41+42+48+50+53+56
21: 1+3+4+5+8+10+11+14+16+18+20+21+25+29+31+35+38+40+41+46+51+53+57 < 7+15+19+24+26+30+36+37+39+42+45+47+48+52+55+56
25: 1+2+4+5+6+7+11+12+13+15+18+21+23+24+26+29+32+34+37+41+44+45+48+55 = 10+20+22+31+33+36+40+43+47+51+53+54+56+57
33: 1+2+3+5+6+7+8+9+10+13+15+16+17+19+20+22+26+28+30+31+33+36+42+47+56 = 18+29+32+35+41+44+45+46+49+51+55+57

a(58) = 4
17: 2+3+4+8+9+10+12+13+14+21+22+25+26+27+29+30+37+42+43+45+46+47+56 < 5+15+16+20+31+32+33+35+36+41+48+49+51+52+53+55
20: 1+3+4+5+7+10+11+13+14+16+19+20+24+27+28+30+33+36+40+41+44+47+53 = 8+17+21+25+31+37+38+42+45+48+50+51+56+57
21: 1+2+4+5+6+8+11+12+14+15+17+20+23+25+28+29+31+35+38+41+45+51+55+57 < 10+19+22+27+33+34+37+40+43+47+49+50+53+54+56
26: 1+2+3+5+6+7+8+9+10+15+16+17+18+19+21+22+31+32+33+34+37+48+49+50 < 14+28+29+30+41+44+45+46+47+55+57+58

When the Abel Prize was announced in 2001, I got very excited and started wondering who would be the first person to get it. I asked my friends and colleagues who they thought was the greatest mathematician alive. I got the same answer from every person I asked: Alexander Grothendieck. Well, Alexander Grothendieck is not the easiest kind of person to give a prize to, since he rejected the mathematical community and lives in seclusion.

Years later I told this story to my friend Ingrid Daubechies. She pointed out to me that my spontaneous poll was extremely biased. Indeed, I was asking only Russian mathematicians living abroad who belonged to “Gelfand’s school.” Even so, the unanimity of those responses continues to amaze me.

Now several years have passed and it does not seem that Alexander Grothendieck will be awarded the Prize. Sadly, my advisor Israel Gelfand died without getting the Prize either. I am sure I am biased with respect to Gelfand. He was extremely famous in Soviet Russia, although less well-known outside, which may have affected the decision of the Abel’s committee.

I decided to assign some non-subjective numbers to the fame of Gelfand and Grothendieck. On Pi Day, March 14, 2010, I checked the number of Google hits for these two men. All the Google hits in the rest of this essay were obtained on the same day, using only the full names inside quotation marks.

• Alexander Grothendieck — 95,600
• Israel Gelfand — 47,900

Google hits do not give us a scientific measurement. If the name is very common, the results will be inflated because they will include hits on other people. On the other hand, if a person has different spellings of their name, the results may be diminished. Also, people who worked in countries with a different alphabet are at a big disadvantage. I tried the Google hits for the complete Russian spelling of Gelfand: “Израиль Моисеевич Гельфанд” and got an impressive 137,000.

Now I want to compare these numbers to the Abel Prize winners’ hits. Here we have another problem. As soon as a person gets a prize, s/he becomes more famous and the number of hits increases. It would be interesting to collect the hits before the prize winner is announced and then to compare that number to the results after the prize announcement and see how much it increases. For this endeavor, the researcher needs to know who the winner is in advance or to collect the data for all the likely candidates.

• Jean-Pierre Serre — 63,400
• Michael Atiyah — 34,200
• Isadore Singer — 44,300
• Peter Lax — 118,000
• Lennart Carleson — 47,500
• Srinivasa Varadhan — 15,800
• John Thompson — 1,610,000
• Jacques Tits — 90,900
• Mikhail Gromov — 61,900

John Thompson is way beyond everyone else’s range because he shares his name with a famous basketball coach. But my point is that Gelfand and Grothendieck could have been perfect additions to this list.

I have this fun book at home written by Clifford Pickover and titled Wonders of Numbers: Adventures in Mathematics, Mind, and Meaning. It was published before the first Abel Prize was awarded. Chapter 38 of this book is called “A Ranking of the 10 Most Influential Mathematicians Alive Today.” The chapter is based on surveys and interviews with mathematicians.

The most puzzling thing about this list is that there is no overlap with the Abel Prize winners. Here is the list with the corresponding Google hits.

1. Andrew Wiles — 64,900
2. Donald Coxeter — 25,200
3. Roger Penrose — 214,000
4. Edward Witten — 45,700
5. William Thurston — 96,000
6. Stephen Smale — 151,000
7. Robert Langlands — 48,700
8. Michael Freedman — 46,200
9. John Conway — 203,000
10. Alexander Grothendieck — 95,600

Since there are other great mathematicians with a lot of hits, I started trying random names. In the list below, I didn’t include mathematicians who had someone else appear on the first results page of my search. For example, there exists a film director named Richard Stanley. So here are my relatively “clean” results.

• Martin Gardner — 292,000
• Ingrid Daubechies — 76,900
• Timothy Gowers — 90,500
• Persi Diaconis — 84,700
• Michael Sipser — 103,000
• James Harris Simons — 107,000
• Elliott Lieb — 86,100

If prizes were awarded by hits, even when the search is polluted by other people with the same name, then the first five to receive them would have been:

1. John Thompson — 1,610,000
2. Martin Gardner — 292,000
3. Roger Penrose — 214,000
4. John Conway — 203,000
5. Stephen Smale — 151,000

If we had included other languages, then Gelfand might have made the top five with his 48,000 English-language hits plus 137,000 Russian hits.

This may not be the most scientific way to select the greatest living mathematician. That’s why I’m asking you to tell me, in the comments section, who you would vote for.

I started my blog about two year ago. I have written about 200 entries. According to my traffic reports, these have been the top ten most popular entries:

1. The Odd One Out
2. Divisibility by 7 is a Walk on a Graph, by David Wilson
3. The Dirtiest Math Problem Ever (Rated R)
4. My IQ
5. A Miracle Equation
6. Back-to-School Funny Pictures
7. Flexible Zipcar Algorithm
8. A Very Special Ten-Digit Number
9. What Does It Take to Get Accepted by Harvard or Princeton?
10. AMC, AIME, USAMO Contradiction

My most popular category was Math Humor.

Many years ago I conducted an experiment. I asked several sets of friends who had written joint math papers what they thought their individual contributions were. I asked them separately, of course. As the result of this experiment I formulated the conjecture:

The total of what joint authors estimate their contributions to be is always more than 100%.

Here is an actual example of answers I received from the two authors of a joint paper.

Author 1: My contribution is 80%. I suggested a breakthrough idea that made this paper possible. He just typed everything.

Author 2: My contribution is 80%. I did all the work. She just suggested a good idea.

You can see how the answers are synchronized. It is clear that both are telling the truth. People just tend to over-value their own input.

In other cases each author thinks that she or he generated the main idea. It doesn’t mean that one of them is lying. Very often they are absolutely sincere. Take this example of Alice and Bob, who are working on a paper together. Alice suggests that they might have better progress on their theorem if they consider graphs with symmetries first. Bob is engrossed in his thoughts and doesn’t register Alice’s suggestion. Next day, he comes up with an idea to add a group action on graphs. He sincerely believes that this was his own idea. It would be hard to know whether this had been provoked by Alice’s suggestion, or had come to Bob independently. Alice assumes that they are working on her idea.

When you acknowledge other people’s contribution, keep in mind that their perception might be different from yours. If you do not want to hurt other people’s feelings, you might consider inflating your gratitude.

The conjecture doesn’t apply to single-author papers. First of all, mathematicians never claim their contribution is 110% as non-mathematicians do. In many cases, especially when there are acknowledgements in the paper, it would be illogical to claim 100% contribution. Most mathematicians are logical, so if they are gracious enough to acknowledge the help of others, they are unlikely to claim 100%.

I would be curious to continue the experiment and either prove or disprove my conjecture. I’d appreciate your help. If you want to be part of this experiment, you can provide the following numbers in your comments: your average contribution to your own papers; and also your weighted average contribution to your joint papers.

I always thought that the famous equation

10² + 11² + 12² = 13² + 14²

is sort of a miracle, a random fluke. I enjoyed this cute equation, but never really thought about it seriously. Recently, when my son Sergei came home from MOP, he told me that this equation is not a fluke; and I started thinking.

Suppose we want to find five consecutive integers such that the sum of the squares of the first three is equal to the sum of the squares of the last two. Let us denote the middle number by n, which gives us the equation:

(n–2)² + (n–1)² + n² = (n+1)² + (n+2)².

After simplification we get a quadratic equation: n² – 12n = 0, which has two roots, 0 and 12. Plugging n = 0 into the equation above gives us (–2)² + (–1)² + 0² = 1² + 2², which doesn’t look like a miracle at all, but rather like a trivial identity. If we replace n with 12, we get the original miracle equation.

If you looked at how the simplifications were done, you might realize that this would work not only with five integers, but with any odd number of consecutive integers. Suppose we want to find 2k+1 consecutive integers, such that the sum of the squares of the first k+1 is equal to the sum of the squares of the last k. Let us denote the middle number by n. Then finding those integers is equivalent to solving the equation: n² = 2k(k+1)n. This provides us with two solutions: the trivial solution 0, and the non-trivial solution n = 2k(k+1).

So our miracle equation becomes a part of the series. The preceding equation is the well-known Pythagorean triple: 3² + 4² = 5². The next equation is 21² + 22² + 23² +24² = 25² + 26² + 27². The middle numbers in the series are triangular numbers multiplied by four.

Actually, do you know that 10² + 11² + 12² = 13² + 14² = 365, the number of days in a year? Perhaps there are miracles or random flukes after all.