Tanya Khovanova's Math Blog

We’ve all been hearing about parallel computing, and now it has turned up in a coin-weighing puzzle invented by Konstantin Knop.

“We have N indistinguishable coins. One of them is fake and it is not known whether it is heavier or lighter, but all genuine coins weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts a minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?”

This puzzle reminds me of another coin-weighing problem, where in a similar situation you need to find a fake coin by using one scale with four pans. The answer in this variation would be 5⁵ = 3125. We can divide coins in five groups with the same number of coins and put four groups on the scale. If one of the groups is different (heavier or lighter), then this group contains the fake coin. Otherwise, the leftover group contains the fake coin. This way each weighing reduces the pile with the fake coin by a factor of five. One scale with four pans gives you more information than two scales with two pans used in parallel. We can conclude that Knop’s puzzle should require at least the same number of weighings as the four-pan puzzle for the same number of coins. So we can expect the answer to Knop’s puzzle will not be bigger than 3125. But what will it be?

Once when I was working at Telcordia, I received a phone call from my doctor’s office. Here is how it went:

— Are you Tanya Khovanova?
— Yes.
— You should come here immediately and redo your blood test ASAP.
— What’s going on?
— Your blood count shows that you are dead.
— If I’m dead, then what’s the hurry?
Given that I wasn’t dead, the conclusion was that there had been a mistake in the test. If there had been a mistake, the probability that something was wrong after the test was the same as it was before the test. There was no hurry.

I started my Yellow Road plan on February 9 when I was 245.2 pounds.

I decided that my first target weight would be my actual weight on February 9: 245.2. Every day this target weight goes down by 0.1 pounds. I weigh myself every morning and compare my actual weight to my target weight. My actions depend on the difference.

My Yellow Zone is plus or minus one pound of my target weight. My Green Zone means I am doing even better: my weight is less than my target weight minus one pound. My Red Zone means that I am not doing so great: my weight is more than my target weight plus a pound.

If I am within the Yellow corridor, I continue building my healthy habits as I have been doing. If I am in the Green Zone, I can afford to digress from healthy habits and indulge myself a bit. If I am in the Red Zone, I have to reduce my evening meals to apples only, which I do not particularly like. The Red Zone has different shades: if I am one pound over my target weight I have to start my apple restrictions after 8:00 pm. If I am two pounds over, then after 6:00 pm, and so on.

Today I am ten pounds lighter. In the process, I have made these discoveries:

Writing down my weight daily is very important. When I look at yesterday’s number and today’s number, I start thinking about what caused the increase or decrease. Now I have more clarity about which foods are better for me.

I have a better picture of how much I should eat. One day I held a party and I didn’t eat much. In fact, I had only one small desert. I didn’t feel full and went to bed feeling proud of myself. The next morning I weighed myself and was surprised to find I had gained three pounds. The amount of food I should be eating is much smaller than I expected. I think it may be three times less than what I was used to eating. My plan might not be aggressive enough. Currently when I am in my lightest Red Zone, I have to eat just apples after 8:00 pm. I discovered that I can still gain weight with this regime.

A half-empty stomach is not such a bad feeling. I was so afraid of starting a plan where I might feel hungry. Now I discovered that there are several hours between my first signal that I should eat and real hunger. My first sense that I should eat something might not be actual hunger at all. I do experience a light feeling in my stomach, but now I am starting to learn to enjoy it.

The system works for me. That’s the bottom line. For the first time in my life, I found a way to lose weight. All my friends ask me about this system. I explain that this Yellow Road plan is not a panacea. My plan is based on many other things that I did before. If it continues working, I promise to discuss it further: to analyze what exactly works and why.

My next step is to adjust my plan in light of my discoveries. From now on, I’ll eat only apples after 8:00 pm—not as an exception, but as a rule.

Here is a problem from the 2012 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 common acquaintances at this meeting.
• Show that n can be greater than 4.

My question is: Why 4? I can answer that myself. If in a group of four people any two people share exactly two common acquaintances, then all four people know each other. So in this Olympiad problem, the author wanted students to invent a more intricate example.

Let’s take this up a notch and work on a more difficult problem.

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 common acquaintances at this meeting.
• Is it possible that n can be greater than 2k?

I stumbled upon an article, Winners Live Longer, that says:

“When 524 nominees for the Nobel Prize were examined and compared to the actual winners from 1901 to 1950, the winners lived longer by 1.4 years. Why? It seems just having won and knowing you are on top gives you a boost of 1.8% to your life expectancy.”

This goes on top of the pile of Bad Conclusions From Statistics. With any kind of awards where people can be nominated several times, winners on average would live longer. The reason is that nominees who die early lose their chance to be nominated again and to win.

I wonder what would happen if we were to compare Fields medal nominees and winners. There is a cut off age of 40 for receiving a Fields medal. If we compare the life span of Fields medal winners and nominees who survived past 40, we might get a better picture of how winning affects life expectancy.

Living a long life increases your chances of getting a Nobel Prize, but doesn’t help you get a Fields medal.

I wish I could write four papers in three weeks. The title just means that I submitted four papers to the arXiv in the last three weeks—somehow, after the stress of doing my taxes ended, four of my papers converged to their final state very fast. Here are the papers with their abstracts:

• On k-visibility graphs (with Matthew Babbitt and Jesse Geneson). We examine several types of visibility graphs in which sightlines can pass through k objects. For k ≥ 1 we improve the upper bound on the maximum thickness of bar k-visibility graphs from 2k(9k−1) to 6k, and prove that the maximum thickness must be at least k+1. We also show that the maximum thickness of semi-bar k-visibility graphs is between the ceiling of 2(k+1)/3 and 2k. Moreover we bound the maximum thickness of rectangle k-visibility graphs. We also bound the maximum number of edges and the chromatic number of arc and circle k-visibility graphs. Furthermore we give a method for finding the number of edges in semi-bar k-visibility graphs based on skyscraper puzzles.
• Skyscraper Numbers (with Joel Brewster Lewis). We introduce numbers depending on three parameters which we call skyscraper numbers. We discuss properties of these numbers and their relationship with Stirling numbers of the first kind, and we also introduce a skyscraper sequence.
• Connected Components of Underlying Graphs of Halving Lines (with Dai Yang). In this paper we discuss the connected components of underlying graphs of halving lines’ configurations. We show how to create a configuration whose underlying graph is the union of two given underlying graphs. We also prove that every connected component of the underlying graph is itself an underlying graph.
• Efficient Calculation of Determinants of Symbolic Matrices with Many Variables (with Ziv Scully). Efficient matrix determinant calculations have been studied since the 19th century. Computers expand the range of determinants that are practically calculable to include matrices with symbolic entries. However, the fastest determinant algorithms for numerical matrices are often not the fastest for symbolic matrices with many variables. We compare the performance of two algorithms, fraction-free Gaussian elimination and minor expansion, on symbolic matrices with many variables. We show that, under a simplified theoretical model, minor expansion is faster in most situations. We then propose optimizations for minor expansion and demonstrate their effectiveness with empirical data.