My Poster Boy

Sergei and Two Sigma PosterAfter 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.


Problems with Problems with Two Children

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.


How to “Predict” the Gender of a Future Child

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.


Plan B

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…


Two Fake Coins

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 3w, 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.

w 5 6 7 8 9 10 11 12
N 22 38 66 115 198 344 585 1026
ITB 22 38 66 115 198 344 595 1031

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.


The Intended Answers

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.


Evil Bananas

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 Olympiad

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.

Ode to Menopause

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.


Time for Jokes

* * *

—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?
—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.