Tanya Khovanova's Math Blog

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?

You are given N coins such that two of them are fake and the other coins are genuine. Real coins weigh the same. Fake coins weigh the same and are lighter than real ones. You need to find both fake coins using a balance scale in the smallest number of weighings.

It is easy to estimate the number of weighings from below using information theory. Given N coins you will have N choose 2 different answers. The number of possible answers has to be not more than 3^w, where w is the number of weighings. This generates a trivial information-theoretic bound (ITB) on the number of coins that can be processed in a given number of weighings.

Previous authors used computers to completely analyze small numbers of weighings: from 2 to 5.

My colleagues from Russia, Konstantin Knop and Oleg Polubasov, performed some fantastic programming accompanied with some subtle heuristic and found optimal solutions for up to 10 weighings. For 11 and 12 weighings, the program is not efficient enough to find the optimal solutions: it found some solutions. Surprisingly, for up to 10 weighings, the optimal solutions match the information-theoretic bound (ITB). The results are in the table below. The first row represents the number of weighings w. The second row is the largest number of coins N for which a solution is found. The last row is the information-theoretic bound (ITB) we explained above.

Their paper, Two counterfeit coins revisited, is available in Russian. Lucky for us, 70 of 73 pages are pseudo-code of solutions for which you do not need any Russian. You just need to understand the pseudo-code. Here is the explanation.

Each line begins with its number. After it they have the weighing in the format 1 10 v 4 5 meaning coins 1 and 10 are weighed versus coins 4 and 5. Each weighing is followed by a colon, after which they describe in order actions for three different outcomes of the weighing: equality, the first pan is lighter, and the second pan is lighter. Each action is one of the following:

• => L means go to line L.
• (a, b) means the fake coins are a and b.
• – means this branch is impossible and there is no output.
• => 23. sym indicates the symmetry of the weighing and its result, therefore the resulting go-to line, 23, is omitted as being equivalent to another line.
• – . sym means the output is symmetric to another one.

The line numbers after => in line L are always 3L+1, 3L+2 and 3L+3. The sym symbol implies that line 3L+3 is omitted as a symmetric version of line 3L+2.

For example, here is their solution for 2 weighings and 4 coins in their pseudo-code. An empty line separates different weighings:

0. 1 v 2 : => 1, => 2, => 3. sym

1. 1 v 3 : – , (1, 2), (3, 4).
2. 3 v 4 : – , (1, 3), – . sym

Another solution for 3 weighings and 7 coins:

0. 1 2 v 3 4 : => 1, => 2, => 3. sym

1. 1 v 2 : => 4, => 5, => 6. sym
2. 1 v 2 : (1, 2), => 8, => 9. sym

4. 5 v 6 : (5, 6), (5, 7), – . sym
5. 3 v 4 : – , (1, 3), – . sym
8. 5 v 6 : (1, 7), (1, 5), – . sym

If you want to see an optimal solution for 10 weighings, look at the paper: the algorithm takes 36 pages.

I want to come back to a middle-school Olympiad problem I posted a while ago.

Streamline School Olympiad 2000 (8th grade). You have six bags of coins that look the same. Each bag has an infinite number of coins and all the coins in the same bag weigh the same amount. Each different bag contains coins of a different weight, ranging from 1 to 6 grams exactly. There is a label (1, 2, 3, 4, 5, 6) attached to each bag that is supposed to correspond to the weight of the coins in that bag. You have only a balance scale. What is the least number of times you need to weigh the coins in order to confirm that the labels are correct?

The answer is unpretentious: one weighing is enough. We can take one 5-gram coin, two 4-gram coins, three 3-gram coins, four 2-gram coins and five 1-gram coins for the total of 35 grams. This number is not divisible by 6, so we can add one more 1-gram coin and weigh all of them against six 6-gram coins. I leave it to the reader to show that this solution works and to extrapolate the solution for any number of bags.

My new challenge is to find a weighing for the above problem using the smallest number of coins. What is the number of coins in such a weighing for a given number of bags?

I manually calculated this number for a small number of bags, but I would like to get a confirmation from my readers. Starting from 6 bags, I don’t know the answer. Can you help me?

I recently wrote a post about the ApSimon’s Mints problem:

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. Therefore, fake coins weigh the same no matter where they’ve been minted. 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 in order to 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?

The post was accompanied by my paper Attacking ApSimon’s Mints.

Unfortunately, both the post and the paper contain wrong information. They both state that the number of coins as a sequence of the number of mints is 1, 2, 4, 8, 15, 38, 74. This is wrong. I took this data from the sequence A007673 in the OEIS database. The sequence had incorrect data lying dormant for 20 years. I believe that the sequence was generated from the paper of R. K. Guy and R. J. Nowakowsky, ApSimon’s Mints Problem, published in Monthly in 1994. To the credit of Guy and Nowakowsky, they never claimed to find the best solution: they just found a solution, thus providing a bound for the sequence. Someone mistook their solution for the optimal one and generated the sequence in the database.

After my post, my readers got interested in the problem and soon discovered the mistake. First Konstantin Knop found a solution for 6 mints with 30 coins and for 7 mints with 72 coins. Konstantin is my long-time collaborator. I trust him so I was sure the sequence was flawed. Then someone located a reference to a paper in Chinese A New Algorithm for ApSimon’s Mints Problem. Although none of my readers could find the paper itself nor translate the abstract from Chinese. But judging from the title and the formulae it was clear that they found better bounds than the sequence in the database. My readers got excited and tried to fix the sequence. David Reynolds improved on Konstantin’s results with a solution for 6 mints with 29 coins and for 7 mints with 52 coins. David did even better on his next try with 28 and 51 coins correspondingly. He also found a solution with 90 coins for 8 mints. Moreover, his exhaustive search proved that these were the best solutions.

Now the sequence in the database is fixed. It starts 1, 2, 4, 8, 15, 28, 51, 90.

For future generations I would like to support each number of the sequence by an example. I use the set P(Q) to represent the sequence of how many coins are taken from each mint for the first(second) weighing. For one mint, only one coin and one weighing is needed. ApSimon himself calculated the first five values, so they were not in dispute.

• a(2) = 2: P=(1,0) and Q=(0,1). Found by ApSimon.
• a(3) = 4: P=(0,1,2) and Q=(1,1,0). Found by ApSimon.
• a(4) = 8: P=(0,1,2,3) and Q=(1,0,2,2) or P=(0,1,1,4), Q=(2,0,1,1). Found by ApSimon.
• a(5) = 15: P=(0,1,1,4,5) and Q=(2,1,2,5,0). Found by ApSimon.
• a(6) = 28: P=(1,2,2,5,5,0) and Q=(0,1,2,1,8,10). Found by Robert Israel, Richard J. Mathar, and David Reynolds,
• a(7) = 51. P=(2,3,7,2,8,12,0) and Q=(0,2,1,7,7,12,12). Found by David Applegate and David Reynolds.
• a(8) = 90. P=(4,6,6,7,3,13,15,3) and Q=(4,0,1,6,12,12,1,27). Found by David Applegate and David Reynolds.

There is a solution for nine mints using 193 coins that is not confirmed to be optimal. It was found by David Reynolds: P=(1,2,4,12,5,4,20,39,43) and Q=(0,1,3,3,25,33,34,18,27). In addition, David Reynolds provided a construction that reduces the upper bound for n mints to (3⁽ⁿ⁺¹⁾−2n−3)/4. The following set of coins work: P=(1,3,7,15,…,2ⁿ−1) and Q=(1,4,13,40,…,(3ⁿ−1)/2).

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 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.

I recently published the following coin puzzle:

There are four silver coins marked 1, 2, 3, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

My readers, David Reynolds and ext_1973756, wrote to me that I am missing a coin of 4 grams. Indeed, the same puzzle with five coins—1, 2, 3, 4, and 5—is a more natural and a better puzzle.

David Reynolds also suggested to go all the way up to 9 coins:

There are nine silver coins marked 1, 2, 3, 4, 5, 6, 7, 8, and 9. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is lighter than it should be. Find the fake coin using the balance scale twice.

It is impossible to resolve this situation with more than nine coins as two weighings provide nine different answers to differentiate coins. But indeed it is possible to solve this problem for nine coins. It is even possible to suggest a non-adaptive algorithm, that is to describe the weighings before knowing the results.

To find such a strategy we need to satisfy two conditions. First, we have to weigh groups of coins of the same supposed weight, otherwise we do not get any useful information. Second, there shouldn’t be any two coins together (in or out of the pan) in both weighings, because it would then be impossible to differentiate between them.

Here is one possible solution of the problem:

• The first weighing: 1, 5, and 9, against 2, 6, and 7
• The second weighing: 1, 6, and 8, against 2, 4, and 9

David Reynolds also suggested a problem in which we do not know whether the fake coin is heavier or lighter:

There are four silver coins marked 1, 2, 3, and 4. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

Again, four coins is the best we can do when in addition to find it, we also want to determine if it is heavier or lighter. Indeed, if there were five coins we would have needed to cover ten different answers, which is too many for two weighings.

Here is the solution for four coins:

The two weighings are 1+3=4, and 1+2=3. If the first weighing balances, then the fake coin is 2 and the second weighing shows if it is heavier or lighter than it should be. Similarly, if the second weighing balances, then the fake coin is four and we can see whether it is heavier or lighter than it should be. If the left pan is lighter/heavier for both weighings, then the fake coin is 1 and is lighter/heavier. But if one pan is heavier on the first of two weighings and the other pan is heavier on the second weighing, then the fake coin is 3. In both cases it is easy to determine whether the fake coin is heavier or lighter.

Now David is missing a coin. If we just want to find the fake coin without determining whether it is heavier of lighter, we can do it with five coins:

There are five silver coins marked 1, 2, 3, 4, and 5. They are supposed to weigh the number of grams that is written on them. One of the coins is fake and is either lighter or heavier than it should be. Find the fake coin using the balance scale twice.

We can use the same solution as the previous (four coins) problem. If the scale balances both times, then the fake coin is 5. However, in this case we will not know whether the coin is heavier or lighter.

We can’t extend this problem to beyond five coins. Suppose we have six coins. We can’t use more than three coins in the first weighing. This is because if the scale unbalances, we can’t resolve more than three coins in one remaining weighing. Suppose the first weighing balances; then we have at least three leftover coins we know nothing about and one of them is fake. These three coins should be separated for the next weighing. That means one of the coins needs to be on the left pan and one on the right pan. We can add real coins any way we need. But if the second weighing unbalances we do not know if the fake coin is on the left and lighter or on the right and heavier.

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?

The ultimate goal of each MIT Mystery Hunt is to find a hidden coin. So it was highly appropriate that our 2013 team created a coin-weighing puzzle (written by Ben Buchwald, Darby Kimball, and Glenn Willen) as a final obstacle to finding the winning coin:

There are nine coins, one real and eight fake. Four of the fake coins weigh the same and are lighter than the real coin. The other four fake coins weigh the same and are heavier than the real coin. Find the real coin in seven weighings on the balance scale.

Actually, it is possible to find the real coin in six weighings. Can you do that?

Baron Münchhausen is famous for his tall tales. My co-author Konstantin Knop wants to rehabilitate him and so invents problems where the Baron is proven to be truthful from the start. We already wrote a paper about one such problem. Here is a new problem by Konstantin:

Kostya has a black box, such that if you put in exactly 3 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 5 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than 3 times?

Actually, Konstantin designed a more complicated problem that was given at the Euler Olympiad, 2012 in Russia.

Let n be a fixed integer. Kostya has a black box, such that if you put in exactly 2n+1 coins of distinct weights, the box will expose the coin of median weight. The Baron gave Kostya 4n+1 coins of distinct weights and told him which coin has the median weight. Can Kostya check that the Baron is right, using the box not more than n+2 times?

Note that Kostya can’t just put 4n+1 coins in the box. The box accepts exactly 2n+1 coins. The problem that I started with is for n = 1. Even such a simple variation was a lot of fun for me to solve. So, have fun.