1
$\begingroup$

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

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

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Jared Apr 17 '13 at 5:32
0
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • 1
    $\begingroup$ According to this answer, $f(13)\le 3$, although I haven't checked its validity. $\endgroup$ – Jared Apr 17 '13 at 5:35
  • $\begingroup$ 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”. $\endgroup$ – Alex Ravsky Apr 17 '13 at 6:07
  • $\begingroup$ @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. $\endgroup$ – Pieter Geerkens Apr 17 '13 at 21:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.