NOTE & BLOG

Problem Statement

The weighing coin problem can be summarized into the following three variations:

1. Given $N$ coins, one of which is heavier (or lighter) than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the heavier (or lighter) coin?
2. Given $N$ coins, one of which has a different weight than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the coin with the different weight and determining whether it is heavier or lighter?
3. Given $N$ coins, one of which has a different weight than the others. Using a balance scale, what is the minimum number of weighings needed to guarantee finding the coin with the different weight without determining whether it is heavier or lighter?

For these three problems, the answers are different. The answer to the first problem is $⌈\log_{3}N⌉$ (where $⌈ x ⌉$ denotes rounding $x$ up to the nearest integer). The answer to the second problem is $⌈\log_{3}(2N+3)⌉$, and the answer to the third problem is $⌈\log_{3}(2N+1)⌉$.

In other words, using the balance scale $k$ times, we can distinguish between $3^k$, $\frac{3^k-3}{2}$, and $\frac{3^k-1}{2}$ coins respectively.

The first problem is relatively simple. Since we know whether the problem coin is heavier or lighter, by putting approximately $\frac{1}{3}$ (rounding up or down) of the coins on each side of the balance scale in each weighing, we can reduce the range of the problem coin to one-third of its previous range. We won't go into further detail here. We mainly discuss the other two problems.

Strict Proof

Here we strictly prove: By using the balance scale $k$ times, we can distinguish among at most $\frac{3^k-3}{2}$ coins and determine whether the problem coin is heavier or lighter.

Let $L_i$ be the set of possibly lighter coins after the $i$th weighing, and $H_i$ be the set of possibly heavier coins.

If we know the problem coin and its weight after $k$ weighings, then:

$$\text{card}(L_k) + \text{card}(H_k) \leq 1$$

where $\text{card}(X)$ denotes the number of elements in set $X$.

Considering the $k$th weighing, there are only three possible outcomes: left side heavier, right side heavier, or balanced. So, before the $k$th weighing, the number of possibly problem coins can be at most $3$, which means:

$$\text{card}(L_{k-1}) + \text{card}(H_{k-1}) \leq 3$$

This conclusion can be recursively generalized:

$$\text{card}(L_{k-i}) + \text{card}(H_{k-i}) \leq 3^{i}$$

where $1\leq i\leq k-1$.

Therefore, after the first weighing, we have:

$$\text{card}(L_{1}) + \text{card}(H_{1}) \leq 3^{k-1}$$

After the first weighing, suppose we put $a$ coins on each side of the balance scale, and $b$ coins are not on the scale, making a total of $2a+b$ coins.

• If the scale is unbalanced, then either the heavier side or the lighter side contains the problem coin, so $a+a\leq 3^{k-1}$.
• If the scale is balanced, among the remaining $b$ coins, there is a lighter or heavier coin, so $b+b\leq 3^{k-1}$.

Thus, we have:

$$a \leq \frac{3^{k-1}}{2} \\ b \leq \frac{3^{k-1}}{2}$$

Considering $a$ and $b$ are both integers, we have:

$$a \leq \frac{3^{k-1}-1}{2} \\ b \leq \frac{3^{k-1}-1}{2}$$

Therefore:

$$N(k) = 2a+b \leq \frac{3^k-3}{2}$$

$Q.E.D.$

Furthermore, we consider the third question: if we don't need to determine whether the problem coin is heavier or lighter.

In this case, $L_k$ and $H_k$ can each only contain one coin.

In this situation, it's still true that after $k$ weighings, if we haven't placed the problem coin on the balance scale (otherwise we would have already known if it's heavier or lighter), we can still conclude whether each coin is problematic. Therefore, the number of coins put on the scale cannot exceed the upper limit of the second question. So, the answer to the third question is obviously $\frac{3^k-1}{2}$.

Solution Construction

We have proven the lower bound of this type of problem, and the other difficulty lies in constructing the solution.

Here is a general method to solve the problem. The process is consistent, but if you need a more practical construction method, you can refer to the end of this post.

Let's take the second question as an example. We use a method called "ternary numbering" to construct the solution.

Taking $12$ coins as an example again: We know from the proof that we only need to weigh $3$ times to find the problem coin. Therefore, our numbering will be $3$ digits. According to the following method:

• The first coin is numbered as $001$;
• The second coin's number is generated by moving each digit of the first coin's number $1$ place forward, i.e., $0\rightarrow1$, $1\rightarrow2$, $2\rightarrow0$. So the number of the second coin is $112$;
• Similarly, the third coin is $220$.

The new numbers of these three coins form a "rotation". They meet the following characteristic: In the new numbers, when we encounter the first different digit from the left, it, and the preceding digit, together, form $01$, $12$, or $20$. We call them "normal" numbers.

For the fourth coin, according to the new number of the first coin, we find the next ternary number. It needs to satisfy: in the new number from left to right, the first non-0 digit is 1. So, the fourth coin's number is $010$. Similarly, we continue this "rotation". The fifth coin's number is $121$, and the sixth coin's number is $202 \dots$

As an additional feature, the conversion between ternary and decimal is as follows:

When the original number is $3a-2$, the new number (normal order) in ternary is: $a+\frac{3^{⌈\log_{3}{2a}⌉}-1}{2}$;

The new number (in reverse order) and the cases when the original number is $3a-1$, $3a$, etc., follow the same pattern.

Here are the normal order and reverse order of the new numbers:

Ternary to decimal conversion:

When the original number is $3a-2$, the new number (normal order) in ternary is: $a+\frac{3^{⌈\log_{3}{2a}⌉}-1}{2}$;

The new number (reverse order) and the cases when the original number is $3a-1$, $3a$, etc., follow the same pattern.

The strategy for weighing is straightforward:

• In the $i$th weighing, we put the coins with the $i$th digit of their new number being $0$ or $2$ on both sides of the balance scale. If the result is left heavy, we record $0$; if it's right heavy, we record $2$; if it's balanced, we record $1$.
• Finally, we record the results of the three weighings, which gives us the number of the problem coin. If it is in normal order, then the problem coin is heavier than normal. If it is in reverse order, then the problem coin is lighter than normal.

This method is easily verifiable. We will give the solutions to the three sub-problems mentioned earlier.

If the weight of the problem coin is not to be determined

We just need to number the extra last coin with $k$ digits of $1$. For example, for $13$ coins, the number of the last coin is $111$ and we can make $3$ weighings.

If the amount is less than $\frac{3^k-3}{2}$

1. If the number of coins is a multiple of $3$, we number them as described above. The method of operation with the balance scale remains the same.
2. If the number of coins is one or two more than a multiple of $3$, we add $1$ to the original number of the last coin.

• For example, if there are $10$ coins, we leave out number $10$ and number the last coin as $11$.
• For example, if there are $11$ coins, we leave out number $11$ and number the last coin as $12$;

It is easy to prove that after the first operation with the balance scale, the number of coins with the first digit of the new number being $0$ or $2$ is the same; and since at least $\frac{1}{3}$ of the normal weight coins can be found after the first operation, if the operation encounters a situation where the number of coins with the $i$th digit being $0$ or $2$ is not the same, we just need to add the normal weight coins to make them the same.

More Intuitive Construction

We have given the complete solution to the coin weighing problem, but in practical operations, it is very cumbersome to assign ternary numbers to coins without the aid of a computer. Is there a more intuitive method?

Yes, there is. We can dynamically construct the solution. Recalling our previous proof, we have the following conclusion:

$$\text{card}(L_{k-i}) + \text{card}(H_{k-i}) \leq 3^{i}$$

where $1\leq i\leq k-1$

The core of the problem is: After each weighing, we need to reduce the solution space to one-third of its original size.

The method is: Take out $\frac{2}{3}$ (rounding up) of the coins contained in $L_i$ and $H_i$, place them on both sides of the balance scale, and add normal weight coins to make the number of coins on both sides of the scale the same. This ensures that no matter which side of the balance scale is heavier or lighter, the solution space can be reduced to one-third of its original size.

To illustrate this method, let's take the example of $12$ coins again:

• First step:
  • Divide the coins into two groups: $1\ 2\ 3\ 4$ and $5\ 6\ 7\ 8$.
    • If the balance is even, then the problem coin is among $9\ 10\ 11\ 12$, go to step $(1a)$.
    • If the balance is uneven, then the problem coin is among $1\ 2\ 3\ 4$ or $5\ 6\ 7\ 8$, go to step $(1b)$.
• Step $(1a)$:
  • Put $9\ 10$ on the left side of the balance scale, and $1\ 11$ on the right side.
    • If the balance is even, then the problem coin is $12$, done.
    • If the balance is uneven, then the problem coin is among $9\ 10\ 11$.
• Step $(1b)$:
  • Divide the coins into two groups: $1\ 2\ 5$ and $3\ 4\ 6$.
    • If the balance is even, then the problem coin is $7$ or $8$, go to step $(2ba)$.
    • If the balance is uneven, then the problem coin is among $1\ 2$ or $5\ 6$, go to steps $(2bb)$ or $(2bc)$.
• Step $(2aa)$:
  • Put $12$ on the left side of the balance scale, and $1$ on the right side.
    • If the balance is even, then the problem coin is $11$, done.
    • If the balance is uneven, then the problem coin is $9$ or $10$.
• Step $(2ab)$:
  • Put $9$ on the left side of the balance scale, and $10$ on the right side.
    • If the balance is even, then the problem coin is $11$, done.
    • If the balance is uneven, then the problem coin is among $9\ 10$.
• Step $(2ba)$:
  • Put $7$ on the left side of the balance scale, and $8$ on the right side.
    • If the balance is even, then the problem coin is $7$ or $8$, done.
    • If the balance is uneven, then the problem coin is among $7$ or $8$.
• Step $(2bb)$:
  • Put $1$ on the left side of the balance scale, and $2$ on the right side.
    • If the balance is even, then the problem coin is $1$ or $2$, done.
    • If the balance is uneven, then the problem coin is among $1$ or $2$.
• Step $(2bc)$:
  • Put $3$ on the left side of the balance scale, and $4$ on the right side.
    • If the balance is even, then the problem coin is $3$ or $4$, done.
    • If the balance is uneven, then the problem coin is among $3$ or $4$.

This gives us a more intuitive dynamic solution.