Tanya Khovanova's Math Blog

I always wanted to be a person of the world. I wanted my genes to be a mixture of everything. I was glad that I had a great-grandfather from Poland and a great-great-great-grandmother from France. I was also thrilled when my mom told me that her Asian students think she is one of theirs. So I decided to send my DNA to 23andMe and really see what I have.

To my surprise, my world is not as mixed as I expected: I am 99.5% European. My Asian part is minuscule: 0.2%, out of which only 0.1% is assigned as Yakut. My African part is also 0.2%.

My European part is a mixture of mostly eastern and northern European. I am 2.8% Ashkenazi.

In addition to my genetic profile, 23andMe sent me the list of a thousand of my distant relatives. They also sent me a report about the most common last names among my relatives. The list starts with Cohen and continues with Levine, Levin, Goldberg, and Rubin.

You might be surprised by this list of Jewish names when I am only 2.8% Jewish. But the list is based on people who decided to send their DNA to 23andME and provided their last names. All my Russian relatives remained in Russia. Russia has its own company, I-gene, that provides a similar service, and the two databases are not shared.

Only my distant relatives who moved to the US and who are curious about their ancestry and who are willing to share their last names will appear on this list. So maybe this list is not surprising.

Here is an old Olympiad problem:

Prove that you can choose 2^k numbers from the set {1, 2, 3, …, 3^k−1} in such a way that the chosen set contains no averages of any two of its elements.

* * *

—Describe yourself in three words.
—Lazy.

* * *

Internet forum:
—Tell me about yourself.
—I am lazy and I like to eat.
—Tell me some more.
—I am tired of typing. I’ll go grab a snack.

* * *

—Why do you want to divorce your wife?
—She nags too much. For the last half six month, she’s been bugging me everyday to throw away the Christmas tree.

* * *

Yesterday I realized that I’m not the laziest person in the world. I saw my neighbor walking the dog on a leash through his window.

* * *

The list of symptoms of laziness:
1)

This is a variation on an old quiz. Can you answer the last question?

—An airplane carries 500 bricks. One of the bricks falls out. How many bricks are left in the airplane?
—This is easy: 499!
—Correct. Next question. How do you put a giraffe into a refrigerator?
—Open the refrigerator, put in the giraffe, and close the refrigerator door.
—Good, next. How do you put an elephant into a refrigerator?
—Open the refrigerator, take out the giraffe, put in the elephant and close the door.
—Correct. The Lion King is hosting his birthday party. All the animals come to congratulate him—except one. Why?
—The elephant couldn’t come because it is in the refrigerator.
—Fantastic, next. A man needs to cross a river inhabited by crocodiles and he doesn’t have a boat. What should he do?
—He can just swim: all the crocodiles are attending Lion King’s birthday party.
—Amazing! The last question: The man swims across the river, and dies. What happened?

Hugh ApSimon described the following coin puzzle in his book Mathematical Byways in Ayling, Beeling and Ceiling.

New coins are being minted at n independent mints. There is a suspicion that some mints might use a variant material for the coins. There can only be one variant material: fake coins weigh the same independently of the mint. The weight of genuine coins is known, but the weight of fake coins is not. There is a machine that can precisely weigh any number of coins, but the machine can only be used twice. You can request several coins from each mint and then perform the two weighings so that you can deduce with certainty which mints produce fake coins and which mints produce real coins. What is the minimum total of coins you need to request from the mints?

I will follow ApSimon’s notation. Suppose P_r and Q_r is the number of coins from the mint r used in the first and the second weighing correspondingly. That is, we are minimizing Σmax(P_r,Q_r). (All my summations are over all the mints. I skip the summation limits because it is difficult to write math in html.) Let us denote by W the weight of the genuine coin and by W(1 + ε) the weight of the fake coin. We do not know ε, except that it is not zero.

Let d_r be either 0 or 1, depending on what material the r-th mint uses. Thus, the coin from the r-th mint weighs W(1 + d_rε). We know the results of these two weighings and the weight of the genuine coin. Therefore, we can calculate the following two values: a = ΣP_rd_rε and b = ΣQ_rd_rε.

It is clear that we need to request at least one coin from each mint and use it in at least one weighing: P_r + Q_r > 0. If both sums a and b are zero, then all the mints are producing genuine coins. Neither of the two values gives us much information as we do not know ε. We can get rid of ε by dividing a by b.

There are 2ⁿ − 1 combinations of possible answers: these are subsets of the set of mints producing fake coins given that there is at least one. Thus we need to select numbers P_r and Q_r, so that a/b produces 2ⁿ − 1 possible answers for different sets of values of d_r.

Let us consider cases in which the total number of mints is small. If there is one mint we can take one coin and we won’t even need a second weighing. For two mints we need one coin from each mint for a total of 2. For three mints, one coin from each mint is not enough. I leave this statement as an exercise. It is possible to test three mints with four coins: one each from the first and second mints and two from the third mint. The coins from each mint for the first and second weighings are (0,1,2) and (1,1,0) respectively.

To prove that this works we need to calculate (d₂ + 2d₃)/(d₁ + d₂) for seven different combinations of d_r. I leave this as an exercise.

This puzzle seems to be very difficult. We only know the answer if the number of mints is not more than seven. The corresponding sequence A007673 in the OEIS is: 1, 2, 4, 8, 15, 38, 74. It is possible to give bounds for this sequence, but they are so far apart. The lower bound is n. And the ApSimon’s book offers a construction for two weighings were P_r = r! and Q_r = 1.

You can try to find a better construction, or you can try calculating more terms of the sequence. You can also read more about this problem in my short paper Attacking ApSimon’s Mints.

I do not want to leave the readers with the puzzle that might end up being intractable. So I suggest the following easy puzzle. Solve the ApSimon’s Mints problem assuming that the weight of the fake coin is known.

I once took an accent reduction course, to modify my Russian accent in English. In the first class the teacher explained that the biggest reason people have strong accents is that they stop learning and trying to improve their speech as soon as they can be understood. I promised myself to never stop learning and to continue working on my accent reduction forever.

Once I was giving a lecture on probability and statistics at the IAP mathematical series. My last slide was about the research on the correlation between masturbation male habits and prostate cancer. Their interpretation of the data had been wrong and a very good example of what not to do.

So I looked directly into the eyes of the course coordinator, who was observing my lecture, and without realizing what I was saying, asked, “Do we have time for masturbation?”

Everyone started laughing and I had to present my slide in order to explain myself.

The news of my double entendre spread. Soon after that I was asked to give a lecture at the Family Weekend at MIT. I wonder if that is why the lecture coordinator asked me not to discuss masturbation as small children might be present.

Luckily that was the only fallout from my blooper. Anyway, I decided to stop working on my accent. When people understand that English is not my first language they forgive more readily my slips of tongue.

* * *

—Honey, have you blocked our computer?
—Yes.
—What’s the password?
—Our wedding date.
—%?#!!

* * *

—What’s the pin on our card?
—We’re on a public chat, honey. Why don’t I sms it?
—But I forgot my phone. Please tell me, cupcake!
—Okay. By digit: the second digit of our apartment number, the fourth digit of your phone number, the month of my birthday, and the number of our children.
—Got it. How clever! 8342, right?

* * *

—Where is the report?
—We are stuck. The tech people took our monitor with passwords.
—What!?!
—Our monitor got broken so the techs took it for repair. Our passwords were written on the stand.

Here is a setup that works for the several puzzles that follow it:

The sultan decides to test his hundred wizards. Tomorrow at noon he will randomly put a red or a blue hat—from his inexhaustible supply—on every wizard’s head. Each wizard will be able to see every hat but his own. The wizards will not be allowed to exchange any kind of information whatsoever. At the sultan’s signal, each wizard needs to write down the color of his own hat. Every wizard who guesses wrong will be executed. The wizards have one day to decide together on a strategy.

I wrote about puzzles with this setup before in my essay The Wizards’ Hats. My first request had been to maximize the number of wizards who are guaranteed to survive. It is easy to show that you cannot guarantee more than 50 survivors. Indeed, each wizard will be right with probability 0.5. That means whatever the strategy, the expected number of wizards guessing correctly is 50. My second request had been to maximize the probability that all of them will survive. Again, the counting argument shows that this probability can’t be more than 0.5.

Now here are some additional puzzles, including the first two mentioned above, based on the same setup. Suggest a strategy—or prove that it doesn’t exist—in which:

1. 50 wizards will be guaranteed to survive.
2. 100 wizards will survive with probability 0.5.
3. 100 wizards will survive with probability 0.25 and 50 wizards will survive with probability 0.5.
4. 75 wizards will survive with probability 1/2, and 25 wizards survive with probability 1/2.
5. 75 wizards will survive with probability 2/3.
6. The wizards will survive according to a given distribution. For which distributions is it possible?

As I mentioned, I already wrote about the first two questions. Below are the solutions to those questions. If you haven’t seen my post and want to think about it, now is a good time to stop reading.

To guarantee the survival of 50 wizards, designate 50 wizards who will assume that the total number of red hats is odd, and the rest of the wizards will assume that the total number of red hats is even. The total number of red hats is either even or odd, so one of the groups is guaranteed to survive.

To make sure that all of them survive together with probability 0.5, they all need to assume that the total number of red hats is even.

I love making math questions out of the movies. Here is a Mission Impossible III question.

Tom Cruise is cute. He plays Ethan Hunt in Mission Impossible movies. In Mission Impossible III he needs to steal the Rabbit’s Foot from a secure skyscraper in Shanghai. He arrives in Shanghai and studies the skyscraper looking out his window. He decides to break in through the roof. And the way to get to the roof is to use a rope and swing across from another, even taller, skyscraper. 1:21 minutes into the movie, Ethan Hunt calculates the length of the rope he will need by using the projection of a skyline on his window, as seen on the first picture.

Explain why the projection is not enough to calculate the length of the rope. What other data does he need for that? Ethan Hunt does request extra data. But he makes one mistake. He uses his pencil as a compass to draw the end of the rope curve, as seen on the second picture. Explain what his mistake is.