# Gold Coins and a Balance

Suppose we know that exactly $1$ of $n$ gold coins is counterfeit, and weighs slightly less than the rest. The maximum number of weighings on a balance needed to identify the counterfeit coin can be shown to be $f(n)=\lceil \log_3(n) \rceil.$

Now let $n\ge 3$, and suppose we don't know whether the counterfeit is lighter or heavier than an authentic gold coin? In this case, one might ask three related questions:

1. What is the maximum number of weighings, $f(n)$, needed to identify the counterfeit?
2. What is the maximum number of weighings, $g(n)$, needed to identify whether the counterfeit is lighter or heavier than an authentic coin, but perhaps not identifying the actual counterfeit itself?
3. What is the maximum number of weighings, $h(n)$, needed to identify both the counterfeit and its weight relative to an authentic coin?

It isn't hard to see that $h(n)=f(n)$ or $h(n)=f(n)+1$. Also, I think that $g(n)\le f(n)$. It seems for large $n$ that strategies can get fairly complex, so I'd be interested to see if there is a nice formula for $f,g,$ and $h$. (perhaps recursive?)

• It seems that $g(nm)\le g(n)$ for each $m$. This suggests the question: is there a number $c$ such that $g(n)\le c$ for each $n$? Apr 17, 2013 at 4:53
• It seems that $g(5)\le 2$, and $g(4m+1)\le 2$ too. Apr 17, 2013 at 5:14
• You're right, I've been too hasty. This is trickier than I thought. Apr 17, 2013 at 5:20
• But it seems to be simpler than I thought. :-) I've just rewrote my answer. Apr 17, 2013 at 5:28
• I decided to look at my sources, and found the problem (3) in the old Russian mathematic journal,"Kvant" I read it now. These results should be in English somewhere in Internet. Apr 17, 2013 at 6:18

It seems that $g(n)\le 2$ for each $n\ge 3$. It is easily to check that $g(3)=2$. If we have $n=4m+k$, where $0\le k<4$, then at the first weighting we compare two piles of $2m$ coins each. If them have equal weighs, then we compare the rest $k$ coins with $k$ coins from the pile. If the piles’s weights are not equal, then we compare the halves of one of them.

• Very nice. This shows that $g(n)=2$ for $n\ge 3$ because we can't extract enough information from one weighing. If the first weighing is balanced, we don't have enough information, and similarly if it is unbalanced, we can't say anything. Apr 17, 2013 at 5:32

Considering only problem (3):

I believe the maximum number of coins that can be solved in n weighings is 3 * 4^(n-2) for n>= 2.

This yields for small values of n:

N=2, 3 coins;

N=3, 12 coins;

N=4, 48 coins;

Anyone familiar with the classic problem of 12 coins and 3 weighings will readily solve 3in 2, and 48 in 4, by the same method of thirds. ( I won't spoil the problem by spelling out the whole solution.) These solutions all feel maximal, but I have not been able to prove that yet.

• According to this answer, $f(13)\le 3$, although I haven't checked its validity. Apr 17, 2013 at 5:35
• It seems that this answer did not show it, because there is a cheat in it: “"S" REPRESENTS A MARBLE KNOWN TO BE OF STANDARD WEIGHT, BUT IS NOT ONE OF THE 13. USE OF THIS ITEM IS CRITICAL TO THE SOLVING THE PROBLEM”. Apr 17, 2013 at 6:07
• @AlexRavsky: What are you talking about? I solved the 12 in 4 problem 35 years ago, after a couple of beers and a night of Bridge. Why spoil the fun for others. Apr 17, 2013 at 21:54