Gold Coins and a Balance

Question

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?)

Answer 1

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.

Answer 2

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.