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$? – Alex Ravsky Apr 17 '13 at 4:53
• It seems that $g(5)\le 2$, and $g(4m+1)\le 2$ too. – Alex Ravsky Apr 17 '13 at 5:14
• You're right, I've been too hasty. This is trickier than I thought. – Jared Apr 17 '13 at 5:20
• But it seems to be simpler than I thought. :-) I've just rewrote my answer. – Alex Ravsky Apr 17 '13 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. – Alex Ravsky Apr 17 '13 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. – Jared Apr 17 '13 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. – Jared Apr 17 '13 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”. – Alex Ravsky Apr 17 '13 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. – Pieter Geerkens Apr 17 '13 at 21:54