Tanya Khovanova's Math Blog

If like me, you fancy Raymond Smullyan and his books, then you’ve heard about knights and knaves. Knights always tell the truth and knaves always lie. In addition to knights and knaves, there are normal people who sometimes tell the truth and sometimes lie. Here is a puzzle.

Puzzle. How, in one sentence, can a normal person prove that they are normal?

We can draw a parallel between people and coins. We can say that knights correspond to real coins, and knaves to fake coins that are lighter than real ones. Inspired by normal people, my coauthor Konstantin Knop invented chameleon coins. Chameleon coins can change their weight and behave like real or fake coins. I just wrote a post about chameleon coins.

Normal people are too unpredictable: they can consistently pretend to be knights or knaves. So logicians invented a simpler type of person, one who switches from telling the truth in one sentence to a lie in the next and then back to the truth. Such people are called alternators. Here is another puzzle:

Puzzle. You meet a person who is one of the three types: a knight, a knave, or an alternator. In two questions, find out which type they are.

Continuing a parallel between people and coins we can define alternator coins: the coins that switch their weight each time they are on the scale from weighing as much as real ones to weighing as much as fake ones. For the purposes of this essay, we assume that the fake coins are lighter than real ones. Unlike the chameleon coin, which might never reveal itself by always pretending to be real, the alternators can always be found. How do you find a single alternator among many real coins? There is a simple strategy: repeat every weighing twice. This strategy allows us to find an alternator among 9 coins in four weighings. Can we do better?

I used the alternator coins as a research project for my PRIMES STEP program where we do math research with students in seventh and eighth grade. The students started the alternator project and immediately discovered the strategy above. The next step is to describe a better strategy. For example, what is the maximum number of coins containing one alternator such that the alternator can always be found in four weighings?

But first we count possible outcomes. Suppose there is a strategy that finds an alternator. In this strategy we can’t have two unbalanced weighings in a row. To prove that, let us suppose there was an unbalanced weighing. Then the alternator switches its weight to a real coin and whether or not the alternator is on the scale, the next weighing must balance. The beauty of it is that given a strategy each outcome has to point to a particular coin as an alternator. That means the number of outcomes bounds the total number of coins that can be processed.

Counting the number of possible outcomes that do not have two unbalances in row is a matter of solving a recurrence, which I leave to the readers to find. The result is Jacobshtal numbers: the most beautiful sequence you might never have heard of. For example, the total number of possible outcomes of four weighings is 11. Since each outcome of a strategy needs to point to a coin, the total number of coins that can be processed in four weighings is not more than 11. But 11 is better than 9 in our previous strategy. Can we process 11 coins in four weighings? Yes, we can. I will describe the first part of the strategy.

So we have 11 coins, one of which is an alternator. In the first weighing we compare 5 coins against 5 coins. If the weighing unbalances, the alternator is on a lighter pan. Our problem is reduced to finding the alternator among five coins when we know that it is in the real state. If the weighing balances, then we know that if the alternator is among the coins on the scale it must now be in the light state. For the second weighting, we pick two sets of three coins out of this ten coins and compare them against each other. Notice that 3 is a Jacobsthal number, and 5, the number of coins outside the scale, is also a Jacobsthal number. If the second weighing balances, the alternator must be among 5 coins outside the scale. All but one of these coins are in the light state, and I leave it to the readers to finish the strategy. If the weighing unbalances, we need to find the alternator among 3 coins that are in the real state now. This can be done in two weighings, and again the readers are to the rescue.

It appears that Jacobsthal numbers provide the exact lower bound of the number of coins that can be processed. This is what my middle-schoolers discovered and proved. We wrote a paper on the subject. The strategy in the paper is adaptive. That means it changes depending on the results of the previous weighings. Can we find an oblivious strategy? I will tell you in later posts.

Suppose we have 3ⁿ identical-looking coins. One of the coins is fake and lighter than the other coins which all are real. We also have a random scale. That is a scale that at each weighing behaves randomly. Find the fake coin in the smallest number of weighings. Oops! That won’t work! It is impossible to find the fake coin. The scale can consistently misbehave in such a way as to blame a specific real coin for being fake.

Let’s try something else. Suppose we have two scales: one normal and one random. Find the fake coin.

What am I thinking? The normal scale can point to one coin and the random scale can point to another coin and we are in a “she said, he said” situation which we can’t resolve.

Now, in my final try, I’ll make it right. We actually have three scales, one of which is random. So here we go, with thanks to my son Sergei for giving me this puzzle:

Puzzle. We have 3ⁿ identical-looking coins. One of the coins is fake and lighter than the other coins, which all are real. We also have three scales: two normal and one random. Find the fake coin in the smallest total number of weighings.

Let’s start with this strategy: repeat every weighing on all three scales and have a majority vote. At least two of the scales will agree, thus pointing to the true result. This way we can use a divide-into-three-equal-groups strategy for one scale to find the fake coin. It will require 3n weighings.

Can we do better? Of course, we can. We can repeat every weighing on two scales. If they agree we do not need the third scale. If they do not agree, one of the scales is random and lying, and we can repeat the weighing on the third scale to “out” the random scale. After we identify one normal scale, the process goes faster. In the worst case we will need 2n + 1 weighings.

Can we do even better? Yes, we can. I will leave it to the readers to find a beautiful solution that is asymptotically better than the previous one.

Update on Dec 24, 2016. The total number of coins should be 3²ⁿ, not 3ⁿ. We are looking at the worst case scenario, when the random scale is adversarial.

We all have played with problems in which we had real coins and fake (counterfeit) coins. For this post I assume that the fake coins are always lighter than the real coins. My coauthor Konstantin Knop invented a new type of a coin: a chameleon coin. This coin can mimic a fake or a real coin. It can also choose independently which coin to mimic for each weighing on a balance scale.

You cannot find the chameleon coin in a mix with real coins if it does not want to be found, because it can consistently behave as a real coin. Let’s add classic fake coins to the mix, the ones that are lighter. Still the task of identifying the chameleons using a balance scale cannot be achieved: the chameleons can pretend to be fake coins. We can’t identify the fake coins either, as the chameleons can mess things us up by consistently pretending to be fake.

What we can do is to find a small number of coins some of which are guaranteed to be fake. Consider the simplest setup, when we have one fake coin and one chameleon in our mix of N coins. That is we have N − 2 real coins. Our task now is to find TWO coins, one of which has to be fake. As usual we want to do it in the smallest number of weighings that guarantees that we’ll find the two coins. Let me give you a fun problem to solve:

Puzzle. The total number of coins is four. And as above we have one chameleon and one classic fake. In two weighings find two coins so that one of them is guaranteed to be fake.

If you want to learn more, we just wrote a paper titled Chameleon Coins.

* * *

—Honey, we are like two parallel lines.
—Why do you say that?
—The intersection of our life paths was a mistake.

* * *

—Q: Why did the obtuse angle go to the beach?
—A: Because it was over 90 degrees.

* * *

Ancient Roman in a clothing store: How come XL is larger than L?

* * *

—Which is the odd one out: one, three, six, seven?
—Well, three of them are odd ones.

* * *

When I am with you, I solve integrals in my head, so that blood can come back to my brain.

* * *

There are two kinds of people in this world: Those that can extrapolate from incomplete data.

* * *

Seven has the word even in it, which is odd.

I have always wanted to be an honest person and have followed my honor code. Soviet Russia had two honor codes. One code was for dealing with people and the other for dealing with businesses and the government. I remind you that in Soviet Russia, all businesses were owned by the government. The money paid for work didn’t have any relation to the work done. The government paid standard salaries and the businesses did whatever. Generally, that meant that they were doing nothing. Meanwhile, the government got its income from selling oil.

All people were being screwed by the government, so they had no motivation to play fair. Just as American workers do, Soviet Russians might use the work copier to make personal copies. The difference was that we didn’t feel guilty at ripping off the government. We wouldn’t just make a few necessary copies; we would make copies for our friends, our family, for strangers—as many copies as possible.

I moved to the United States in 1990. Several of my friends took time to explain to me the difference between Soviet Russia and the US. One of the friends, let’s call her Sarah, was working as staff at Harvard University. She told me the story of a recent visit by a famous Russian professor. After he left, the department received a bill. It appears that the professor, in a short visit, used several months-worth of the department’s budget allocation for copying and phone calls. I was impressed, in a good way, by the professor who I assume spent a good deal of his time making a lot of copies of papers unavailable in Russia, presumably not only for himself but also for students and colleagues. On the other hand, it was clearly wrong.

My new friend Sarah told me that in the US money does not come from nowhere, and I should include Harvard University in my honor code for people. Actually, not only Harvard, but also any place of work and the government too. Sarah also told me that since that budget problem, she was asked to talk to every incoming Russian visitor and explain to them how capitalism works. Most Russian visitors were ready to accept the rules. I too was delighted with that. It is much easier to follow one honor code than two.

I was also very happy for my son, Alexey. He was eight when we moved to Boston. Before our move I had a dilemma. Should I tell him that Lenin and Stalin were bad guys and killed millions of people? If I gave him a truthful explanation, I would also have to teach him to lie. Otherwise, if he mentioned this at school or on the street, we would be at risk of going to prison. If I didn’t teach him the truth, he might become brainwashed and grow up believing in communism, which would be very, very bad.

I was so lucky that I moved to the US: I didn’t have to teach my son to lie.