We are given $(3^n-1)/2$ coins, and among those coins there is just one counterfeit coin. All the other coins weigh the same, but the counterfeit coin weighs slightly heavier or lighter (we don't know which is the case) than a normal coin.
Using a balance scale only, is it possible to identify the counterfeit coin, weighing not more than $n$ times?
My attempt : Using $-1, 0, +1$ instead of $0, 1, 2$, we may write each integer from $-(3^n-1)/2$ to $(3^n-1)/2$ in base 3, with digits among $-1, 0, +1$, in a unique manner. Label the coins from $1$ to $(3^n-1)/2$, and for each coin, labelled $k$, say, we designate one number in $\left\{-k,+k\right\}$ as being 'heavy' and the other one as being 'light'.
My claim is that it is possible to do this so that the resulting designation satisfies the following property :
For each $0\leq i\leq n-1$, the number of heavy numbers whose $3^i$-digit is -1 equals the number of heavy numbers whose $3^i$-digit is +1.
If this is the case, than the following weighing strategy works :
On $i$th weighing, put all the coins whose 'heavy' representation has $-1$ on its $3^i$-digit on the left. Put all the coins whose 'heavy' representation has $+1$ on its $3^i$-digit on the right.
Assuming the counterfeit coin is heavy, our $i$th weighing shows us the $3^i$-digit of the coin. After $n$ weighings, we may deduce which coin is counterfeit.
If the counterfeit coin is light, a similar reasoning also works, and it is clear from our construction the final answer does not depend on whether the counterfeit coin is heavier or lighter than a normal coin.
I believe that this strategy makes sense, but I was not capable proving that such a designation is possible (see the quote box). Am I on the right track? Is such a dsignation possible? Are there any more beautiful solutions to this innocent-looking puzzle?
Answer
Note that we are only asked to find the counterfeit coin (which we know exists), but strictly speaking need not find out if it is heavy or light.
Thus we might lay one coin aside and use the following theorem, interpreting "all coins weigh the same" as "the coin put aside is counterfeit".
If you think this is a loophole to the problem, the theorem allows us one extra weighing in that last case and we can use it to compare the counterfeit coin against one of the known good coins.
Theorem. Given $(3^n-3)/2$ coins, it is possible with $n$ weighings to arrive at one of the following results: "Coin $i$ is a heavy counterfeit" with $1\le i\le \frac{3^n-3}{2}$, or "Coin $i$ is a light counterfeit" with $1\le i\le \frac{3^n-3}{2}$, or to arrive at the result "all coins weigh the same" already after $n-1$ weighings.
Proof.
For $n=1$ this is clear: Given $0$ coins, it takes $0$ weighings to declare that they "all" weigh the same.
For $n>1$, (in your mind) glue the coins into groups of three (note that $3\mid \frac{3^n-3}{2}$). This leaves us with $\frac{3^{n-1}-1}2=\frac{3^{n-1}-3}2+1$ big coins. Ignoring the extra coin, we can either determine that the first $\frac{3^{n-1}-3}2$ big coins weigh the same with $n-2$ weighings, or determine with $n-1$ weighings which of the first the first $\frac{3^{n-1}-3}2$ big coins is counterfeit and how.
In the first case, "un-glue" the last coin into three coins $a,b,c$; also un-glue another coin into $d,e,f$. We know that $d,e,f$ are not counterfeit! Compare $a+b$ against $c+d$. In case of equilibrium, we know that all coins weigh the same and we used $n-1$ weighings for that.
If $a+b>c+d$, either $a$ or $b$ is too heavy or $c$ is too light. Compare $a$ against $b$; in case of equilibrium, $c$ is too light, and otherwise the heavier of the two coins is found. That is, we have determined the counterfeit coin and its type in $n$ weighings.
In the second case, we have found a counterfeit big coin and know if it is too heavy or too light. Un-glue it into three smaller coins $a,b,c$ and compare $a$ against $b$. In case of equilibrium, $c$ is counterfeit and in the same way the big coin was. And otherwise, we see which of $a,b$ is too light or too heavy, respectively. That is, we have determined the counterfeit coin and its type in $n$ weighings.
The theorem now follows by induction. $\square$
No comments:
Post a Comment