Tanya Khovanova's Math Blog

You are given N coins such that two of them are fake and the other coins are genuine. Real coins weigh the same. Fake coins weigh the same and are lighter than real ones. You need to find both fake coins using a balance scale in the smallest number of weighings.

It is easy to estimate the number of weighings from below using information theory. Given N coins you will have N choose 2 different answers. The number of possible answers has to be not more than 3^w, where w is the number of weighings. This generates a trivial information-theoretic bound (ITB) on the number of coins that can be processed in a given number of weighings.

Previous authors used computers to completely analyze small numbers of weighings: from 2 to 5.

My colleagues from Russia, Konstantin Knop and Oleg Polubasov, performed some fantastic programming accompanied with some subtle heuristic and found optimal solutions for up to 10 weighings. For 11 and 12 weighings, the program is not efficient enough to find the optimal solutions: it found some solutions. Surprisingly, for up to 10 weighings, the optimal solutions match the information-theoretic bound (ITB). The results are in the table below. The first row represents the number of weighings w. The second row is the largest number of coins N for which a solution is found. The last row is the information-theoretic bound (ITB) we explained above.

Their paper, Two counterfeit coins revisited, is available in Russian. Lucky for us, 70 of 73 pages are pseudo-code of solutions for which you do not need any Russian. You just need to understand the pseudo-code. Here is the explanation.

Each line begins with its number. After it they have the weighing in the format 1 10 v 4 5 meaning coins 1 and 10 are weighed versus coins 4 and 5. Each weighing is followed by a colon, after which they describe in order actions for three different outcomes of the weighing: equality, the first pan is lighter, and the second pan is lighter. Each action is one of the following:

• => L means go to line L.
• (a, b) means the fake coins are a and b.
• – means this branch is impossible and there is no output.
• => 23. sym indicates the symmetry of the weighing and its result, therefore the resulting go-to line, 23, is omitted as being equivalent to another line.
• – . sym means the output is symmetric to another one.

The line numbers after => in line L are always 3L+1, 3L+2 and 3L+3. The sym symbol implies that line 3L+3 is omitted as a symmetric version of line 3L+2.

For example, here is their solution for 2 weighings and 4 coins in their pseudo-code. An empty line separates different weighings:

0. 1 v 2 : => 1, => 2, => 3. sym

1. 1 v 3 : – , (1, 2), (3, 4).
2. 3 v 4 : – , (1, 3), – . sym

Another solution for 3 weighings and 7 coins:

0. 1 2 v 3 4 : => 1, => 2, => 3. sym

1. 1 v 2 : => 4, => 5, => 6. sym
2. 1 v 2 : (1, 2), => 8, => 9. sym

4. 5 v 6 : (5, 6), (5, 7), – . sym
5. 3 v 4 : – , (1, 3), – . sym
8. 5 v 6 : (1, 7), (1, 5), – . sym

If you want to see an optimal solution for 10 weighings, look at the paper: the algorithm takes 36 pages.

I recently posted two trick questions.

First question. What is the answer to this question?

The title to this post was the same as the content except for the question mark: What is the Answer to This Question. The title contained the answer: WHAT.

What I like about trick questions is that sometimes people produce alternative answers that are as good as the intended ones. For this problem I like the following answers:

• If you have a compiler which converts recursion to loops, then infinite loop. Otherwise, stack overflow. (by aphar)
• Chocolate is the answer. It doesn’t matter what the question is. (by Mark James)
• 42. (by Clao)
• This is the Answer to that Question. (by Javifields)

Second question. How many letters are there in the correct answer to this question?

The intended answer was FOUR, as four is the only number in the English language for which the number of letters in its name is equal to the number itself. Many people used variations on the theme and supplied the following answers by writing out numbers in non-canonical ways:

• Positive fifteen. (by my AMSA students)
• One plus twelve. (by Michael and MQ)
• Two plus eleven. (by MQ)
• Maybe eleven. (by Michael Albert)
• Certainly sixteen. (by Michael Albert)
• Zero plus one plus two plus three plus …. (by Bob Hearn)

Some people used sentences to express numbers:

• Any number n whose value can be expressed using n letters, for example sixty seven. (by Michael Albert)

Some other people used Roman numerals and digits to express the answer:

• I, II, or III (by my AMSA students)
• 0 (by my AMSA students, Leo, and lvps1000vm)

Many people pointed out that if the puzzle would be asked in other languages, it would produce completely different answers.

But the majority of my AMSA students took a completely different approach:

• 30.

This is because there are thirty letters in the phrase the correct answer to this question.

Although I cut most carbs from my diet, I still wasn’t losing weight. I started my weight-loss journey three years ago when I was 245 pounds. My initial excitement helped me get to 220, but then I started slowly gaining it back to 235 pounds. A couple of friends of mine who lost a lot of weight explained to me that I didn’t actually cut all the carbs from my diet. I eliminated pizza, potatoes, spaghetti, sugar, cookies, soda, and so on. But there are many carbs hidden in some very natural and healthy foods. For example, a banana has 27 grams of carbs.

I love bananas; I can live on bananas alone. But my friends convinced me to cut the bananas, too. I agreed, but in that week I gained five more pounds. I think that every time I remove something from my diet, I end up becoming more relaxed with other food.

Clearly, carbs-cutting doesn’t work. I am back to 240 pounds. Time for plan B.

The first Moscow Math Olympiad was conducted in 1935. Today, eighty years later, I decided to check it out. Most of the problems look standard, but some of the stereometry problems look too complicated. I found four problems that I really like: all of them are geometry problems.

Problem 1. The lengths of the sides of a triangle form an arithmetic progression. Prove that the radius of the inscribed circle is one third of one of the heights of the triangle.

Problem 2. A median, bisector, and height all originate from the same vertex of a triangle. You are given the three points that are the intersection points of the aforementioned median, bisector, and height with the circumscribed circle. Construct the triangle.

Problem 3. Find the set of points P on the surface of a cube such that the main diagonal subtends the smallest possible angle if viewed from P. Prove that the main diagonal subtends larger angles if viewed from other points on the surface. [Clarification: the two corners the main diagonal passes through don’t count.]

Problem 4. Given three parallel straight lines, construct a square such that three of its vertices belong to these lines.

Each of these problems has a powerful idea that solves it. You can try and solve these problems, but if you want help, the ideas are presented below as hints in a scrambled order.

• Hint. Rotate by 90 degrees.
• Hint. Consider a circumscribed sphere.
• Hint. The line connecting the intersection point of the bisector with the circle and the circle’s center is parallel to the height.
• Hint. Use Heron’s formula.

As a child I felt that society expected me to grow up and be a mother. And only to be a mother. It didn’t make any sense to me, because if all that people do is reproduce, how will progress be made? So in my teens I decided that in addition to having children, I need to do something else, something to make the world a better place.

For many years I wasn’t too successful in my plan. My children were my priority. I believed that for the first three years they needed a lot of my attention, which they couldn’t necessarily get from a nanny. Later, being a single mother was so overwhelming that I didn’t have time for other missions.

As my children grew, I felt myself imposing my own ambitions onto them. It wasn’t fair to burden my children like that. I was meant to do something with my life other than bring up children. There was no substitute — I had to do it myself.

At that time, I was working at BAE Systems, but I hated my job. Its only purpose was to support my family. So as soon as my youngest son turned 16, I resigned to come back to mathematics. Though mathematics has my full attention now, my children are still my priority. I can afford to do what I love, because it is good for my children too. I am living my own ambitions, and they have the space to live theirs.

I was supposed to write about menopause. I am writing about menopause, just give me a second. I was also raised to believe that the best thing I can do for a man is to give him children. Every time I loved someone I wanted to have a child with that person, or I thought that I was supposed to want to. Now that I can’t conceive a child for any potential future husband, I feel relieved. I can’t be blamed any more for not having children. I am so happy that my current attempt at mathematics will not be interrupted any more.

I am so glad that I live in an age when women’s life expectancy is way past menopause. I might love a man again; I might marry. I am so glad that I have an excuse not to have children. I can do what I want to do. I am free.

* * *

—Mike, here are 10 chocolates. Give half of them to your brother.
—OK. I’ll give him three chocolates.
—You can’t count?
—I can, but he can’t.

* * *

—How is your progress?
—50%.
—Done or left to do?

* * *

—Q: What did Al Gore play on his guitar?
—A: An Algorithm.

* * *

I put my root beer in a square glass. Now it’s just beer.

* * *

—Q: Why shouldn’t you argue with a decimal?
—A: Decimals always have a point.

* * *

—I am cold.
—Go stay in the corner. It’s 90 degrees.

* * *

Arithmetic is the art of counting up to twenty without taking off your shoes.

* * *

I bought a book online “How to implement an Internet scam.” Somehow, though, it’s been a while, and I still haven’t received it.

* * *

Sex is a pathetic thrill for losers who are not able to take a triple integral.

* * *

Paradox: Less money, more need to count it.

How many letters are there in the correct answer to this question?

What is the answer to this question?

In my paper Nim Fractals written with Joshua Xiong we discovered an interesting graph structure on P-positions of impartial combinatorial games. P-positions are vertices of the graph and two vertices are connected if they are consecutive P-positions in an optimal longest game.

A longest game of Nim is played when exactly one token is removed in each turn. So in Nim two P-positions are connected if it is possible to get from one of them to the other by removing two tokens.

In the paper we discussed the evolution graph of Nim with three piles. The graph has the same structure as three branches of the Ulam-Warburton automaton.

For completeness, I would like to describe the evolution graph of the 2-pile Nim. The P-positions in a 2-pile Nim are pairs (n,n), for any integer n. Two positions (n,n) and (m,m) are connected if and only if m and n differ by 1. The first picture represents this graph.

The Wythoff’s game is more interesting. There are two piles of tokens. In one move a player can take any number of tokens from one pile or the same number of tokens from both piles.

The P-positions (n,m) such that n ≤ m start as: (0,0), (1,2), (3,5), (4,7), (6,10) and so on. They can be enumerated using φ: the golden ratio. Namely, n_k = ⌊kφ⌋ and m_k = ⌊kφ²⌋ = n_k + k, where k ≥ 0.

In a longest Wythoff’s game the difference between the coordinates decreases by 1. That is, it takes a maximum of 2k steps to end an optimal game starting from position (n_k,m_k). The picture shows the evolution graph.

The interesting part of the picture is the crossover between two “lines”. From positions with large coordinates like (6,10) with a difference of 4 you can get to only one position with a difference of 3: (4,7) and not (7,4). But from position (3,5) with a difference of 2 you can get to both positions with a difference of 1: (1,2) and (2,1).

I enjoy doing research in recreational mathematics. The biggest problem is that the probability that something I’ve done has already been done before is very high. This is partially because of the nature of this area of research. Trying to find new questions that are not buried deep in the abstract means someone else could have stumbled upon the same question. In addition, I like going in different directions: geometry, number theory, probability, combinatorics, and so on. That means I am not an expert in any of the areas. This too increases my probability of doing something that has already been done before.

This is quite unpleasant: to discover that I reinvented the wheel. And I keep reinvented different wheels on a regular basis. When I complain, my mathematician friends give me the same advice over and over:

Find your own niche!

I’ve been trying to understand what they mean, and finally I got it:

Do something no one else is interested in using methods no one else can understand.

Finding a topic that is not interesting almost guarantees that other people didn’t do it before. Developing new complicated methods helps limit the number of followers and prevents the niche from becoming crowded.

Now I know why I see so many boring math papers I can’t understand.

To hell with my own niche!