Tanya Khovanova's Math Blog

Now that my weight loss is under way, I want to build an exercise program.

I already exercise. I am a member of the MIT ballroom dance team and I go to the gym, where I use the machines, swim, and take gentle yoga and Zumba classes.

Doesn’t sound bad, right? But the reality is that I went to Zumba class a total of three times last year. I skipped half the dance classes I signed up for because I was too tired to attend. I had sincerely planned to go to them, but they’re held in the evenings, when I’m already drooping.

The yoga situation is the worst. I’m scheduled to go to yoga twice a week, but just as it is time to leave for yoga, I get very hungry and cannot resist having a snack. Then I remember that they do not recommend practicing yoga after eating a meal, and voilà—I have found my excuse. I am all set up to exercise five hours a week, but in reality most weeks I do not exercise at all.

How can I motivate myself? I know that with food, if I have gained weight one day, I eat less the next. So if I’ve missed my goal of exercising one week, do I add those hours to the next week? That’s unlikely to actually help, since the problem is that I’m not meeting my exercise goal, period.

Many people suggested that I punish myself. For example, if I do not meet my goal, I should donate money to a cause I do not support. This feels wrong. If I fail, I’ll feel doubly guilty. I’ll go broke paying for psychotherapy.

I can try to reward myself. But what should the reward be? Should I reward myself with a piece of tiramisu? Since I am trying to persuade myself that sugar is bad, I shouldn’t create a situation that makes sugar desirable. So rewarding with food won’t work. Should I buy myself something? If I really want it, I will buy it anyway.

I’ve been thinking about a plan for a long time. Finally I realized that I should find other people to reward me. I do have a lot of friends, and I came up with an idea of how they could help.

The next time I saw my friend Hillary I asked her if she wanted to sponsor my new exercise plan. She said, “I’m in,” without even hearing the plan. Hillary is a true friend. This is what she blindly signed up for.

I decided to push myself to exercise five hours a week. Because of weather and health fluctuations, I pledged to spread 20 hours of exercise over four weeks. I will sent Hillary weekly reports of what I do. This is in itself a huge motivating factor. After the four weeks, we will go to lunch together, which is a great reward for me to look forward to. If I succeed with my plan, she pays for lunch. If I fail, I pay.

Once I saw how enthusiastic Hillary was, I lined up four other friends for the next four-week periods. I hope that after several months of exercise, I will learn to enjoy it. Or at least, I will start feeling the benefits and that itself will be a motivating factor.

Hillary liked my plan so much that she designed a similar exercise plan for herself. Now I am looking forward to two lunches with Hillary.

I was driving on Mass Pike, when the cars in front of me stopped abruptly. I hit the brakes and was lucky to escape the situation without a scratch.

Actually, it wasn’t just luck. First of all, I always keep a safe distance from the other cars. Second, if I see the brake lights of the car in front of me, I automatically remove my foot from the gas pedal and hold it over the brake pedal until I know what the situation is.

On a highway, if the car in front of me has its brake lights on, usually that means that the driver is adjusting their speed a little bit. So, most of the time I don’t have to do anything. Seeing that the car in front of me has its brake lights on is not a good predictor of what will happen next. Only after I see that the distance between me and the car in front of me is decreasing rapidly, do I know to hit my brakes. That means that brake lights alone are not enough information. Differentiating between insignificant speed adjustments and serious braking requires time and can cost lives.

I have a suggestion. Why not create smart brake lights. The car’s computer system can recognize the difference in the strength with which the brakes are hit and the lights themselves can reflect that. They can be brighter or a different color or pulsing, depending on the strength of the pressure.

The drivers behind will notice these things before they will notice the decrease in the distance. This idea could save lives.

I recently posted the following 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 than all the genuine coins, which weigh the same. There are two balance scales that can be used in parallel. Each weighing lasts one minute. What is the largest number of coins N for which it is possible to find the fake coin in five minutes?

The author’s solution in Russian is available at his blog. Also, two of my readers, David Reynolds and devjoe, solved it correctly.

Here I want to explain the solution for any number of required weighings.

It is easy to see that for n weighings the information theoretical bound is 5ⁿ. Indeed, each weighing divides coins into five groups: four pans and the leftover pile. To distinguish between coins, there can’t be two coins in the same pile at every weighing.

Suppose we know the faking potential of every coin, that is, each coin is assigned a value: potentially light or potentially heavy. If a potentially light coin is ever determined to be fake, then it must be lighter than a real coin. The same story holds for potentially heavy coins. How many coins with known potential can we process in n weighings?

If all the coins are potentially light then we can find the fake coin out of 5ⁿ coins in n weighings. What if there is a mixture of coins? Can we expect the same answer? How much more complicated could it be? Suppose we have five coins: two of them are potentially light and three are potentially heavy. Then on the first scale we compare one potentially light coin with the other such coin. On the other scale we compare one potentially heavy coin against another potentially heavy coin. The fake coin can be determined in one weighing.

The discussion above shows that there is a hope that any mixture of coins with different potential can be resolved. After each weighing, we want the number of coins that are not determined to be real to be reduced by a factor of 5. If one of the weighings on one scale is unbalanced, the potentially light coins on the lighter pan, plus the potentially heavy coins on the heavier pan would contain the fake coin. We do not want this number to be bigger than one-fifth of the total number of coins we are processing. So we divide coins in pairs with the same potential, and from each pair we put the coins on different pans of the same scale. So in one weighing we can divide the group into five equal groups. If there is an odd number of coins with the same potential, then the extra coin doesn’t go on the scales.

The only thing that we is left to check is what happens if the number of coins is small. Namely, we need to check what happens when the number of potentially light coins is odd and the number of potentially heavy coins is odd, and the total number of coins is not more than five. In this case the algorithm requires us to put aside the extra coin in each group, but the put-aside pile can’t have more than one coin.

After checking small cases, we see that we can’t resolve the problem in one weighing when there are 2 coins of different potential, or when the 4 coins are distributed as 1 and 3.

On the other hand, if we have extra coins that are known to be real, then the above cases can be resolved. Hence, any number of coins with known potential greater than four can be resolved in ⌈log₅n⌉ weighings.

Now let’s go back to the original problem in which we do not know the coins’ potential at the start. After a weighing, if both scales balance, then all the coins on the scale are real and the fake coin is in the leftover pile and we do not know its potential. If a scale doesn’t balance then the fake coin is in one of its two pans: the lighter pan has coins that are potentially light and the heavier pan has coins that are potentially heavy.

Let’s add an additional assumption to the original problem. Suppose we have an unlimited supply of coins that we know to be real. Let u(n) be the maximum number of coins we can process in n weighings if we do not know their potential.

What would be the first weighing? Both scales might be balanced, meaning that the fake coin is in the leftover pile of coins with unknown potential. So we have to leave out not more than u(n−1) coins. On the other hand, exactly one scale might be unbalanced. In this case, all the coins on this scale will get their potential known. The number of these coins can’t be more than 5^n-1. But this is an odd number, so we can use one extra real coin to make this number even, in order to put the same number of coins in each pan on this scale.

So u(n) = 2 · 5^n-1 + u(n−1), and u(1) = 3. This gives the answer of (5ⁿ+1)/2. Now we need to go back and remember that we got this bound using an additional assumption that we have an unlimited supply of real coins. Looking closer, we do not need our additional supply of real coins to be unlimited; we just need not more than two real coins. The good news is that we will have these extra real coins after the first weighing. The bad news is that for the first weighing we do not have extra real coins at all. So in the first weighing we should put unknown coins against unknown coins, not more than 5^n-1 on each scale, and as the number on each scale must be even, the best we can do is put 5^n-1−1 coins on each scale.

Thus the answer is (5ⁿ−3)/2 for n more than 1.

We can generalize this problem to any number of scales used in parallel. Suppose the number of scales is k. Suppose the number of weighings is more than 1, then the following problems can be solved in n weighings:

• If all the coins have known potential, then the maximum number of coins that can be resolved is (2k+1)ⁿ.
• If we do not know the potential of any coin and there is an unlimited supply of real coins, the maximum number of coins that can be solved is defined by a recursion: u(n) = k (2k+1)^n-1 + u(n−1) and u(1)=k + 1. So the answer is: ((2k+1)ⁿ+1)/2.
• If we do not know the potential of any coin and there is no extra real coins, then the answer is u(n) − k = ((2k+1)ⁿ+1)/2 − k.

The methods I described can be used to answer another common question in the same setting: Find the fake coin and say whether it is heavier or lighter. Let us denote by U(n) the number of coins that can be resolved in n weighings when there is an unlimited supply of extra real coins. Then the recurrence for U(n) is the same as the recurrence for u(n): U(n) = 2·5^n-1 + U(n−1). The only difference is in the initial conditions: U(1) = k. This means that U(n) = ((2k+1)ⁿ−1)/2. If we don’t have extra real coins then the answer is: U(n) = ((2k+1)ⁿ−1)/2 − k.

When we don’t need to say whether the fake coin is heavier or lighter, we can add one extra coin to the mix: the coin that doesn’t participate in any weighing and is fake if the scales always balance.