# Find The Fake Coin

## by Greg Egan

How can you find one fake coin among many, by comparing the weights of various sets of coins, using the smallest possible number of comparisons?

Puzzles like this have a long history, but somehow I never got around to thinking about them until I read this fun set of balance puzzles by Quanta magazine’s columnist Pradeep Mutalik. If you want to read and solve those Quanta puzzles for yourself, DO NOT keep reading the page you are on now, as I am about to reveal a whole lot of spoilers.

### Analysis of the problem

The idea is that we have a collection of n coins, and while the genuine coins are all identical in weight, some number of fake coins among them will have a different weight. We have a balance that lets us directly compare the weights of any two sets of coins from the collection, by placing them in the two pans of the balance and seeing whether one side drops, proving it to be heavier, or whether the pans remain level, proving that they contain equal weights. To be precise, by “any two sets” we mean any two disjoint sets, i.e. sets with no elements in common, since a coin can’t be in both pans at once. But apart from it being impossible to perform such a measurement, the contribution of the shared coins to each set would cancel out, so even in theory there would be no advantage at all to allowing overlapping sets.

In what follows, we will focus on the versions of the puzzle where we know for sure that there is exactly one fake coin and n–1 genuine coins. There are then four possible variations:

1. We know that the one fake coin is definitely lighter than the genuine coins.
2. We know that the one fake coin is definitely heavier than the genuine coins.
3. We do not know whether the fake coin is lighter or heavier than the genuine coins, only that it has a different weight. We need to locate the fake coin, but we don’t need to know at the end whether it is lighter or heavier.
4. We do not initially know whether the fake coin is lighter or heavier, but as well as locating the fake, we need to end up knowing for sure whether it is lighter or heavier.

Variations 1 and 2 are essentially the same; if we can solve Variation 1 by a series of measurements, we can solve Variation 2 by doing the same thing but swapping every mention of “lighter” and “heavier” in our procedure.

Variation 1 is fairly easy to solve.

• If n=1, that single coin must be the fake, so we have found the fake with 0 comparisons.
• If n=2, we compare the two coins, and the lighter coin is the fake.
• If n=3, we compare any two of them; if one of that pair is lighter, it is the fake, but if the two coins we compared have the same weight, then since we know there is exactly one fake, it can only be the one we didn’t place on the balance. So, if we have either 2 or 3 coins, we can always find the fake with 1 comparison.

For larger values of n, we adopt a strategy of repeatedly dividing up the set of coins that must contain the fake into three parts. Two of these parts need to have the same number of coins, so that if we compare them they will either be the same weight, which will tell us that the third part contains the fake, or one of the first two parts will be lighter, so it will contain the fake.

How, exactly, should we divide up the coins? If n is divisible by 3, we can divide it into three equal parts. If there is a remainder of 1 after dividing by 3, we put the extra coin in the third set. If there is a remainder of 2, we put an extra coin in each of the first two sets. So, 9 → (3,3,3), 10 → (3,3,4), 11 → (4,4,3), etc.

Each comparison shrinks the size of the set that must contain the fake. If we started out with n = 3p coins, every comparison would shrink the set by precisely a factor of 3 every time, so that after p comparisons we would have pinned the fake down to a set of size one, locating it exactly. But in general, the number of comparisons that we can guarantee are enough to find the fake will be the lowest value of p such that 3pn. So for 10 coins, which we split into two sets of 3 and one set of 4, we might be lucky and pin the fake down to one of the sets of 3, then settle the question with just one more comparison, but if the fake is in the set of 4, we might need two more comparisons, for a total of 3 comparisons.

Variation 2 can be solved in the same way, except that when two sets have different weights, it is the heavier of the two that must contain the fake.

What about Variation 3, where we have no advance knowledge as to whether the fake coin is heavier or lighter than the genuine coins? If n=1, that single coin must be the fake, but if n=2 it is impossible to tell whether the lighter of the two coins is a genuine coin accompanied by a heavier fake, or a lighter fake accompanying the genuine coin. So it really only makes sense to talk about a strategy for n ≥ 3.

For n=3, it is impossible to be sure of finding the fake in just one measurement. We can only compare two coins, and if they are the same then that pins down the fake to the third coin. But if the coins we compare have different weights, we have no way of knowing which is the fake; this is the same situation as n=2, where we were stuck. The only solution is to perform another comparison. Luckily, we now know that the third coin is genuine, so we can compare it with either of the first two, and that will settle the matter: any coin matching the third coin will be genuine, making the other fake, while any coin disagreeing with the third coin will itself be fake.

We can illustrate this strategy with the following decision tree: Here, we colour a set of coins grey if we know nothing about them except that they might include a fake of either weight. We colour a set yellow if we know they are all genuine. We colour a set light blue if they might include a lighter fake, but not a heavier fake. And we colour a set pink if they might include a heavier fake, but not a lighter fake.

We will call the totality of grey sets F for fake, the totality of yellow sets R for reference [we know they are genuine, so we can use them as reference weights to check other coins], the totality of light blue sets L for light, and the totality of pink sets H for heavy. We will use f, r, l and h for the number of elements in F, R, L and H respectively.

Whenever we perform a measurement comparing two sets A and B (such as the sets of coins marked on our tree by the green and magenta dots), the F, R, L and H sets change as follows:

• If A and B weigh the same, then all of A and all of B are moved into R and removed from F, L and H, because a single fake in either A or B would have tipped the balance one way or the other.
• If A and B have different weights, F becomes the empty set, while L becomes those elements of the lighter of the sets A and B that were previously in L or in F, and H becomes those elements of the heavier of the sets A and B that were previously in H or in F. Everything else goes into R.

Once we have pinned down the set containing the fake to a single coin, we give its number as a “leaf” on the decision tree.

It’s easy to extend the strategy we gave for n=3 to n=4. The only difference is that when the initial pair of coins we compare turn out to weigh the same, that no longer identifies the fake coin immediately, and we need one more comparison to reach the answer. So this time we locate the fake with exactly two comparisons in every case. What about higher values of n? Before trying to answer the question systematically, let’s look at one specific case. The Quanta balance puzzles asked for a solution to n=12, using at most 3 comparisons. After an awful lot of trial-and-error, I finally came up with this decision tree: To keep the tree diagram from being needlessly large, we have omitted the branch where the first comparison finds the green set to be lighter than the magenta set, because everything we do for the branch where the opposite is true can easily be adapted for this outcome, just by swapping the two sets 1-4 and 5-8.

Here is a description of the strategy in words:

• For measurement 1, compare four of the 12 coins with four others.
• Suppose the result of measurement 1 was that the two sets of four coins weighed the same. This means we now have 8 coins that we know are genuine, so we can treat them as reference coins, and another 4 coins that must include the fake.
For measurement 2A, compare two of the 8 reference coins with two of the 4 potential fakes.
• Suppose the result of measurement 2A was that the two potential fakes weighed the same as the reference coins. This rules them out, leaving the other two potential fakes as the only candidates.
For measurement 3AA, compare one of the reference coins with one of the two potential fakes, which will settle which one is fake.
• Suppose the result of measurement 2A was that the two potential fakes weighed either more or less than the reference coins. This means that they remain potential fakes, while the other two are ruled out.
For measurement 3AB, compare one of the reference coins with one of the two potential fakes, which will settle which one is fake.
• Suppose the result of measurement 1 was that the two sets of 4 coins had different weights. This means we now have 4 reference coins (the 4 that were not involved in the measurement), 4 heavier coins and 4 lighter coins.
For measurement 2B, we take 3 of the heavier coins along with 2 of the lighter coins, and compare them with 1 of the heavier coins and all 4 of the reference coins. This leaves 2 of the lighter coins set aside, not taking part in the measurement.
• Suppose the result of measurement 2B was that the 3 heavier coins and 2 lighter coins were lighter than the 1 heavier coin and the 4 reference coins. That leaves us with only 1 coin that could be a heavier fake, and 2 coins that could contain a lighter fake.
For measurement 3BA, we compare those 2 coins that could include a lighter fake. If they are different, the lighter of the two is the fake. If they are the same, the 1 heavier coin is the fake.
• Suppose the result of measurement 2B was that the two sets of coins we compared weighed the same. That turns all 10 of them into reference coins, and means the fake must be one of the 2 lighter coins we set aside from the measurement.
For measurement 3BB, we compare one of those 2 lighter coins with a reference coin, which will settle which one is fake.
• Suppose the result of measurement 2B was that the 3 heavier coins and 2 lighter coins were heavier than the 1 heavier coin and the 4 reference coins. This leaves us with only the 3 heavier coins as possible fakes.
For measurement 3BC, compare 2 of those 3 heavier coins. If they weigh the same, the 3rd one is the fake. If one of them is heavier than the other, the heavier of the two is the fake.

Phew! While most of the individual steps here were fairly easy to come up with, one comparison that sticks out as being a lot less obvious than the others is measurement 2B in the written description, which is the top 2nd-level comparison in the tree diagram. Here, we compare two sets of coins that are each drawn from two different categories: 3 coins from H and 2 from L are compared with 1 from H and 4 from R.

We can extend this strategy to n=13, still with just 3 comparisons. Again, compare four of the coins with four others as the first measurement, and if they have different weights everything works in essentially the same way as for n=12. If they have the same weights, leaving us with 8 reference coins and 5 potential fakes, we now compare 3 of the potential fakes with 3 reference coins. If those 3 potential fakes weigh the same as the reference coins, we have narrowed down the possibilities to the other 2 potential fakes, with the culprit easily located with one more comparison. And if the 3 potential fakes are either heavier or lighter than the reference coins, the comparison tells us definitively whether the fake is heavier or lighter, which takes us back to n=3 for Variation 1 or Variation 2, which is settled by comparing one pair of coins from the 3 candidates.

To see how we can approach the general case, we will start by describing all the situations from which we can reach a result with just one more comparison:

• f = 2, r ≥ 1. We compare 1 potential fake with 1 reference coin, which tells us either that the compared coin is fake, or the other one is.
• l + h = 2 or 3, and one of l or h is at least 2, so (l, h) = (0,2), (0,3), (1,2), (2,0), (2,1), or (3,0). We compare two of the coins from the same set with each other; if they are the same there must be a 3rd coin, which is the fake, but if one is heavier and one lighter, since we already know these two coins can only be fakes of one particular kind, that settles which of them is the fake.
• l = 1, h = 1, r ≥ 1. We no longer have a pair of the same kind to compare with each other, but comparing either of the potential fakes with a reference coin will settle the matter.

The requirement that r ≥ 1 is not very limiting; while r = 0 at the very beginning, that will only persist if we make some very specific choices that aren’t particularly helpful, let alone obligatory. So apart from those circumstances, it will generally be true that if f ≤ 2 or l + h ≤ 3 we can reach a result with at most one more comparison.

Now let’s consider a comparison of the most general kind. When we have coins in the grey set F, this is:

w coins from F are compared with v from F, wv from R, while setting aside fwv from F

After a measurement, we end up with one of the following results:

• The first set was lighter than the second set. We now have w coins in L and v coins in H, all others in R.
• The first set was the same as the second set. We now have fwv coins in F, all others in R.
• The first set was heavier than the second set. We now have w coins in H and v coins in L, all others in R.

When we have coins in the blue and pink sets L and H, the most general comparison is:

a coins from L, b from H are compared with c from L, d from H, a+bcd from R, while setting aside lac from L, hbd from H

After a measurement, we end up with one of the following results:

• The first set was lighter than the second set. We now have a coins in L and d coins in H, all others in R.
• The first set was the same as the second set. We now have lac coins in L and hbd coins in H, all others in R.
• The first set was heavier than the second set. We now have c coins in L and b coins in H, all others in R.

Now, we ought to be able to divide and conquer in a similar, if slightly more complicated, fashion as we did with Variation 1. We can divide the coins in L and H into three groups: all equal in size if the total number is divisible by 3, with one extra in one group if there is a remainder of 1, and one extra in each of two groups if there is a remainder of 2. This will always result in at least two of the groups being equal in size, but we will not commit in advance to any particular pair of groups being equal.

These three groups will specify the possible new sets of elements of L and H after the next comparison we perform. That comparison will be between (A) all the current L elements in the first group and all the H elements in the second group, and (B) all the L elements in the second group and all the H elements in the first group. If one of these sets is smaller than the other, we will need to make up the difference by padding out the smaller set with reference coins from R. If the comparison tells us that A weighs less than B, that shrinks both L and H down to their intersection with group 1; if A weighs more than B, that shrinks them to their intersection with group 2; and if A and B weigh the same, that shrinks them to their intersection with group 3.

The maximum value of l + h that we can reduce to 1 in c comparisons this way will be 3c, but the initial value of l + h will always be even, because l and h will always start out being equal the first time they are non-zero (e.g. they are both 4 in our decision tree for n=12). So 3c–1 will be the actual maximum. The question then is how many coins we should compare in the very first comparison, and how many we should set aside. The number we compare will determine the value shared by l and h if the comparison finds the sets have different weights, while the number we set aside will determine the value of f if the sets turn out to weigh the same.

Suppose we initially compare two sets of w = (3c–1)/2 coins. How many additional coins could we set aside without being at risk of falling behind the c comparisons that we know will suffice to locate the fake coin if it lies in the two sets that are initially compared?

If we look at the ceiling we can place on l + h, after the initial value of 3c–1 this falls to 3c–1; for example, for c=3 we have 3c–1 = 26, which we would then split into sets of 9, 9 and 8. At each subsequent comparison we have a ceiling on l + h of 3ck. So, suppose we have an additional (3c+1)/2 coins at the start, so that after the first comparison we might end up with f = (3c+1)/2. If we then take 3c–1 of these and compare them with reference coins, then if they turn out to be heavier or lighter, we get either l or h equal to 3c–1 and the other zero, so l + h would match the ceiling we get at the same stage by a different route. And if they turn out to weigh the same as the reference coins, what we are left with as the new value of f is:

(3c+1)/2 – 3c–1
= (3c–1+1)/2

So we can continue this strategy for as long as we need to: when f is (3ck+1)/2, the ceiling on l + h one step deeper into the decision tree will be 3ck–1, and we can ensure that we keep pace with it by comparing that many of the coins in F with reference coins.

What we have sketched so far suggests that, with a total of c comparisons, including the first one that we haven’t been counting until now, we ought to be able to solve Variation 3 for:

n ≤ 3c–1–1 + (3c–1+1)/2 = (3c–1)/2

This formula takes the values 1, 4, 13, 40, 121, ... though as we have noted, it only really makes sense to start at n = 3.

To make this concrete, we will need to spell out an algorithm for choosing the comparisons at each point in the decision tree, for any n ≥ 3. Suppose we are at a point in the decision tree with:

l + h = 3 t + u
where u is either 0, 1 or 2

Depending on the value of the remainder u we get after dividing l + h by 3, we will have three possible triplets of values for the size of the three groups into which we divide the l + h coins:

• If u = 0, group sizes are (t, t, t)
• If u = 1, group sizes are (t, t, t+1)
• If u = 2, group sizes are (t+1, t+1, t)

But we don’t want to commit yet to which of these are g1, g2, g3, the size of the first, second and third groups. The first group is made up of a coins from L and d coins from H, and the second group is made up of c coins from L and b coins from H; the comparison we perform will then be between a coins from L together with b coins from H, against c coins from L together with d coins from H, with as many reference coins added to one side as we need to ensure that we are comparing equal numbers of coins.

This leads to the following equations and inequalities:

a + d = g1
b + c = g2
0 ≤ a ≤ min(g1, l)
0 ≤ b ≤ min(g2, h)

d = g1a
c = g2b
a + c = ab + g2l
b + d = ba + g1h
g1hablg2

So, for a given choice of g1 and g2, we have (a, b) constrained to a rectangle in the coordinate plane by the first set of inequalities, and then further restricted to a band running at 45° to the coordinate axes by the second set of inequalities. If we then choose a particular point (a, b), that determines the other parameters of the comparison, (c, d), and the number of reference coins we need to use:

ρ = |a + b – (c + d)| = |2a + 2b – (g1 + g2)|

In considering our choices for g1 and g2 [when there is more than one possibility] we need to check that the rectangle and the 45° band have a non-empty intersection. Then, along with our choice of (a, b) we will try to make ρ as small as possible, to ensure that we will have as many reference coins as we need. If we ignored this last criterion, there is at least one scenario where we could make the wrong choice: for n=3, in the second step we only have one reference coin available, so a strategy that suggests we compare the two other coins (one in L and one in H) with two reference coins, while it would work in principle, would be impossible to implement.

First, we note that the 45° band itself can’t be empty, because the number of integer values it allows for ab is:

lg2 – (g1h) + 1 = l + h – (g1 + g2) + 1 = g3 + 1

The range for ab encompassed by the top left and bottom right corners of the rectangle is:

–min(g2, h) ≤ ab ≤ min(g1, l)

For the intersection to be empty, one of these ranges would have to lie entirely outside the other. If the rectangle’s range is to the left of the 45° band:

min(g1, l) < g1h

This is clearly impossible unless it is l that is the minimum in min(g1, l), so it would require:

l < g1h

which in turns leads to the impossible requirement:

g1 > l + h

Similarly, it turns out to be impossible for the rectangle’s range to lie to the right of the 45° band. So, we are free to choose g1 and g2 without any risk of making the solution set for (a, b) empty.

That leaves us with the problem of picking definite values for g1 and g2 and (a, b) in order to minimise:

ρ = |2a + 2b – (g1 + g2)|

subject to the constraints of the rectangle and the 45° band. The sum 2a + 2b takes constant values on each line that cuts across the plane at –45°, so to minimise ρ, we want the point (a, b) to lie as close as possible to the particular line where 2a + 2b = g1 + g2.

Because g1 and g2 will either be equal or will differ by 1, the only way we can end up using no reference coins at all is if they are equal. So, let’s tentatively assume that we make the choice g1 = g2, and see if we hit any obstacles.

What particular point could we choose for (a, b)? The point P1 = (g1, 0) will lie on the line that gives us ρ = 0, but it might not meet the constraints we need. We need:

g1h ≤ (ab = g1) ≤ lg1

Clearly it will satisfy the first inequality, but it might or might not satisfy the second. If 2 g1 > l, consider the alternative point:

P2 = (floor(l/2), g1 – floor(l/2))

This gives:

(ab = 2 floor(l/2) – g1) ≤ lg1

Does P2 meet the first inequality? To violate it would require:

g1h > 2 floor(l/2) – g1
2 g1 > 2 floor(l/2) + h

If l is even, the RHS here is l + h, and it is impossible for the sum of two equal-sized groups, out of the three into which l + h is divided, to have a larger size. If l is odd, the inequality becomes:

2 g1 > l + h – 1

This is only possible if g1 = g2 = 1 and g3 = 0, with l + h = 2. Since we also require 2 g1 > l, the only way this can arise is with l = h = 1. We have already noted that this might be a case that needs special treatment, so we will set it aside for now and check whether the other constraints are satisfied for all other cases.

If 2 g1l, P1 = (g1, 0) lies at the bottom right-hand corner of the rectangle, because min(g1, l) = g1. So it meets all the constraints.

If 2 g1 > l, we have P2 = (floor(l/2), g1 – floor(l/2)). Both coordinates are clearly non-negative, and a = floor(l/2) is less than or equal to both g1 and l. We also need:

b = g1 – floor(l/2) ≤ min(g1, h)

Now, we can rewrite h to obtain:

h = 2 g1 + g3l > g3
g3g1 – 1

It follows that hg1, so the RHS of our constraint on b is min(g1, h) = g1, and it becomes manifestly true.

We now have a reasonably simple algorithm for deciding what comparison to perform when we are dealing with the sets L and H:

if l = 1 and h = 1 then
Set g1 = 1, g2 = 0, g3 = 1
Set a = 1, b = 0, c = 0, d = 0 and ρ = 1
[We compare the single coin in L with a single reference coin.]
else
Set g1 = g2 = round((l+h)/3)
if 2 g1l then
Set a = g1, b = 0, c = g1, d = 0 and ρ = 0
[We compare g1 coins from L with g1 coins from H.]
else
Set a = floor(l/2), b = g1 – floor(l/2), c = floor(l/2), d = g1 – floor(l/2) and ρ = 0
[We compare floor(l/2) coins from L and g1 – floor(l/2) coins from H with a second set containing the same numbers of coins from L and H.]

In the initial comparison, we can split up the coins in exactly the way we did for Variation 1. But we also need to deal with the general case where we still have the set F rather than L and H. If n ≤ (3c–1)/2 [where c is the smallest integer for which this is true], we need to ensure that after the kth comparison [starting with k=1 for the initial comparison], we do not allow l + h to be greater than 3ck. So we compare this many coins in F with reference coins, or all of F if it contains fewer coins.

Variation 4 can be solved using essentially the same algorithm, but the number of coins it can deal with for a given number of comparisons will be slightly less. The only way the status of the fake coin as lighter or heavier can remain unresolved in Variation 3 is if the set F persists to the end of the process, finally reduced to a size of 1. If we always take 3ck coins from F to compare, for k = 2, ..., c, this adds up to (3c–1–1)/2, which is one less than the number of coins we set aside in the first comparison when n is exactly the upper limit, (3c–1)/2. If n was one less, we would set aside one less coin, and we would never have any coins in F by the end. So for Variation 4, the maximum number of coins we can deal with using c comparisons becomes (3c–1)/2 – 1 = (3c–3)/2.

### CoinBot

You can see how the algorithm for Variation 3 works to locate the coin by selecting the number of coins, the location of the fake coin, and the weight of the fake coin, then hitting the LOCATE FAKE button.

 Coins that might include a fake of EITHER weight Coins that might include a LIGHT fake Coins that might include a HEAVY fake Coins that are known to be GENUINE  Science Notes / Find The Fake Coin / created Saturday, 23 July 2022