Tanya Khovanova's Math Blog

I valued my previous analog scale: I brought it from Europe and it showed my weight in kilograms.

I don’t remember why, a year ago, I decided to buy a digital scale: after all, my old scale is still functioning. But my new digital scale became an important instrument in my weight loss program.

Now I understand how my old scale and my lazy nature played tricks on my mind. For example, let’s say I decide that as soon as I reach one hundred kilograms (220 pounds), I would do something about it. Some time passes, I step on the scale, and it shows 100 kilograms — and maybe more. Is it more or not quite? If I lean to the right, it looks lower. The scale is not precise. So, I step back and adjust the scale at zero a little bit, to make sure it is not more than zero, but it actually could be slightly less. So I have reached my limit, but the scale’s imprecision allows me to pretend that there is a chance I am not over 100 kilograms, and thus do not have to do anything. More time passes, the scale shows 103 kilograms. I realize that I have been deceiving myself, but then it is too late for a fast fix that would lower my weight below 100. So I push the limit, and decide to wait until 105 kilograms.

My digital scale erased any ambiguity. The scale, however, has its own doubts. When I stand on it, the display flips between two numbers for a while. One of the numbers means no dinner tonight. But at the end the scale calls it: it spits out the final number with a beep. I had already decided that the scale is the boss. The flipping is irrelevant; the decision is irrevocable. If it means no dinner, so be it.

My new scale prevents inaction. It also allowed me to design my new plan: my Yellow Road. In this plan, my target weight decreases by 0.1 pounds per day. My behavior depends on my real weight with respect to my target weight. A small difference changes my behavior. So precision is essential.

As you can see in the picture the plan continues to work. I’ve lost 16 pounds since the start of the plan. Actually, I’ve lost 18 pounds, if I weigh myself without the camera.

I recently posted the following problem from the Moscow Olympiad:

There were n people at a meeting. It appears that any two people at the meeting shared exactly two common acquaintances.

• Prove that all the people have exactly the same number of acquaintances at this meeting.
• Show that n can be greater than 4.

Here is the proof for the first bullet. Choose a person X. Take a pair of X‘s acquaintances. These two acquaintances have to share two acquaintances between themselves one of whom is X. In other words, we have described a function from all pairs of X‘s acquaintances to people who are not X. On the other hand, for every person who is not X, s/he and X share a pair of acquaintances. Hence, there is a bijection between people other than X and all pairs of X‘s acquaintances. If the number of X‘s acquaintances is a, and the total number of people is t, then we have shown that (a choose 2) = t−1. As this is true for any X, we see that everyone has the same number of acquaintances. Moreover, this situation can happen only if t−1 is a triangular number.

But wait. There is more work that needs to be done. The smallest triangular number is 1. That means that t might be 2. If there are two people at the meeting, then the condition holds: they have 0 common acquaintances. The next triangular number is 3. So we need to see what would happen if there are four people. In this case, if everyone knows each other, it works. This is why the second bullet asks us to find an example of the situation with more than four people, because four people is too easy.

Let’s look at larger triangular numbers. The situation described in the problem might also happen when there are:

• 7 people total and everyone has 4 acquaintances,
• 11 people total and everyone has 5 acquaintances,
• 16 people total and everyone has 6 acquaintances,
• and so on: a(a−1)/2 + 1 people total and everyone has a acquaintances.

The official Olympiad solution suggests the following example for 16 people total. Suppose we put 16 people in a square formation so that everyone knows people in the same row and column. I leave it to the reader to check that every two people share exactly two acquaintances.

Let me prove that there is no solution for a total of seven people. If there were a solution, then each person would have to know four people. My first claim is that the acquaintance graph can’t contain a four-clique. Suppose there is a four-clique. Then each person in the clique has to have another acquaintance outside of the clique to make it up to four. In addition, this extra acquaintance can’t be shared with anyone in the clique, because the clique contains all the acquaintances that they share. This means we need to have at least four more people.

Next, suppose two people a and b know each other and share an acquaintance c. Any two people in this group of three has to have another shared acquaintance, who is not shared with the third person. That is, there should be another person who is the acquaintance of a and b, a different person who is an acquaintance of a and c, and a third person who is acquainted with b and c. These three extra people are all the acquaintances of a, b, and c. Which means the last person who is not acquainted with a, b, or c, has less than for four acquaintances.

Let’s look at a more difficult problem that I offered at the same posting:

There were n people at a meeting. It appears that any k people at the meeting shared exactly k common acquaintances.

• Prove that all the people have exactly the same number of acquaintances at this meeting.
• Is it possible that n can be greater than 2k?

As in the previous solution, we see that a, the number of acquaintances of a person and t, the total number of people, satisfy the following equation: (a choose k) = (t−1 choose k−1).

For example, if k = 3, the equation becomes (a choose 3) = (t−1 choose 2). This is a question of finding numbers that are both tetrahedral and triangular. They are known and their sequence, A027568, is finite: 0, 1, 10, 120, 1540, 7140. The corresponding number of acquaintances is 3, 5, 10, 22, 36 and the total number of people is 3, 6, 17, 57, 121. The first trivial example involves 3 people who do not know each other. The next example is also simple: it has 6 people and everyone knows everyone else.

What about non-trivial examples? If there are 17 people in the group, then each person has to know 10 people. Does the acquaintance graph exist so that every group of three people share 3 acquaintances?

We see that the problem consists of two different parts. First, we have to solve the equation that equates two binomial coefficients. And second, we need to build the acquaintance graph. Both questions are difficult. We see that for k = 2 we have an infinite number of solutions to the equation with binomial coefficients. For k = 3, that number is finite. What happens with other k? If there are 2k people and they all know each other, then this works. But are there other non-trivial solutions? I am grateful to Henry Cohn for directing me to the works of Singmaster who studied non-trivial repetitions of numbers in Pascal’s triangle. In particular, Singmaster showed that the equation (n+1 choose k+1) = (n choose k+2) has infinitely many solutions given by n = F_2i+2F_2i+3−1 and k = F_2iF_2i+2−1.

This sequence generates the following non-trivial examples (15 choose 5) = (14 choose 6), (104 choose 39) = (103 choose 40), and so on. That means it might be possible that there is a group of 16 people so that every 6 people share 6 acquaintances. In this situation every person must know everyone else except for one other person. That leads us to the structure of the acquaintance graph: it is a complement to the perfect matching graph. I leave it to my readers to check that the corresponding acquaintance graph doesn’t exist. Are there examples of two binomial coefficients that equal each other and that lead to an acquaintance graph that can be built?

Now that I’ve tackled the solution to this Olympiad problem, I see that I generated more questions than I answered.

Many years ago at Gelfand’s seminar in Moscow, USSR, someone pointed out a young girl and told me: “This is Natalia Grinberg. In her year in the math Olympiads, she was the best in the country. She is the next you.”

We were never introduced to each other and our paths never crossed until very recently.

Several years ago I became interested in the fate of the girls of the IMO (International Math Olympiad). So, I remembered Natalia and started looking for her. If she was the best in the USSR in her year, she would have been a gold medalist at the IMO. But I couldn’t find her in the records! The only Grinberg I found was Darij Grinberg from Germany who went to the IMO three times (2004, 2005, and 2006) and won two silver medals and one gold.

That was clearly not Natalia. I started doubting my memory and forgot about the whole story. Later I met Darij at MIT and someone told me that he was Natalia’s son.

I was really excited when I received an email from Natalia commenting on one of my blog posts. We immediately connected, and I asked her about past events.

Natalia participated in the All-Soviet Math Olympiads three times. In 1979 as an 8th grader she won a silver medal, and in 1980 and 1981 she won gold. That indeed was by far the best result in her year. So she was invited to join the IMO team.

That year the IMO was being held in the USA, which made Soviet authorities very nervous. At the very last moment four members of the team did not get permission to travel abroad. Natalia was one of them. The picture below, which Natalia sent to me, was taken during the Soviet training camp before the Olympiad. These four students were not allowed to travel to the IMO: Natalia Grinberg, Taras Malanyuk, Misha Epiktetov, and Lenya Lapshin.

Because of the authorities’ paranoia, the Soviet team wasn’t full-sized. The team originally contained eight people, but as they rejected four, only six traveled to the USA, including two alternates.

I have written before how at that time the only way for a Jewish student to get to study mathematics at Moscow State University was to get to the IMO. I wrote a story about my friend Sasha Reznikov who trained himself to get to the IMO, but because of some official machinations, still was not accepted at MSU.

Natalia’s story surprised me in another way. She didn’t get to the IMO, but she was accepted at MSU. It appears that she was accepted at MSU as a member of the IMO team, because that decision was made before her travel documents were rejected.

Natalia became a rare exception to the rule that the only way for a Jewish person to attend MSU was to participate in the IMO. It was a crack in the system. They had to block visas at the last moment, so that people wouldn’t have time to make a fuss and do something about it. Natalia slipped through the crack and got to study at the best university in the Soviet Union.

Unfortunately, the world lost another gold IMO girl. Three Soviet team members won gold medals that year. Natalia, being better then all of them, would have also won the gold medal.

I recently published the following coin puzzle:

There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

My readers, David Reynolds and ext_1973756, wrote to me that I am missing a coin of 4 grams. Indeed, the same puzzle with five coins—1, 2, 3, 4, and 5—is a more natural and a better puzzle.

David Reynolds also suggested to go all the way up to 9 coins:

There are nine silver coins marked 1, 2, 3, 4, 5, 6, 7, 8, and 9. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

It is impossible to resolve this situation with more than nine coins as two weighings provide nine different answers to differentiate coins. But indeed it is possible to solve this problem for nine coins. It is even possible to suggest a non-adaptive algorithm, that is to describe the weighings before knowing the results.

To find such a strategy we need to satisfy two conditions. First, we have to weigh groups of coins of the same supposed weight, otherwise we do not get any useful information. Second, there shouldn’t be any two coins together (in or out of the pan) in both weighings, because it would then be impossible to differentiate between them.

Here is one possible solution of the problem:

• The first weighing: 1, 5, and 9, against 2, 6, and 7
• The second weighing: 1, 6, and 8, against 2, 4, and 9

David Reynolds also suggested a problem in which we do not know whether the fake coin is heavier or lighter:

There are four silver coins marked 1, 2, 3, and 4. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

Again, four coins is the best we can do when in addition to find it, we also want to determine if it is heavier or lighter. Indeed, if there were five coins we would have needed to cover ten different answers, which is too many for two weighings.

Here is the solution for four coins:

The two weighings are 1+3=4, and 1+2=3. If the first weighing balances, then the fake coin is 2 and the second weighing shows if it is heavier or lighter than it should be. Similarly, if the second weighing balances, then the fake coin is four and we can see whether it is heavier or lighter than it should be. If the left pan is lighter/heavier for both weighings, then the fake coin is 1 and is lighter/heavier. But if one pan is heavier on the first of two weighings and the other pan is heavier on the second weighing, then the fake coin is 3. In both cases it is easy to determine whether the fake coin is heavier or lighter.

Now David is missing a coin. If we just want to find the fake coin without determining whether it is heavier of lighter, we can do it with five coins:

There are five silver coins marked 1, 2, 3, 4, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

We can use the same solution as the previous (four coins) problem. If the scale balances both times, then the fake coin is 5. However, in this case we will not know whether the coin is heavier or lighter.

We can’t extend this problem to beyond five coins. Suppose we have six coins. We can’t use more than three coins in the first weighing. This is because if the scale unbalances, we can’t resolve more than three coins in one remaining weighing. Suppose the first weighing balances; then we have at least three leftover coins we know nothing about and one of them is fake. These three coins should be separated for the next weighing. That means one of the coins needs to be on the left pan and one on the right pan. We can add real coins any way we need. But if the second weighing unbalances we do not know if the fake coin is on the left and lighter or on the right and heavier.