Insights puzzle

Seeking Mathematical Truth in Counterfeit Coin Puzzles

By Pradeep Mutalik

July 29, 2022

Readers balanced logical reasoning and mathematical insights to find phony coins with a double-pan balance scale.

James Round for Quanta Magazine

Our recent suite of puzzles featured the humble double-pan balance scale, historically a symbol of commerce and government, art and science. Balance scales are also popular in recreational mathematics. Balance puzzles require clear, logical reasoning and lend themselves well to mathematical generalization. Let’s see how Quanta readers balanced these qualities in the puzzles below.

Puzzle 1

You have eight identical-looking coins. One is counterfeit and lighter than the others, which have identical weights. Find the bad coin in two weighings. Find the general formula for the maximum number of coins for which you can find the counterfeit one in x weighings.

Tackling a simple version of a problem often reveals the key to the solution. In this case, imagine that you have just three coins, with one lighter than the other two. If you weigh any one of them against one of the other two, either they will balance or they won’t. If they don’t, you know which is lighter. If they do balance, then the third one is the light one. You only need a single weighing.

So in this puzzle, if you can isolate a group of three (or fewer) containing the light coin in the first weighing, you will just need one more weighing. You can do this by balancing any three against any other three. If the two groups are unbalanced, you’ve found the group containing the light one and can proceed as above for the second weighing. If they balance, just weigh the remaining two coins against each other, and you’ll find the light one.

Notice that this also works if there are three in the unweighed group, so we could have started with nine coins. Following this logic, and starting with three coins, for each additional weighing we can find the light coin in three times the number of coins we previously had. The formula giving us the maximum number of coins n in w weighings is therefore n = 3^w.

Puzzle 2

You have 12 identical-looking coins. One is either heavier or lighter than the others, which have identical weights.

1. Find the bad coin in three weighings.

2. What is the maximum number of coins for which you can find the bad one in four weighings? Describe how you would find the fake coin.

The solution to this puzzle was well described by Ted, who also showed that you can actually detect the bad coin among 13 coins in three weighings. Here’s Ted’s solution (with indentations to separate the three weighings in each case):

Start by weighing 4 coins vs 4 coins.

Case 1: If unbalanced, for the second weighing put 2 each of the heavier side on both sides of the scale along with 1 each of the lighter side.

1a: If unbalanced, the bad coin is either the 2 coins still on the heavy side or the single coin still on the light side.

Weigh the 2 possible heavy coins, the bad one is either the heavier of the two, or the single light one if they are balanced.

1b: If second weighing is balanced, the bad coin is one of the 2 unused from the lighter side of the first weighing.

Weigh them against each other, the lighter one is bad.

Case 2: If balanced, the bad coin is one of the 5 remaining. Weigh 3 of those against any 3 already weighed (which are known [to be] good).

Case 2a: If unbalanced, you know the bad coin is one of those 3 and whether it’s light or heavy.

The third weighing is any 2 of those against each other — if unbalanced, that identifies the bad coin, if balanced it’s the last of the three.

Case 2b: If the second weighing is balanced, the bad coin is one of the remaining 2.

Weigh either of them against a known good coin. If this result is unbalanced, this new coin is bad and you know whether it is heavy or light. If this result is balanced, the 13th coin is bad, but it is unknown whether it’s heavy or light (which we don’t need to know, so we’re done).

Ted also went on to show that the maximum number of coins for four weighings is 40. The formula for this puzzle is: n = (3^w − 1)/2.

For the remaining puzzles, the generalized formulas are still under investigation by professional mathematicians and are the subject of published papers, some of which have been cited by Rainer aus dem Spring. I will confine myself to solutions for the small numbers of coins we consider in the puzzles and will only mention generalizations that follow naturally from the methods used in these cases.

Puzzle 3

This is a variation of puzzle 1. You again have eight identical-looking coins, one of which is lighter than the others. However, now you have three scales. Two of the scales work, but the third is broken and gives random results (it is sometimes right and sometimes wrong). You do not know which scale is broken. How many weighings will it take to find the light coin?

As we saw in problem 1, this takes just two weighings with a good balance. We also know that the two good balances will always agree, so if we just repeat each weighing on all three balances, we will have the answer in six weighings as a reader suggested. If we try to do it in a smaller number of weighings, it gets a little tricky. We cannot identify a good scale just by weighing the same coins on two scales, because even if they agree, either of the two might still be a bad scale. (This also shows how easily misinformation or random information can obfuscate the truth.)

In fact, this problem can be solved, very cleverly, in just four weighings! Rainer aus dem Spring posted the solution using a newfangled notation that seems to have been created for this puzzle. But before you go there, I want you to imagine a scenario that I hope will make things more intuitive.

Imagine you’re a detective investigating a hit-and-run in a tiny country whose cars have two-digit license plates using only the digits 0, 1 and 2. Three people, A, B and C, have observed the incident. Two of them always answer a three-choice question correctly, and one gives completely random answers. You do not know who the random answerer is. You have to ask each of them a single three-choice question and then pick the one who is definitely telling the truth to get more information.

Here’s how you do it. Ask A if the first digit is 0, 1 or 2. Let’s say A says 2. Ask B if the second digit is 0, 1 or 2. Let’s say B says 1. Then ask C to make a choice between these three statements:

• Only A is telling the truth.
• Only B is telling the truth.
• Both are telling the truth.

You can believe the one that C tells you to and question that person about the other digit. To see why, consider that if A is lying, then C is reliable and will say that B is telling the truth. The second digit will in fact be 1 and you can then question B about the first digit. Similarly, if B is lying, then C is again reliable and will say that A is telling the truth. Then the first digit is in fact 2 and you can question A about the second digit. Finally, if C is lying, then both A and B are reliable, so you can still believe and pick whomever C says to. (And if C says both A and B are telling the truth, then they both must be.) The key here is that your choice of questions does not allow C to lie in such a way as to cast doubt on both A and B. Since at least one of A and B must be reliable, you can always pick the one that C agrees with, even if it is just a random answer. If all three of them agree, then you already have both digits of the license plate.

Here’s how to translate this tale back to our puzzle. The scales are A, B and C. You can translate the two digits of the license plate to the coins as follows: 01 is coin 1, 02 is coin 2, 10 is coin 3, 11 is coin 4, 12 is coin 5, 20 is coin 6, 21 is coin 7 and 22 is coin 8. Astute readers will recognize that this is the base 3 (or ternary) number system. Also note that there is an additional possible number 00, which you can use for a ninth coin for which this technique will also work, as in puzzle 1.

For the first weighing, you divide the coins by their first (base 3) digit, so your three groups will be coins [1, 2], [3, 4, 5] and [6, 7, 8]. Weigh [3, 4, 5] against [6, 7, 8] on scale A. If A is working well, you will have the correct first digit group as in puzzle 1. Similarly, for the second weighing on scale B your groups will be those with the same second digit: [1, 4, 7], [2, 5, 8] and [3, 6]. If B is working well, you’ll have the correct second digit. For the third weighing, on scale C, you weigh the group that A identified against the group that B did. Following our example, for 21, the groups will be [6, 7, 8] and [1, 4, 7]. Coin 7 cannot be put on both sides at the same time, so we leave it out and weigh [6, 8] and [1, 4] against each other. Note that if A and B are both reliable, then 7 is in fact the correct answer, and it doesn’t matter which side comes out lighter on C. If by chance the weighing on C is balanced, then all three scales agree, and you have your answer (coin 7) in just three weighings. If A is reliable and B is not, the lighter coin is in [6, 8], which scale C will confirm, and if B is reliable and A is not, the lighter coin is in [1, 4], which scale C will also confirm.

So in three weighings we have either identified the light coin or narrowed it down to a group of two, and we have also identified a working scale. The fourth weighing on either scale A or scale B (whichever one scale C agreed with) will do the rest.

This solution strikes me as amazingly beautiful!

This method can be generalized to find the light coin among 3^2x coins in 3x + 1 weighings with the given set of balance scales. Thus, you need seven weighings for 81 coins. For larger numbers of coins (>~1,000), an even stronger solution exists.

Puzzle 4

You have 16 coins, eight of which are heavy and of the same weight. The other eight are light and of the same weight. You do not know which coins are heavy or light. The coins look identical except for one that has special markings. With one good scale, can you figure out if the special coin is light or heavy in three weighings? What’s the maximum number of coins you can start with and successfully solve this problem in four weighings?

At first sight, this puzzle seems almost impossible to do in three weighings, as one of our readers concluded. Nevertheless, with some cleverness it can be done, and both Ted and Rainer aus dem Spring provided correct solutions. Ted provided some invaluable general principles which are worth paying attention to.

First, until you get an unbalanced result from a weighing, you won’t have enough information to determine if the special coin is heavy or light. So you have to try and force an unbalanced result.

Second, if you get a balanced result (say the special coin A balances coin B), you can combine the coins that are balanced and weigh them against two more coins, C and D. If they are unbalanced, you have the answer; otherwise, you have now doubled the number of coins that are similar, which might help you get an unbalanced answer in the next weighing. You can also carry out this process in reverse with numbers of coins that are powers of two (4, 8, etc.) if you have an initial unbalanced result as seen in the following solution.

Below is the entire procedure that can identify the type of the special coin A in all cases in three weighings. (B, C and D are three coins placed on the same side as A in weighing 1 (W1); X and Y are the two coins not used in W1.)

This puzzle was invented by the Russian mathematician Konstantin Knop, a world authority on coin-weighing puzzles. Many of his papers are in Russian, but you can find several coin puzzles (among other interesting puzzles) on the blog of his collaborator Tanya Khovanova.

As for generalization, I’ll leave it to you to see if this same method works for finding the type of a special coin among 32 coins, of which 16 are heavy and 16 are light.

Puzzle 5

You have n identical-looking coins, some of which are counterfeit and lighter than the others. All you know is that there is at least one counterfeit coin and that there are more normal coins than counterfeit ones. Your job is to detect all the counterfeit coins.

The fact that there is at least one light coin and that there are more normal coins than light ones makes this puzzle less complex than it first appears, at least for small numbers. Let’s look at the numbers of weighings for one to eight coins.

For one and two coins, there can be no light coins per the second condition, so no weighings are required.

Three coins: Only one light coin. One weighing required per puzzle 1.

Four coins: Only one light coin. One additional weighing required, so w = 2.

Five coins: One to two light coins. This is the first interesting case. The question is: Should we weigh one coin against one, or two coins against two?

If we weigh one against one, then we can have:

1. Two unbalanced weighings: Two coins discovered; we are done.
2. One balanced weighing out of two: The balanced coins have to be normal, so the last coin needs another weighing, w = 3.
3. Two balanced weighings: In the third weighing, weigh one coin from each prior weighing against another. If they are balanced, all four are normal, and coin 5 is the light one. We are done; w = 3 again. If they are unbalanced, we’ve found the two light coins, and we are done in three weighings.

If instead we weigh two against two, we still require three weighings, because we have to distinguish between the possibilities that the coins may be dissimilar or similar on either side. Weighings using small numbers of coins grouped together do not appear to have any advantage over weighings with single coins.

This is borne out for:

Six coins: One to two light coins; w = 4.

Seven coins: One to three light coins; w = 5.

Eight coins: One to three light coins; w = 6. This solution has a simple structure:

• First do four weighings of one coin against the next. All coins are used.
• Worst case: All four weighings are balanced (there are two light coins that balance each other).
• Next two weighings: Weigh a coin from weighing 1 against a coin from weighing 2; similarly, weigh a coin from weighing 3 against a coin from weighing 4.
• One of these weighings will be unbalanced, identifying the two light coins. We are done in six weighings.

Sorry, our sequence of 0, 0, 1, 2, 3, 4, 5, 6 is certainly not interesting enough to submit to the On-Line Encyclopedia of Integer Sequences!

As Jonas Tøgersen Kjellstadli pointed out, the solution seems to be w = n − 2 for small numbers, but we haven’t proved that this will not change for larger numbers. At some n, using multiple coin weighings might start doing better, or more weighings than n − 2 may be required. We can simply generalize the solution for eight coins to all powers of 2, giving n − 2 as the upper bound for the number of weighings for all powers of 2.

Mark Pearson discussed the similarity of this problem to error-correcting codes and suggested using an information theory approach based on the number of possible outcomes. Using such an approach, Mike Roberts posted a lower bound for the more general case, which Rainer aus dem Spring derived an approximation for. Rainer also posted an upper bound from a published paper but noted that the bounds are not sharp for low n and therefore not helpful for the small numbers we have considered above. Thus, for seven coins, the bounds cited give a range of 4 to 16, which our answer, 5, falls between. J. Payette gives additional mathematical references and bounds for all the puzzles.

Thank you to all who participated. The Insights prize for this month goes jointly to Ted and Rainer aus dem Spring. Congratulations!

See you next time for new Insights.

from Hacker News https://ift.tt/y82CPnU