Monthly Archives: February 2016

Given 12 coins, find one that is lighter or heavier

This is a problem of a well-known type: you’re given some coins (balls, rings), one of them is lighter, heavier, or maybe it can be either lighter or heavier. You need to find that one using no more than some specified number of weighings. In this particular example we have 12 coins, one of them is forged and may be heavier or lighter, we don’t known which. We need to find it in no more than 3 weighings.

In simpler problems, like when you’re given 8 balls and one of them is heavier, and we’re limited to two weighings, we can often succeed using brute-force approach. Try splitting them 4/4, then you quickly figure out that you can’t find one among 4 in one weighing. Well, just try a 3/3 split and then you’re done.

With 12 coins it is not so simple. You could guess that 4/4/4 first split is a good idea, but then you could spend hours trying to figure out the rest. So a smarter approach would be useful. And this is exactly what I’m about to show. But first let’s think about bounds.

Lower bound of the number of weighings

What is the lower bound of the number of weighings for this problem? There are 12 possible answers and each weighing gives us one of the three possible results. This leads to a ternary decision tree that represents our algorithm. To minimize the number of weighings we should minimize the height of the tree by balancing it out. The height of such tree is \lceil \log_3 12 \rceil=3. Makes sense. But only we assume that our algorithm only tells us which coin is forged without actually determining whether it’s lighter or heavier. Such an algorithm is hard to imagine, and if it gives us the complete answer, then there are total of 24 answers. Not that it changes the lower bound, though, as \lceil \log_3 24 \rceil is also 3.

Note that it is only a lower bound. It may or may not be actually reachable, and that’s much harder to prove (but the proof does exist with exact numbers). Obviously if we can find an algorithm that works, then it’s reachable. But if we can’t find one, it doesn’t mean that it doesn’t exist. Unless we’ve actually brute-forcibly tried all of them. It isn’t that hard for small problems, and I’ve actually done it for 12 and 13 coins. Turns out the lower bound is reachable in case of 12 coins, but in case of 13 coins it’s only reachable if we don’t need to know whether the forged coin is lighter or heavier. So even though that \lceil \log_3 26 \rceil = 3, we can’t build an algorithm that finds all 26 answers.

A heuristics for building the right solution

How do we produce an algorithm for a given problem without brute-forcing it? I hereby present a heuristics that gives three hints as to what to do next.

U -> L, H, G; L -> G; H -> G

Possible coin transitions

Let’s start by partitioning coins into four groups. Initially all coins belong to the group U, which is the group of coins we know nothing of. Then there are groups L and H which contain coins that may be lighter (but not heavier) and vice versa. If we weigh some coins from U and they don’t balance out, then the heavier pile goes to H and the lighter one goes to L. The rest of the coins, which did not participate in the weighing, are obviously genuine so they go to the last group, G. When we weigh suspicious coins with some genuine ones and they balance out, then the suspicious coins go to G no matter which group they belonged to.

Our goal is to maximize the information gained by each weighing. And since we have no idea what the result of the weighing will be, we should try to maximize worst-case results, much like in the minimax algorithm.

But how do we measure information gained? Obviously each coin promoted from one group to another is something. But if a coin jumps from U to G directly, it’s even better than a coin going from U to L or H, or from L or H to G. So here is the first hint:

We should pick a weighing that maximizes the minimum of N_{U \rightarrow L} + N_{U \rightarrow H} + N_{L \rightarrow G} + N_{H \rightarrow G} + 2N_{U \rightarrow G} for all possible results of a weighing. In other words, each coin jumping from U to G gives us two points, and all other movements give us one points each.

The second hint is somewhat obvious. Whenever you’re facing a weighing that may only give you two results instead of the three (e. g. it’s impossible for the coins to balance out), you’re probably doing something wrong, unless it’s the last weighing.

The third hint is less obvious: if, at some point, you hit a decision tree branch that allows you to figure out the answer in less weighings than the given limit, you’re probably doing something wrong.

The last two hints are actually the two sides of the same coin, no pun intended: they both tell you that you’re going to create an unbalanced decision tree. In a well-balanced ternary tree most non-leaf nodes should have all three children, and the tree should ideally have the same height everywhere. Of course, that depends on the exact problem: if you’re allowed to do 100 weighings for 12 coins, you probably end up with lots of branches much shorter than that. But for three weighings it’s really desirable to balance everything out.

The last two hints are mostly redundant. If you’re squeezing as much information as possible, you would probably create a well-balanced tree anyway. So they just serve as additional warnings. But sometimes they simplify the math.

Back to the problem

So let’s try to build a good algorithm for 12 coins and 3 weighings. A 6/6 split is a bad idea because of the second hint. That’s how it simplifies the math, so we can instantly skip to an n/n split, where n<6. Since the situation is symmetrical for now, we don’t need to consider lighter/heavier results separately, so that leaves us two possible results of the weighing:

  1. The chosen coins balance out, therefore jumping right to G. The rest still belongs to U. That gives us 4n points (2n coins jumping from U to G).
  2. They don’t balance out. Therefore the lighter group goes to L, the heavier one to H and the rest straight to G because we know that the forged coin is among the weighed piles. That gives us 2n+2(12−2n) = 24−2n points.

The first expression increases with n, the second one decreases. If we find the point where they are equal, it’s obvious that the minimum will be less towards both directions from there: to the left 4n will be less, to the right 24−2n will be less. That gives us the following equation:

4n = 24−2n, 6n = 24, n = 4

Then we have two cases to consider.

Four coin piles balance out

The easiest case is when the coins balance out, so we now have just 4 U-coins. Intuitively, one may think of comparing two of them. If they balance out, we compare one of them with one of the remaining ones. If they balance out again, then the remaining one must be the forged one, but we don’t know whether it’s lighter or heavier. If the third weighing doesn’t balance out, then the third coin is the forged one (and we now know whether it’s lighter or heavier). If the second weighing doesn’t balance out, then we again compare one of them with one of the remaining ones, this time identifying not only which one is forged, but also whether it’s heavier or lighter. But there was still one case when we couldn’t do it. So let’s try to use our heuristics.

It makes no sense to compare good coins with good coins, so the only way we may end up putting good coins on the balance scale is to compare them with suspicious ones. This means that only one pan should contain good coins (if both of them do, we can just remove the minimum number of good coins from both pans). That means that we can have n1 U-coins on the left pan and n2 U-coins and n1-n2 G-coins on the right pan. Here, n2 can be zero (comparing suspicious coins with good ones), but then n1 can’t be 4 because all 4 U-coins can’t possibly balance out with 4 G-coins, and the second hint tells us it’s probably a bad thing. n1+n2 also can’t be 4 because of the same reason. So we have three cases now:

  1. Balancing out: 2(n1+n2) points for coins now promoted to G.
  2. The left side is lighter: n1+n2 points for promoting n1 coins to L and n2 coins to H. 2(4−n1−n2) points for promoting the rest to G.
  3. The left side is heavier: n1+n2 points for promoting n2 coins to L and n1 coins to H. 2(4−n1−n2) points for promoting the rest to G.

Note that even though cases 2 and 3 give equal number of points, the resulting group configuration is different if n1 ≠ n2. Now let n=n1+n2, then we have the following equation:

2n = 2(4-n), 3n = 8, n = 2 2/3

Let’s pick the closest integer value n = 3. Note that n1 and n2 by themselves don’t really matter, so let’s pick n1=3, n2=0. Going back to three cases:

  1. Balancing out: three coins are genuine, which means the remaining one is forged. We even have a spare weighing to determine if it’s lighter or heavier. Here is where 13 coins case breaks (the algorithm up to this point is the same): we can still determine which one of the remaining coins is forged, but with probability 1/2 we won’t know whether it’s lighter or heavier.
  2. Three U-coins are lighter: it means that the forged coin is among them and it’s lighter. Comparing any two of them will give us the answer.
  3. Three U-coins are heavier: the same as case 2, but the forged coin must be heavier.

See how using our heuristics allowed us to build a much simple algorithm than one may come up with intuitively, and how it’s also more powerful?

Four coins do not balance out

This case is much harder because we now have 4 L-coins, 4 H-coins and 4 G-coins which is a mess of possible combinations. Let’s pick n1 L-coins and m1 H-coins for the left pan, and n2 L-coins and m2 H-coins for the right pan, possibly adding some n1+m1−n2−m2 G-coins. Obviously we can’t use all L and H coins or else we can’t possibly balance out everything. The three cases now are:

  1. Balancing out: n1+m1+n2+m2 points for new G-coins.
  2. Pan 1 is lighter: m1+n2 points plus 8−n1−m1−n2−m2 points for not-participating coins. Where did m1+n2 points came from? Well, m1 coins were from H-group and now they are on the lighter side. The forged coin can’t possibly be both heavier and lighter, so it’s obviously then that these m1 coins are all genuine. Ditto with n2.
  3. Pan 1 is heavier: m2+n1+8−n1−m1−n2−m2. The same reasoning.

We now have three expressions and must do our best to balance them out. Let’s put it this way:



Subtracting one from another we get m1+n2=m2+n1. Let k denote this, that turns the first expression into 2k and the second and the third ones into 8-k. By solving 2k=8-k we get 3k = 8, much like in the previous case. And again, we have some freedom, but we can’t pick n1=3, m1=0, n2=3, m2=0, for example, because n1+n2=6 and we only have 4 L-coins. So let’s pick n1=3, m1=2, n2=1, m2=0. We’ll also need to add all 4 genuine coins to the right pan.

  1. Balancing out: we’re now left with 2 H-coins. Finding out which one is forged is a piece of cake.
  2. The left pan is lighter: we’re left with 3 L-coins. The right pan did not contain any H-coins, so it’s obviously that the forged one is among those 3. Again, it’s trivial to solve.
  3. The left pan is heavier: we’re left with 2 H-coins from the left side an 1 L-coin from the right side. Comparing the two H-coins we will instantly know which one of them is heavier and therefore is the forged one, in case they don’t balance out. If they do, then the forged one must be the remaining L-coin.

Problem solved! We didn’t even have to try different variations (but you can, and you’ll get correct algorithms). And we also didn’t have to use the third hint.