Tanya Khovanova's Math Blog

Let us start with regular (non-weighted) mediants. Suppose we have two fractions a/b and c/d, the mediant of these two numbers is the wrong way a child might sum these two fractions: (a+c)/(b+d). There is nothing wrong with this childish way of summing, it is just not a sum of two numbers, but rather an operation the result of which is called a mediant. One must be careful: the result doesn’t depend on the initial numbers chosen, but on their representations. The way to deal with this is to assume that a/b, c/d, and (a+c)/(b+d) are in their lowest terms.

The numerical value of the mediant is always in between given numbers. This is probably why it is called a mediant.

Suppose you start with two rational numbers 0/1 and 1/1, and insert a mediant between them. If you continue doing it recursively, you can reach any rational number between 0 and 1. This is a well-known property of the mediants. For example, after three rounds of inserting mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 1/1.

The mediants are easy to generalize if we assign weights to initial fractions. Suppose the first fraction has weight m and the second n, then their weighted mediant is (am+cn)/(bm+dn). The simplest generalization happens when the total weight, m+n is 3. In this case, given two rational numbers a/b and c/d, the left mediant is (2a+c)/(2b+d) and the right one is (a+2c)/(b+2d). Obviously the inequality property still holds. If a/b ≤ c/d, then a/b ≤ (2a+c)/(2b+d) ≤ (a+2c)/(b+2d) ≤ c/d.

James Propp suggested the following question for our PRIMES project. Suppose the starting numbers are 0/1 and 1/1. If we recursively insert two weighted mediants in order between two numbers we will get a lot of numbers. For example, after two rounds of inserting weighted mediants into the initial sequence (0/1, 1/1), we get the sequence: 0/1, 1/5, 2/7, 1/3, 4/9, 5/9, 2/3, 5/7, 4/5, 1/1. It is easy to see that new fractions must have an odd denominator. Thus unlike the standard case, not every fraction will appear. The question is: will every rational number between 0 and 1, which in reduced form has an odd denominator appear?

I started working on this project with Dhroova Aiylam when he was a high-school junior. We didn’t finish this project during the PRIMES program. But Dhroova finished another project I already wrote about: he analyzed the case of the standard mediants with any starting points. He showed that any rational number in between the starting points appears.

Dhroova became an undergraduate student at MIT and we decided to come back to the initial PRIMES project of weighted mediants. In our paper Stern-Brocot Trees from Weighted Mediants we prove that indeed every fraction with an odd denominator between 0 and 1 appears during the recursive procedure. We also analyzed what happens if we start with any two rational numbers.

In the starting position you see four multi-colored quadrants of a ring. For example, the first picture shows the starting position of level 33.

You can either swipe or touch between the quadrants. A swipe expands one quadrant into two quadrants and compresses two other quadrants into one. You can swipe clockwise or counterclockwise. The second figure shows the result of the clockwise swipe of the North opening. The NW quadrant that was half-red and half-yellow has expanded into two quadrants. The red piece now occupies the entire NW quadrant and the yellow piece—the entire NE quadrant. Two East quadrants got contracted into one SE quadrant. The former blue NE quadrant became the top blue half of the SE quadrant. The former SE half-blue half-green quadrant became the bottom half of the SE quadrant. In general the quadrant where the swiping movement starts expands in the direction of the swipe and the quadrant where the swiping movements ends together with the next quadrant compresses.

You can also touch an opening between quadrants. In this case the neighboring quadrants exchange places. The third figure shows the result of touching the East opening.

The goal of the game is to reach the final position: have each quadrant in one color. The next image shows the end of this particular level. As you can see the game was finished in 7 moves. In this particular case this is the smallest number of moves possible. To tell you a secret, it wasn’t me who finished the game in the smallest number of moves: it was my brother.

There is also a tutorial for this game on youtube.

I was at the 1976 International Mathematics Olympiad as part of the USSR team. There were eight people on the team and I decided to find out what they have achieved in the last 40 years. Here is the picture of our team. From left to right: Sergey Finashin, Yuri Burov, Nikita Netsvetaev, Boris Solomyak, Alexander Goncharov, Tanya Khovanova, Sergei Mironov, our chaperone Z.I. Moiseeva, our team leader A.P. Savin, no clue who this is (probably a translator), Piotr Grinevich.

The list below is ordered by the number of points received at the Olympiad.

Tanya Khovanova, 39 points: a lecturer at MIT. I am interested in a wide range of topics, mostly recreational mathematics and have written 60 papers.

Sergey Finashin, 37 points: a full professor at Middle East Technical University in Turkey, who is interested in topology. He wrote 40+ papers.

Alexander Goncharov, 37 points: a full professor at Yale University. He is the highest achiever on the team. He won the EMS Prize in 1992 and was an Invited Speaker at the 1994 International Congress of Mathematicians. He is interested in geometry, representation theory, and mathematical physics. He published 75 papers in refereed journals.

Nikita Netsvetaev, 34 points: a full professor at Saint-Petersburg University in Russia. He is interested in topology and algebraic geometry and wrote 20 papers.

Boris Solomyak, 31 points: a full professor at Bar-Ilan University. He is interested in fractal geometry and dynamical systems and wrote 90 papers.

Piotr Grinevich, 26 points: a leading scientific researcher at the Landau Institute for Theoretical Physics. He also teaches at Moscow State University. He is interested in integrable systems and wrote 80 papers.

Sergei Mironov, 24 points. Sergey became very ill while he was an undergrad. He stopped doing mathematics.

Yuri Burov, 22 points. Yuri wrote two papers, but quit mathematics after graduate school. He died several years ago from multiple sclerosis.

Six out of eight people on our team became mathematicians. Or more precisely five an a half. I consider myself a mathematician and am grateful for my position at MIT, where I run innovative programs for young mathematicians. But in the research world, a lecturer is a nobody. This makes me sad. I had to take breaks from research in order to raise my two children. And then I had to work in the private sector in order to support them. I was the best on my team and now I am the only one who is not a full professor. If you are looking for an example of how gender affects a career in academia, this is it.

For many years I tried to lose weight using the idea that most appealed to me: intuitive eating. By that I mean that you eat only when you are hungry. Looking back at frustrating years of trying, I wonder what took me so long to realize that this doesn’t work.

I am most hungry at the end of a meal. The only time I want to kill people is when they get between me and my future third helping of cheesecake. I never get the same ravenous feeling if I haven’t eaten for some time, or have just started eating.

I am least hungry in the morning. I can work on my computer for hours before I even remember that I need to eat.

When my stomach signals that it needs more food, it is always wrong. Recently, I discovered what is right. I am using myfitnesspal app for my phone that counts my calories. From time to time I know that I haven’t eaten enough. At these times, I don’t experience my hunger in my gut. I feel it in my head: I feel dizzy.

I decided to drop the idea of intuitive eating and outsource the decision of when and what to eat to a higher power: my smart-phone.

After graduating from MIT, my son Sergei joined Two Sigma, a hedge-fund. Last year he came to MIT representing Two Sigma at a career fair. I visited him in his booth. He was just standing there next to himself on the poster.

I should stop worrying about him. If math does not work out, he has a chance at modelling.

I have written ad nauseam about the ambiguity of problems with children. Usually a problem with two children is formulated as follows:

Mr. Smith has two children and at least one of them is a boy. What is the probability that he has two boys?

I don’t want to repeat my arguments for why this problem is ambiguous. Today I want to discuss other problematic assumptions about these problems.

Assumption 1: The probability of a child being a boy is 1/2. We know that this is not the case. Usually boys are born more often than girls. In addition to that, when policy interferes, the numbers can change. When China had their one-child policy, 118 boys were born per 100 girls. That makes a probability of a boy 0.54.

Assumption 2: The gender of one child in a family is independent of the gender of the other children. I am not sure where this assumption comes from, but I easily came up with a list of possible influences on this situation.

• A family can have identical twins.
• Families that adopt children can choose the gender of those kids.
• There are studies showing that people (especially men) can have a genetic predisposition to one gender of their children over the other.
• Sex-selective abortion is possible in many countries.
• In vitro fertilization and artificial insemination can use sex-selection techniques.
• People may reject their newborns based on sex.
• The decision to have a second child depends on the gender of the first child.

I would like to discuss how the last bullet point changes the probabilities in two children problems. Let us consider China. Up to now China had a one-child policy with some exceptions. In some cases if the first child was a girl, the family was allowed a second child. For the sake of argument, imagine a county where people are allowed to have a second child only if the first one is a girl. A family with two boys wouldn’t exist in this county. Thus the probability of having two boys is zero.

I tried to find the data about the distribution of children by gender in multi-children families. I couldn’t find any. I would be curious to know what happens in real life, especially in China.

A long time ago, before anyone ever heard about ultrasound, there was a psychic who could predict the gender of a future child. No one ever filed a complaint against him.

The psychic had a journal in which he wrote the client’s name and the gender of the future child. The beauty of the scam was that what he wrote in the journal was the opposite gender that he had predicted. Whenever a client complained that the gender was wrong, he would show the journal and argue that the client had misunderstood.

Happy clients don’t return to complain.

Oh, the power of conditional probability! It is useful to understand it to run scams or to expose them.

I’ve been trying to lose weight for three years. I wasn’t very successful, but I always had plan B. I just didn’t like it. I started my weight-loss journey at 245 pounds. Driven by my initial enthusiasm, I lost 25 pounds, but then I slowly gained back 20 pounds. That was it. I had to do the difficult thing: plan B.

My plan B was to log all I eat, convert it to nutrition elements, study it, and adjust my eating habits accordingly. I didn’t want to do that: it seemed so complicated. I am not good at estimating weights, nor do I know how to convert food to calories and fat. Besides, it all seemed like such a bother.

When I gained back the weight and reached 240 pounds, I didn’t feel I had much choice. At that point my friend Luba showed me how to use the phone app myfitnesspal. I loved it. The app simplified the whole challenge. I bought a small kitchen scale to help me determine food weight, but more often than not, I don’t need it. The app has a database of standard foods, as well as a barcode scanner. For example, when I take my favorite cranberry walnut roll that I buy at Trader Joe’s, I just scan the barcode and the phone tells me, “Oops. 210 calories.” This means I can only eat one a day — not all six as I might have done.

I started using this app on November 16, 2015. It seems to be working. And I made a lot of interesting discoveries.

• Those walnuts that I eat like popcorn while watching movies have a ton of calories. They might be healthy natural food, but if I munch them throughout a movie, then I can’t eat anything else that day.
• When I know that I can only allow myself one square of chocolate, it tastes better than pigging out on the whole bar.
• I made a rule of logging my food before I eat it. This killed my habit of snacking. Finally, my laziness works for me.

I am losing weight, but to avoid jinxing it until I achieve a certain target, I don’t want to reveal actual numbers.

To be continued…

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.