1

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

Jared
  • 31,451
  • 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 04:53
  • It seems that $g(5)\le 2$, and $g(4m+1)\le 2$ too. – Alex Ravsky Apr 17 '13 at 05:14
  • You're right, I've been too hasty. This is trickier than I thought. – Jared Apr 17 '13 at 05:20
  • But it seems to be simpler than I thought. :-) I've just rewrote my answer. – Alex Ravsky Apr 17 '13 at 05: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 06:18
  • In the article from “Kvant” I found a next bound: if $n>3$ and $m\le\frac 12(3^n-3)$, then $h(m)\le n$. This problem and this bound are old and well-known. Try to Google: http://www.google.ru/search?newwindow=1&safe=off&site=&source=hp&q=F.J.+Dyson+coins+weight&oq=F.J.+Dyson+coins+weight – Alex Ravsky Apr 17 '13 at 06:46
  • I just read this article. Dyson’s algorithm is very elegant, you should read about it. Moreover, it seems that $h(n)=\lceil \log_3 (2n+3)\rceil$ for each $n\ge 7$. I expect to continue my reading add to find more references. – Alex Ravsky Apr 17 '13 at 09:25

2 Answers2

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.

Alex Ravsky
  • 90,434
  • 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 05:32
0

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.

Pieter Geerkens
  • 901
  • 1
    According to this answer, $f(13)\le 3$, although I haven't checked its validity. – Jared Apr 17 '13 at 05: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 06: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