Need Thorough Explanation of Coin Weighing Puzzle Solution

Question

One of the coolest things I've seen on Puzzling is this puzzle, and especially the solution in 7 static weighings posted by Julian Rosen.

I have revisited that solution many times over the years, always amazed at it, but never fully understanding it. I have dug into the two sources cited by Julian Rosen, but still I do not understand how the set is chosen, why it works, how to fully apply it to find which coins weigh 10 and which coins weigh 20, and even how to extrapolate the strategy for numbers other than 12.

My challenge to the community is to explain the solution posted by Julian in a way that makes it easy to understand. Choose simple wording over complex wording where possible. Use pictures/diagrams if they would be helpful.

For example, the cited literature is very "mathy", making it a bit cryptic for many, I think (myself included). Avoid that style if possible, as much as possible.

To encourage thorough, high-quality, reference-style answers only, after 2 weeks, the best answer that accomplishes the above objectives receives a 500 bounty on top of the 25 for the check mark.

In the case that there is more than one excellent answer that each add new, useful information or relevant insight, the top answer gets 500 and the 2nd answer gets 250.

Answer 1

Part 1

Imagine instead of a simple scale, we have a scale with two compartments. This new "advanced" scale tells us the weight of the left compartment minus the weight of the right compartment.

With one coin, we can simply put it in the left compartment and get its weight. Notice that we didn't have to use the right compartment.

Suppose we have a weighing strategy that works for $n$ coins in $w$ weighings. Then, we will construct a new weighing strategy that works for $2n + w$ coins in $2w$ weighings. If the original weighing strategy had a weighing that didn't use the right compartment, so will the new strategy.

There will be three (disjoint) groups of coins, each of which we will handle a bit differently. The first group will have $n$ coins. We will call these red. The second group will also have $n$ coins. We will call these blue. The third group will have $w$ coins. We will call these yellow.

To construct a weighing strategy, we can separately consider its restriction to the red coins, blue coins, and yellow coins. (In other words, we can separately ask: Which red coins does each weighing include? Which blue coins? Which yellow coins?)

For our first $w$ weighings, we will duplicate the original weighing strategy on the red coins. On the blue coins we will also duplicate the original weighing strategy, but reverse the left and right compartments. Each of these weighings will include exactly one of the yellow coins (a different one for each weighing). Put the yellow coins in the left compartment.

For the other $w$ weighings, we will again duplicate the original weighing strategy on the red coins, and also duplicate the original weighing strategy on the blue coins, but without reversing them. This time, we will not include any yellow coins. If a weighing from the original strategy didn't use the right compartment, the weighing constructed from it here also won't use the right compartment.

First, we calculate the weights of the yellow coins. To get a yellow coin's weight, take the sum of the weights from the weighing that includes that coin, plus the corresponding weighing from the second group.

The contribution to this sum from the blue coins will be zero because if a coin appears on the left in one weighing, it appears on the right in the other weighing and vice versa. The contribution to this sum from the red coins will be a multiple of 20 because any coin that appears also appears in the other weighing. Thus, the total sum will be a multiple of 20 exactly when the yellow coin weighs 20, and if the total sum is not a multiple of 20, then it is because the yellow coin weighs 10.

Now that we know that weights of the yellow coins, we can subtract off their weights from the first group of weighings to get what those weights would have been if we hadn't included the yellow coins.

To get the weights of the red coins, we then do the same thing again. Take a weighing from the first group (minus the result of the yellow coin) and add it to the corresponding weighing from the second group. The contributions from the blue coins cancel out, and we get double the result of applying a weighing from the original strategy to the red coins. Doing this for all the weighings (and halving) just gives us the result of applying the original strategy to the red coins which tells us the weights of the red coins.

Similarly, to get the weights of the blue coins, we can take a weighing from the first group (minus the result of the yellow coin) and subtract from it the corresponding weighing from the second group. This time, the contributions from the red coins will cancel out and we get double the result of applying a weighing from the original strategy to the blue coins. Again, doing this for all the weighings reproduces the entire original weighing strategy for the blue coins, so we can figure them out as well.

Starting from our base case, this gives us $2^{k-1}(k+2)$ coins with $2^k$ weighings, at least one of which doesn't use the right compartment.

Example

The solution for seven weighings to the original problem will involve applying this inductive step twice to get a way to solve eight coins with four weighings of the advanced scale. The first inductive step is less instructive, so I'll focus on the second inductive step, but we need the result of the first inductive step as a base case. This involves two weighings and three coins. The first weighing puts the first and third coins in the left compartment against the second coin in the right compartment and the second weighing puts the first two coins in the left compartment against nothing in the right compartment. (In the context of the first inductive step, the first coin is red, the second coin is blue, and the third coin is yellow.)

Now, to apply the second inductive step, let $r_1$, $r_2$, and $r_3$ be the weights of the three red coins, let $b_1$, $b_2$, and $b_3$ be the weights of the blue coins, and let $y_1$ and $y_2$ be the weights of the yellow coins. Our weighings will be:

$(r_1 + r_3 + b_2 + y_1) - (r_2 + b_1 + b_3)$

$(r_1 + r_2 + y_2) - (b_1 + b_2)$

$(r_1 + r_3 + b_1 + b_3) - (r_2 + b_2)$

$(r_1 + r_2 + b_1 + b_2) - 0$

Suppose the results of the weighings are as follows:

$(r_1 + r_3 + b_2 + y_1) - (r_2 + b_1 + b_3) = 0$

$(r_1 + r_2 + y_2) - (b_1 + b_2) = 10$

$(r_1 + r_3 + b_1 + b_3) - (r_2 + b_2) = 10$

$(r_1 + r_2 + b_1 + b_2) - 0 = 70$

To solve using the general method, first we tackle the yellow coins. Adding the first and third equations gives $2(r_1+r_3-r_2) + y_1 = 10$. Because $2(r_1+r_3-r_2)$ is a multiple of $20$, we conclude $y_1 = 10$. Then we add the second and fourth equations to get $2(r_1+r_2)+y_2 = 80$. Again, $2(r_1+r_2)$ is a multiple of $20$, so $y_2 = 20$.

Now $y_1$ and $y_2$ can be eliminated from the equations by substituting in their known values.

$(r_1 + r_3 + b_2) - (r_2 + b_1 + b_3) = -10$

$(r_1 + r_2) - (b_1 + b_2) = -10$

$(r_1 + r_3 + b_1 + b_3) - (r_2 + b_2) = 10$

$(r_1 + r_2 + b_1 + b_2) - 0 = 70$

Again, add the first and third equation to get $2(r_1+r_3-r_2) = 0$ and add the second and fourth to get $2(r_1 + r_2) = 60$. If we divide out the twos, we have $r_1+r_3-r_2 = 0$ and $r_1 + r_2 = 30$ which is exactly what we would have gotten by directly applying the three coin case to the three red coins.

If we want to solve this, we can rename the coins to recover their colors from the first inductions step: $r' = r_1$, $b' = r_2$ and $y' = r_3$. To solve for $y'$, we take the sum of the two equations and get $2r' + y' = 30$. Because $2r'$ is a multiple of 20, we have $y' = 10$. We can then eliminate $y'$ from the system, and things become trivial as it just a system of two equations with two unknowns.

To solve the blue coins from the eight coin case, we take the difference of the first and third equations to get $2(b_1+b_3-b_2) = 20$ and the difference of the second and fourth equations to get $2(b_1+b_2) = 80$. Again, this is equivalent to the three coin case applied to the blue coins which can be similarly solved.

Part 2

We don't actually have an advanced scale with two compartments, so we have to modify our strategy.

We want to achieve $2^{k-1}k$ coins with $2^k - 1$ weighings. We can start with the same base case: one weighing can determine one coin.

Now suppose we have a strategy "A" with $2^k - 1$ weighings that weighs $w = 2^{k-1}k$ coins. From part one, we also have a strategy "B" using the advanced machine with $2^k$ weighings that weighs $u = 2^{k-1}(k+2)$ coins.

Our new strategy will determine the weights of $w$ red coins and $u$ blue coins.

We will again construct two groups of weighings. Restricted to the red coins, each group will simply reproduce the weighings of strategy "A". Restricted to the blue coins, the first group will include coins when the left compartment of strategy "B" would include them and the second group will include coins when the right compartment of strategy "B" would include them. This doesn't quite work because strategy "B" has one more weighing. So, in the first group, we have one extra weighing that doesn't include any red coins. But, remember that strategy "B" includes at least one weighing that uses no coins in the right compartment, so we can line this up so that our extra weighing in the second group doesn't include any coins at all, and we can skip it (although it is still maybe useful to imagine we are doing it).

To recover the weights of the blue coins, we can take a weighing from the first group, and subtract the weight of the corresponding weighing from the second group. The contributions from the red coins will cancel out, and we will get exactly the result of applying an advanced weighing of strategy "B" to the blue coins. If we do this for all the pairs of corresponding weighings, we can get the full result of applying strategy "B" to the blue coins from which we can recover the weights of the blue coins.

Then, we can simply subtract out the known weights of the blue coins from the weighings and we have the results of applying strategy "A" to the red coins. (Actually, we have it twice, but we only need it once.) From this, we can recover the weights of the red coins.

This new strategy gives us $2^{k+1}-1$ weighings and $w + u = 2^{k-1}[(k+2)+k)] = 2^{k-1}(2k+2) = 2^k(k+1)$ coins, so we can continue.

Example

Again, let's focus on the second inductive step which solves 12 coins with seven weighings. The result of the first inductive step is our base case. This involves four coins and three weighings. The weights are 1) coins one, two, and four; 2) coins two and three; and 3) coins one and three. (In the context of the first inductive step, the first coin is red and the other three are blue.)

Then for the second step, let $x_1$ through $x_4$ be the weights of the red coins. For clarity, we will let $r_1$, $r_2$, $r_3$, $b_1$, $b_2$, $b_3$, $y_1$, and $y_2$ be the weights of the blue coins (so named to correspond to the names of the corresponding coins in the previous example). Our weighings are then:

$x_1 + x_2 + x_4 + r_1 + r_3 + b_2 + y_1$

$x_2 + x_3 + r_1 + r_2 + y_2$

$x_1 + x_3 + r_1 + r_3 + b_1 + b_3$

$r_1 + r_2 + b_1 + b_2$

$x_1 + x_2 + x_4 + r_2 + b_1 + b_3$

$x_2 + x_3 + b_1 + b_2$

$x_1 + x_3 + r_2 + b_2$

Suppose we have the following results for our weighings:

$x_1 + x_2 + x_4 + r_1 + r_3 + b_2 + y_1 = 90$

$x_2 + x_3 + r_1 + r_2 + y_2 = 80$

$x_1 + x_3 + r_1 + r_3 + b_1 + b_3 = 80$

$r_1 + r_2 + b_1 + b_2 = 70$

$x_1 + x_2 + x_4 + r_2 + b_1 + b_3 = 90$

$x_2 + x_3 + b_1 + b_2 = 70$

$x_1 + x_3 + r_2 + b_2 = 70$

To solve the blue coins ($r_i$, $b_i$, and $y_i$), we take the difference of the first and fourth equations to get $(r_1 + r_3 + b_2 + y_1) - (r_2 + b_1 + b_3) = 0$, the difference of the second and fifth equations to get $(r_1 + r_2 + y_2) - (b_1 + b_2) = 10$, the difference of the third and sixth equations to get $(r_1 + r_3 + b_1 + b_3) - (r_2 + b_2) = 10$, and then simply take the fourth equation on its own. These are exactly the four equations from the previous example, and they can be solved as outlined there.

To solve the red coins ($x_i$), we can substitute the known values of the blue coins into the first three equations. This gives the following system of equations:

$x_1 + x_2 + x_4 = 40$

$x_2 + x_3 = 30$

$x_1 + x_3 = 30$

This is exactly what we would have gotten by applying the base case directly to the red coins. If we wanted to solve it, we could rename our variables to reflect the colors in the previous induction step: $x' = x_1$, $r''=x_2$, $b''=x_3$, $y''=x_4$. We can solve for $r''$, $b''$, and $y''$ by taking the difference of the first and third equations to get $(r'' + y'') - (b'') = 10$ which together with the second equation $r'' + b'' = 30$ give a case of using the advanced scale to solve three coins as outlined in the first example. Once this is solved, the known values can be substituted into the first equation to get the value of $x'$.

Answer 2

I’ve only skimmed the linked papers. I will say that in terms of understanding why 7 is the minimum number of weighings for 12 coins, or how to construct a sufficient set of weighings, I’m not sure you’ll find a much simpler explanation. It looks like it involves a fair bit of math and if it could have been explained more simply, it probably would have been. I don’t think the authors were intentionally obscure. But I’ll try to read it later and see if I can understand and more simply explain the linear algebra bits that are involved in constructing the weighings.

I will take a stab at explaining the most trivial part of your question, which is how it works / how to apply a known sufficient set of weighings to determine the weights of the coins. I apologize in advance if I’m explaining something you already understand. Also I realized halfway through writing this that I am calling the coins “real” and “fake” which is terminology that didn’t actually appear in the original puzzle, so for the purposes of this explanation assume that real coins weigh 20 grams, and fake coins weigh 10 grams.

So for starters let’s think about a single weighing. Say we have a bunch of coins, and we’re not sure which are real and which are fake. What could happen if we weigh three of the coins together?

• The total weight could be 30, indicating that all three coins are fake.
• The total weight could be 40, indicating two of the coins are fake and one is real.
• The total weight could be 50, indicating one of the coins is fake and two are real.
• The total weight could be 60, indicating all three coins are real.

Note that we haven’t necessarily learned which coins are real or fake, but in every case we have learned how many real coins were in the group we weighed.

Determining if a set of weighings is sufficient

Let’s say you have $N$ coins, and we have a sequence of weighings (e.g. “first I’ll weigh coins 1 and 2, then I’ll weigh coins 1, 3, and 4, …”). For each weighing, we’ll keep track of how many real coins were in the group we weighed - again, we won’t necessarily know which coin(s) were real, but we will know how many real coins there were, if any. Let’s call the number of real coins $R$ for a single weighing. After completing your series of weighings on the set of coins, you will have a set of totals $ R_1, R_2, R_3, ...$, etc. that resulted from that process.

Now consider if you did that same exact sequence of weighings on a different permutation of $N$ coins, what would the output be? For example, imagine all $N$ coins are real. What would $R_1, R_2, R_3, …$ turn out to be with your sequence of weighings if all the coins were real? Now imagine all $N$ coins are fake - what would the output turn out to be? (In this case, $R_1, R_2, R_3, …$ would obviously just be (0, 0, 0…) no matter what your sequence of weighings was, since none of the coins are real.)

Now consider ALL the different possible permutations of $N$ coins. For each permutation, if you apply your sequence of weighings, you’ll get some corresponding sequence of totals as output. The proof says that if each of those total sequences is unique, then the set of weighings you chose was sufficient to identify all the coins. This is pretty straightforward. If you have a one-to-one mapping from coins to outputs, then given any particular output, you’ll know which coins you have.

An Example

To keep it simple, instead of 12 coins let’s pretend we just have 4 coins. Obviously we could determine if each is real or fake with four weighings (just weigh each coin individually). But the proof tells us that we can actually accomplish the task with just 3 weighings.

As a first stab, let’s say our three weighings are “coins 1 and 2”, “coins 3 and 4”, and “coins 1 and 3.” Is this sufficient?

Well what happens if coins 2 and 3 are real, and 1 and 4 are fake? Then on each of our three weighings, we’ll have one real coin, so our output for the series of weighings is (1, 1, 1).

Now what happens if, instead, coins 2 and 3 are fake and 1 and 4 are real. Then on each of our three weighings, we’ll once again have one real coin, so the output is also (1, 1, 1).

Since we got identical output for two different possible permutations of coins, this particular sequence of three weighings we chose is NOT sufficient to identify each of the coins as real or fake.

If we modify our sequence of three weighings to be “coins 1 and 2”, “coins 2 and 3”, and “coins 1, 3, and 4” then we actually do have a sufficient set of weighings. This is because for each of the 16 different possible permutations of the four coins, we would get a unique output sequence. See this image, in which gold coins are real and gray coins are fake.

So for example, if we did these three weighings on a set of four coins and found that there was 1 real coin in each of the three weighings, then we know the real coins are coins 2 and 4. This is the only permutation of coins that would produce the output (1, 1, 1) given this particular set of weighings.

In the absence of a complete table like the one in the linked picture, we can of course use logic to determine the weight of each coin. In this example, we weighed coins 1 and 2 and got a total of 30 grams, so we know one is real and one is fake. Then we weighed coins 2 and 3, and got 30 grams, so we know one is real and one is fake. Finally we weighed coins 1, 3, and 4 and got 40 grams, so we know one is real and two are fake.

Assume coin 1 is real. Then by the first weighing, coin 2 is fake, and by the third weighing, coins 3 and 4 are fake. But this contradicts the result of our second weighing. So coin 1 is fake, and therefore coin 2 is real, coin 3 is fake, and coin 4 is real.

Anyway... I know this doesn't satisfyingly explain how to determine the minimum number of weighings, or how to construct a sufficient set of weighings, but perhaps it helps illustrate how to apply a set of weighings to determine the weight of each coin.