Archimedes and the Greedy Goldsmith

Note: this is an original puzzle, composed of two parts. If you don’t want to read the background or solutions, you may skip to the first question, or skip to the second — much harder — question.

You may have heard of Archimedes of Syracuse, the wise Ancient: most famous for leaping out of his bath, shouting “Eureka,” while running naked through the streets.

His discovery had to do with determining if the King’s crown were pure gold. On the naked heels of this success, King Heiro entrusted Archimedes with creating eight crowns of pure gold: one each for the Princes of Sicily.

Each crown was to be identical, so as not to incite envy among the rival princes. So Archimedes commissioned the Royal Goldsmith, Aplistos, for eight equal portions of pure gold, and set about making the crowns.

Pleased with how they looked, he rushed off to the coronation ceremony. However, on the way, he came upon his trusty aide Pistis, who alerted Archimedes to a horrible possibility: one of the crowns may not be of pure gold!

That cretinous cur Aplistos had been rumored to have occasionally added pyrites — ‘Fool’s Gold’ — when customers were distracted. Thankfully Archimedes was there to observe all but one pile of gold dust dispensed by the avaricious Aplistos.

But this meant that one of the crowns, possibly not being of pure gold, may be lighter than the others. This would be scandalous in court!

Of course, Archimedes would be blamed — and possibly executed¹!

Running very low on time², Archimedes needs to find which crown, if any, is the lighter. The only way to do this is to compare the weights among each other with a balance.

Because the balance needs to adjust, each weighing takes time, and he is already late.

How many balance measurements does Archimedes need to do to guarantee he has identified the one false crown out of eight? Indeed, if there is one! Also, knowing that Archimedes risks his life by being late: how do you know this is the smallest number of measurements possible?

(I) Naïve solution

One quickly realizes that measuring each crown against a chosen reference crown, arbitrarily chosen, is not a great solution. This would require seven measurements, in the worst case. Measuring each pair against each other yields a better solution, with four measurements.

But an even better solution generalizes this concept of grouping. Again, taking the most naïve approach, we could split the crowns into two groups:

We can then continue the divide-and-conquer program by observing ever smaller groups, leading to three measurements.

(II) Adaptive Solution

Is this the best we can do? How do we know? Remember that Archimedes’ life is on the line here!

Looking beyond the naïve approach, we could experiment with group sizes. Pairs, the smallest group size, are too few because we end up needing four measurements. Initially dividing in twain (four each) was better than this. What if we grouped into threes, at least for the first six?

This gives us three possibilities:

(i) They’re both equal

(ii) Left is lighter

(iii) Right is lighter

In case (i), then there is the potential that 7 or 8 is the false (lighter) crown. So Archimedes needs to compare these two, then we’d find out which one is lightest.

In cases (ii) and (iii) we are led directly to comparing an arbitrary pair for the respectively light group, which would also tell us immediately which of the three were the false crown.

Hence choosing a group size of three is even better, leading to the required number of measurements to be two.

From the perspective of grouping, this is the best we can do — we have already seen that one measurement is not enough, as we noticed that starting with two large groups requires three measurements.

(III) Non-adaptive Solution

You may have noticed that the preceding solution was adaptive. In other words, we tallied up each possibility and looked at the consequent outcomes of each, recognizing there were a countably small number of options each time. Is there a non-adaptive solution? Is there a measurement scheme Archimedes could adopt that didn’t depend on the results of previous measurements?

Imagine Archimedes’ predicament as an encoding problem, wherein the measurement system encodes each possible combination. Of course, not every encoding we could dream up could actually work in the real world, because balances have certain constraints. But if we think about the output of each balance measurement, we have three options each time. Each weighing could yield three possible configurations. Hence two weighings yields 3×3 = 9 possibilities. This is enough to give an indication of each of the eight crowns, plus the possibility that none were false.

Choosing a specific encoding for the result of each balance:

We can encode each measurement as a 1, 0 (equal weight) or -1 (this is known as a balanced ternary encoding³). Then we can assign a unique combination to each crown. For example:

This certainly gives a unique possibility for each crown (each column is distinct from any other), as long as we have two measurements (rows). At least in theory. But would this work in the ‘real world’?

Importantly, the way a balance works in the physical world means that we have to have an equal number of crowns on each side. So we can only use a scheme like this if it leads to equal numbers on each side of the balance for each measurement.

Luckily, this is what we have! Examining each row in the measurement encoding, we see that there are three of each possible symbol, meaning that the sum total of each row is zero. If we interpret -1 as a crown on the left hand side, and +1 as the right (0 not included) we can read off the non-adaptive measurement scheme:

For example, what if crown #7 were lighter?

(i) First measurement would give +1 (left side down)

(ii) Second measurement would give -1 (left side up)

Reading this off our measurement scheme, [1, -1] is indeed the encoding for crown #7!

So this encoding scheme serves as not only as a non-adaptive solution to the predicament — we don’t have to adjust our scheme according to previous results. But it also serves as a proof for the optimal number of measurements. We simply cannot encode for more possibilities using fewer than two measurements!

(IV) An Even Worse Predicament!

As if the situation weren’t already dire, there is an even worse complication. Aplistos, that rancorous goldsmith, heard of Archimedes’ attempt to unveil the false crown! Having managed to sneak into Archimedes’ laboratory, the goddess Hera granted him the remarkable ability to hide just long enough to sneak his thumb on the scale for (at most) one measurement. This results in one of the measurements possibly being altered either towards or away from equilibrium.

In light of this heinous prospect, what is the least number of measurements Archimedes requires to ensure he can correctly identify the potentially false crown out of eight, given a possible error in one of the measurements?

(V) Yet Another Naïve Solution

This is harder than it might sound! A naïve solution would be to simply repeat each measurement (four measurements). But then what happens when one of these measurements disagrees with its analogue? We would have to do another set of measurements to disambiguate by way of a vote⁴, resulting in six measurements. In the likely case of a false crown, we would be faced with this worst-case scenario. Is this the best we can do?

(VI) Is There a Non-adaptive Solution?

We can take the encoding concept we used above, but extend it by allowing for the possibility that a small error in one of the measurements could be accounted for, by spacing out the distance between each point representing a crown. An error could be then interpreted as diverting a small amount from the ‘true’ value representing one of the false crowns.

In particular, we could take the following measurement scheme:

The first item to note: each crown’s encoding is a distance of four from any other. For example, take crowns 3 and 4:

And 1+0+2+1=4. This means that if Aplistos altered a result, we could not only figure out which measurement were in error, but also how to remedy that error. Put another way: the most efficient way to encode the original problem, i.e. without any measurement error, is to pack each uniquely identified outcome with a distance of at least one from each other. For example:

Here we can represent this geometrically, by taking the first and second measurements as dimensions (x and y) and plot their positions in the plane.

But this is a lot harder to do with four measurements! For a start, the screen you’re reading this on is only two dimensional. But we can illustrate the idea by considering the first three measurements. There is more room with each additional measurement. So we could either pack more distinct points in this volume (three measurements would allow Archimedes to weigh 3³ = 27 , or 26 crowns plus the possibility none were false). Or we could keep the same number of crowns and space each out further, putting distance between them. Four measurements would give 3⁴ = 81 possibilities. Filling this with eight crowns, plus the possibility of none, leaves us with nine available spaces for each. If we could space these out, then a small error would just have the effect of pushing us slightly off the ‘true’ value, but still close enough that we could figure out what the value should have been.

Another observation is that the optimal group size again falls neatly and directly from the encoding scheme (still groups of three). Another advantage of the non-adaptive approach!

This comes from the same constraint: the number of crowns on the left has to be that on the right, so the sum of each row must be zero.

Finally, note that the distance to the origin (no false crowns: [0, 0, 0, 0]) is three for each point. Any single error from the origin has a distance of two from the nearest other points.

(VII) Finding the False Crown

But how does Archimedes actually determine which measurement is wrong? And therefore which of the eight crowns were false?

Recall our picture of the distances between each point representing each crown. The way Archimedes managed to arrange each means they can cope with a small error, up to one position away or towards equilibrium.

We can think of the ‘true’ measurement as a particular code-word, say, c, that we want, and the apostate Aplistos’ thumb-induced error adds an extra bit of weight to a single measurement, giving a total error, e. Then we can take the measurements we observe, s, as a combination of the two: s = c + e

Where e has at most one non-zero element.

Recall the example with crown #3, where there was an error in the first measurement. We can express this as:

But we can only see s. How can we reverse this process to figure out where the potential error was, and thus to infer what c should have been?

Imagine there were some mathematical transformation we could apply to s to get rid of c, leaving us with e. We couldn’t add or subtract something, as that would just look like another error! Perhaps we could multiply something with s ?

For example, it would be great if we could do something like Hs = H(c + e) = Hc + He = He

This would work if H were identically zero, but this isn’t much help! If only we had an H that had these magical properties…

(Homer Simpson some magical animal)

It turns out we do!

We can exploit the fact that our points are in a four-dimensional space. This means that we can multiply the vectors by matrices that have the peculiar property that multiplying and adding together all the elements happen to be zero for every code-word in our code-book, and only for those code-words. In particular, take H:

If we multiply this, and the code-word for crown #3:

If Aplistos managed to get his thumb on the scale for the first measurement, we could then have e = [1, 0, 0, 0], so:

Aha! But this is the first column of H! This means that the position the error occurred was the first. So now we know that if Archimedes observed s = [1, 1, 1, 1]

We know that c = s-e = [1, 1, 1, 1]-[1, 0, 0, 0] = [0, 1, 1, 1], which is c3, our code-word for the third crown!

OK, but what if Aplistos had corrupted the scales in the opposite direction? Obviously this is just as bad. We would then have observed s = [-1, 1, 1, 1] . Again, multiplying by H:

And this doesn’t correspond to any column of H!

However, notice that H is symmetric around zero. If you multiply by -1, you will get another four columns, representing negative additions. Therefore we know that e = [-1, 0, 0, 0] and hence c = s -e = [-1, 1, 1, 1] -[-1, 0, 0, 0] = [0, 1, 1, 1]

Voila!

(VIII) Is This Solution Optimal?

We have seen that four measurements guarantee that we can identify the false crown, accounting for the possibility of one of those measurements being in error. But can we do any better than this?

We know that two measurements fully occupy the space, so there’s no room for error. But how about three? Recall the minimum distance between points, in order to cope, and correct for, a single error, is d=3; it’s not out of the realm of possibility that Archimedes could do this with three measurements.

One item to note is that the distance of each point should be at least d=3 from the origin [0, 0, 0]. This means that we have no room for non-zero elements (we only have three elements in total!) But we could do this:

But we can see here that the distance between a few points is d=2 (e.g. 2 & 3; 4 & 5).

So with three measurements we could detect if there were a false crown, but not which one. Hence the optimal number of weighings required to determine the false crown, with the possibility of an error in one of the measurements, is indeed four.

(IX) Relevance to Your Life and Further Reading

While hopefully you found this puzzle fun, it is admittedly contrived. Do these ideas have any real use besides accidentally wasting an afternoon and hurting your brain?

The answer is yes! This puzzle is built around the concept of forward error correcting codes.

These are codes which can not only detect an error, but also correct for a small number of errors. These are used in most digital storage media (for example, memory on your phone, hard-disks in computers). The two Voyager spacecraft, the only man-made objects to go beyond our Solar System, depend (depended?) on forward-error-correction codes. If we had to ask Voyager 1 “could you repeat that last message?” it would take 42 hours to get the response back!

The classic is the Hamming code. If you’re further interested, you might want to start there.

Of course, if you see any errors in this post, please let me know… so I can correct it!

[1] Never go in against a Sicilian when death is on the line

[2] No, he doesn’t have enough time to run a bath

[3] The famous computer scientist Donald Knuth, described the balanced ternary number system as “perhaps the prettiest number system of all”

[4] This is otherwise known as a repetition code