Tanya Khovanova's Math Blog

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.

Centaurs, manticores, and minotaurs roam their planet. Their society is very democratic: any two animals can become sex partners. When two different species mate, their orgasm is so potent that they merge into one creature of the third species. For example, once one centaur and one manticore make love, they are reborn as one minotaur. At the beginning of the year 2016 there were 2016 centaurs, 2017 manticores, and 2018 minotaurs. They mated non-stop and at the end of the year only one creature was left on the planet. Which one?

This is one of those puzzles that I love-hate. I hate it because it is easy to answer this puzzle by inventing a specific mating pattern that ends with one animal. It is possible to get the correct answer without seeing the beauty. I love it because there is beauty in the explanation of why, if the mating ends with one animal, it has to be a specific animal.

The solution is charming, but being a mathematician this problem makes me wonder if ii is always possible to end with one animal. So I add another puzzle.

Describe the sets of parameters for which it is impossible to end up with one creature.

Today I have two new coin puzzles that were inspired by my son, Alexey Radul:

You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have a balance scale which might or might not be faulty. A faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of weighings you need in order to figure out whether the scale is faulty?

If you think about it, this problem is isomorphic to a known problem I wrote about before:

You have N ≥ 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is either lighter than the real ones or heavier than the real ones. You also have a normal balance scale. What is the smallest number of weighings you need in order to figure out whether the fake coin is lighter or heavier?

To make things more interesting let’s mix the problems up.

You have N > 2 identical-looking coins. All but one of them are real and weigh the same. One coin is fake and is lighter than the real ones. You also have M > 1 identical-looking balance scales. All but one of them are normal and one is faulty. The faulty scale differs from a normal one in reversing the sense of unbalanced weighings—it shows a lighter pan as heavier and vice versa (but still shows equal-weight pans as weighing the same). What is the smallest number of total weighings needed to figure out which scale is faulty?

The following problem was at a 2016 entrance test for the MIT PRIMES STEP program.

I drew several triangles on a piece of paper. First I showed the paper to Lev and asked him how many triangles there were. Lev said 5 and he was right. Then I showed the paper to Sasha and asked him how many triangles there were. Sasha said 3 and he was right. How many triangles are there on the paper? Explain.

The intended answer was 8: there were 5 triangles on one side of the paper and 3 on the other.

Most of the students didn’t think that the paper might be two-sided, but they came up with other inventive ideas. Below are some of their pictures, and I leave it to you to explain why they work. All the students who submitted these pictures got a full credit for this problem on the test.

Alexander Shapovalov is a prolific puzzle writer. He has a special webpage of his river-crossing puzzles (in Russian). Here is one of these puzzles.

Three swindlers have two suitcases each. They approach a river they wish to cross. There is one boat that can carry three objects, where a person or a suitcase counts as one object. No swindler can trust his suitcase to his swindler friends when he is away, but each swindler doesn’t mind his suitcases left alone at the river shore. Can they cross the river?

Replace question marks with letters in the following sequence:

Y, Y, ?, ?, Y, ?, Y, ?, R, R, R, R.

Problem 1. It is true that it is possible to put positive numbers at the vertices of a triangle so that the sum of two numbers at the ends of each side is equal to the length of the side?

This looks like a simple linear algebra question with three variables and three equations. But it has a pretty geometrical solution. What is it?

Problem 2. Prove that it is possible to assign a number to every edge of a tetrahedron so that the sum of the three numbers on the edges of every face is equal to the area of the face.

Again we have six sides and four faces. There should be many solutions. Can you find a geometric one?

I am running a PRIMES-STEP program for middle school students, where we try to do research in mathematics. In the fall of 2015 we decided to study the following topic in logic.

Suppose there is an island where the following four types of people live:

• Absolute truth-tellers always tell the truth.
• Partial truth-tellers tell the truth with one exception: if they are guilty, they will say that they are innocent.
• Absolute liars always lie.
• Responsible liars lie with one exception: if they are guilty, they will say that they are guilty.

See if you can solve this simple logic puzzle about people on this island.

It is known that exactly one person stole an expensive painting from an apartment. It is also known that only Alice or Bob could have done it. Here are their statements:
Alice: I am guilty. Bob is a truth-teller.
Bob: I am guilty. Alice stole it. Alice is the same type as me.
Who stole the painting and what types are Alice and Bob?

My students and I discovered a lot of interesting things about these four types of people and wrote a paper: Who Is Guilty?. This paper contains 11 cute logic puzzles designed by each of my 11 students.

I envied my students and decided to create two puzzles of my own. You have already solved the one above, so here is another, more difficult, puzzle:

A bank was robbed and a witness said that there was exactly one person who committed the robbery. Three suspects were apprehended. No one else could have participated in the robbery.
Alice: I am innocent. Bob committed the crime. Bob is a truth-teller.
Bob: I am innocent. Alice is guilty. Carol is a different type than me.
Carol: I am innocent. Alice is guilty.
Who robbed the bank and what types are the suspects?

The following cute puzzle of unknown origins was sent to me by Martina Balagovic and Vincent van der Noort:

A car travels from A to B and back again. When going uphill it goes 56 km an hour, when going downhill it goes 72 km an hour and while driving on flat surface it goes 63 km an hour. Getting from A to B takes 4 hours and getting back (over the same road) takes 4 hours and 40 minutes.
What is the distance between A and B?