1
$\begingroup$

I am reading the paper entitled "Counterfeit Coin Problems" by Bennet Manvel, 1977. The counterfeit coin problem described in and solved by Theorem 3 is

Theorem 3 (adapted slightly). Let $S$ be a set of more than two coins, one of which is counterfeit with a different weight than the others (it is not known whether the counterfeit coin is heavier or lighter than the standard ones). The least number of weighings (using a beam balance) in which the counterfeit coin can be found is the unique $n$ satisfying $(3^{n-1} -3)/2 < |S| < (3^n - 3)/2$.

The proof goes as follows (the lemma and theorem 2 used are listed below):

Cleary we must begin by comparing two equal sets $S_1$ and $S_2$ on the balance, leaving off a set $S_3$.

If the beam does not balance, the counterfeit is in $S_1 \cup S_2$, each coin is labeled "possibly heavy" or "possibly light" and so, by the lemma, $|S_1 \cup S_2| \le 3^{n-1}$. Since we must balance equal sets of coins and have no standard coin, the maximum for $|S_1 \cup S_2|$ is actually $3^{n-1} - 1$.

If, on the other hand, the beam balances, we are left with $S_3$ and some standard coins (in $S_1$ and $S_2$). Thus, by Theorem 2, $|S_3|$ can be as large as $(3^{n-1})/2$.

Combining these results, we find $|S|$ can be $(3^{n-1} - 1) + (3^{n-1})/2 = (3^n - 3)/2$, as desired.


I have two questions both concerning the roles of standard coins.

First, in the case of "the beam does not balance", why do we "have no standard coin"? In my opinion, we have known that the coins in $S_3$ are standard. However, the lemma does not make use of these standard coins. Why not?

Lemma. If in a set $S$ of coins one coin is a different weight than the rest and each coin is labeled "possibly heavy" or "possibly light", the least number of weighings on a beam balance in which the counterfeit coin can be found is the unique $n$ satisfying $3^{n-1} < |S| \le 3^n$.

Second, in the case of "the beam balances", we know that the coins in $S_1$ and $S_2$ are all standard. However, Theorem 2 only uses a single standard coin. Does it mean that multiple standard coins do not help? If so, how to prove it?

Theorem 2. If we are given a set $S$ of coins, plus a standard coin, and one coin in $S$ is a different weight than the rest, then the least number of weighings in which the counterfeit coin can be found is the unique $n$ satisfying $(3^{n-1} - 1)/2 < |S| \le (3^n - 1)/2$.

$\endgroup$
3
$\begingroup$

For the first question, you need to look back at the proof of Theorem 2 and the use to which we put the standard coin in that proof.

There, we wanted to achieve the theoretical maximum $|S_1 \cup S_2| = 3^{n-1}$, but this runs into a problem: $|S_1| = |S_2|$, so $|S_1 \cup S_2|$ is even, but $3^{n-1}$ is odd. The solution was to let $S_1$ be a set of $\frac{3^{n-1}+1}{2}$ coins, let $S_2$ be a set of $\frac{3^{n-1}-1}{2}$ coins, and compare these by putting $S_1$ on one side of the balance while putting $S_2$ and the extra standard coin on the other side. So we actually have $3^n + 1$ coins on the scale - we just know one of them can't possibly be the relevant coin.

In the case of Theorem 3, we have no standard coin at the beginning: before the first weighing. We must have $|S_1 \cup S_2| \le 3^{n-1}$, and we must also have $|S_1 \cup S_2|$ be even, so we actually must have $|S_1 \cup S_2| \le 3^{n-1} - 1$. If we put $3^{n-1}+1$ coins on the scale, if it does not balance we're in the case of Theorem 1 with more than $3^{n-1}$ coins, and then we need $n$ more weighings. So we can only put $3^{n-1}-1$ coins on the scale.


For the second question, the reason multiple standard coins do not help is simply that the bound in the Lemma applies no matter how large a supply of standard coins we get. We found a use for a single standard coin: it helps us achieve the value $|S_1| + |S_2| = 3^{n-1}$, which we know is best possible. There is no more room for further standard coins to help us.

$\endgroup$
  • $\begingroup$ Thanks. For the first question, I am confused about the logic flow behind Theorem 3 and Theorem 2. After the first weighing of Theorem 3, if the beam does not balance, we have known that "the counterfeit is in $S_1 \cup S_2$, each coin is labeled "possibly heavy" or "possibly light"" and that there are plenty of standard coins (in $S_3$). Then we solve this variant of the counterfeit coin problem, for example, by utilizing the Lemma (ignoring the standard coins). Why should we care about the situation before the first weighing? $\endgroup$ – hengxin Oct 7 '17 at 6:13
  • $\begingroup$ In an answer, @Ross Millikan argues that the reason that we have no standard coin is that we are not given that $S_3$ contains any coins. In other words, it may be the case that $S_3$ is empty. What do you think of it? $\endgroup$ – hengxin Oct 7 '17 at 6:16
  • $\begingroup$ I've clarified the logic about the first question and where we need a standard coin. We don't care if $S_3$ is empty because if it were, and $S_1$ vs. $S_2$ did not balance, after the first weighing we'd be in a Theorem 1 situation, where we don't need standard coins (and they don't help us). $\endgroup$ – Misha Lavrov Oct 7 '17 at 16:54
  • $\begingroup$ I think I have got the idea: The key point of solving this puzzle is to decide what $|S_1|, |S_2|, |S_3|$ are. With a standard coin, we can achieve $|S_1 \cup S_2| = 3^{n-1}$, as in Theorem 2. Otherwise, we only have $|S_1 \cup S_2| = 3^{n-1} - 1$, as in Theorem 1. Is this understanding correct? Great thanks. (Now, I still have some difficulty in showing that " (A single or multiple) standard coins do not help in Theorem 1 and the Lemma. I will think about it and maybe open another post.) $\endgroup$ – hengxin Oct 8 '17 at 3:48
2
$\begingroup$

For your first question, you are not given that $S_3$ contains any coins. You are correct that if there are any coins in $S_3$ they are standard. Yes, in theorem 2 you only need one standard coin and more do not help. You can see why if you follow the proof of theorem 2 and see where the standard coin is used. In particular, the maximum number of coins that can be solved with three weighings is $12$ if you do not have a standard coin, but $13$ if you have a standard coin in addition. Wikipedia has a detailed solution for each.

$\endgroup$
  • $\begingroup$ For the first question: an algorithm is free to let $S_3$ be non-empty. In this situation, we know that the coins in $S_3$ are standard if the beam does not balance. Is it possible that the Lemma can be improved with some standard coins? Or, standard coins do not help in the Lemma? By the way, what do you think of the arguments given by @Misha Lavrov for the first question? $\endgroup$ – hengxin Oct 7 '17 at 6:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.