9
$\begingroup$

In one variant of the classic counterfeit coins problem you are given a bag of $n$ numbered but otherwise identical looking coins and a scale and your job is to find which coins are counterfeit. Counterfeit coins all have one weight and the other coins all have another weight. The scale can only tell you if two sets of coins have the same weight, or which one of the two is heavier.

I am interested in a small extension where rather than using scales you can explicitly weigh sets of coins (on a digital scale, say). For simplicity let us also set the weights of the coins to either $1$ or $0$ depending on whether they are counterfeit or not. How many weighings do you need to be sure to determine which of the coins are counterfeit? I am interested in large $n$ answers. Bounds or asymptotic results (or references to them) would be really great.

The first observation is that if $n>4$ you can always get away with fewer than $n$ weighings.

I have the book "Combinatorial group testing and its applications" by Hwang and Du but I can't find any reference to this version of the problem. (See http://bit.ly/1cACC2G for Google books link.)

[Equivalent problem posted to https://math.stackexchange.com/questions/600328/a-whats-my-vector-game before I had reformulated it as this classic looking counterfeit coin problem. I have also posted some explicit solutions for small $n$ there.]

Improve this question
$\endgroup$
7
  • $\begingroup$ Let the weight of all the coins be $k$. If counterfeits are $0$, then isn't the answer just $n-k$ counterfeits? Am I missing something? $\endgroup$
    – Tim Ratigan
    Commented Dec 10, 2013 at 18:18
  • 1
    $\begingroup$ If any number of coins can be counterfeit, there are $2^n$ possibilities, so in the worst case we'll need at least $(n \log 2)/(\log n)$ weighings. It would be very cool to find a way to realize this as an asymptotic upper bound. $\endgroup$
    – Jeremy Kahn
    Commented Dec 10, 2013 at 19:23
  • 1
    $\begingroup$ Note, the OP asked an equivalent version of this problem two days ago (Dec. 9, 2013, or thereabouts) at math.stackexchange.com/questions/600328/a-whats-my-vector-game $\endgroup$
    – Barry Cipra
    Commented Dec 11, 2013 at 23:38
  • 1
    $\begingroup$ I think the actual value should be about twice as large as the lower bound Jeremy Kahn gave. It is hard to measure a subset of any size and get a range of likely possibilities wider than a band of size $c\sqrt{n}$. $\endgroup$
    – Douglas Zare
    Commented Dec 12, 2013 at 21:55
  • 1
    $\begingroup$ Variants of this puzzle appear in Dennis Shasha's The Puzzling Adventures of Dr. Ecco. On p. 107: given 20 coins determine which are fake and which are real in 15 weighings, with the limitation that you can only weigh up to three coins at a time. On p. 108, Contest Puzzle #7 is to do the same in 10 weighings, given that there are exactly four fakes. As in your problem, each weighing reveals the exact number of fake coins weighed. $\endgroup$
    – bof
    Commented Dec 14, 2013 at 6:20

2 Answers 2

Reset to default
8
$\begingroup$

This problem was solved (up to a small multiplicative factor) by Erdos and Renyi: http://www.renyi.hu/~p_erdos/1963-12.pdf

Ps. Wow, Douglas Zare has a good intuition!

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ And at the very end of the paper they refer to an article of Lindström, then not yet published, which shows that the factor indeeds tends to $2$ in the limit. $\endgroup$
    – Carsten S
    Commented Dec 16, 2013 at 14:35
3
$\begingroup$

In his book aimed at general audience,

MR1710978 Steinhaus, H. Mathematical snapshots. Translated from the Polish. With a preface by Morris Kline. Reprint of the third (1983) English edition. Dover Publications, Inc., Mineola, NY, 1999. vi+311 pp. ISBN: 0-486-40914-7 (in the chapter "Weighing, measuring and fair division", which can be glimpsed at in Google books)

Hugo Steinhaus says that for n objects the number $1+kn-2^k$ of weighings is sufficient, where $k=1+[\log_2 n]$ (and $[\cdot]$ denotes the integer-part function), and that $k$ alone was proved to be sufficient for n=3,4,5,6,7,8,9,10,11. I do not know the references for the proofs.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Thanks for the reference. If I am not mistaken you are referring to the formula on page 56 (in which case I think it should be $1+kn-2^k$). This method sorts the coins by weight but that is more expensive than just doing $n$ weighings isn't it? As an extra data point, our problem can be solved in $4$ weighings when $n=5$. $\endgroup$
    – user32786
    Commented Dec 10, 2013 at 20:05
  • $\begingroup$ I edited to correct the formula. I do not know any other general estimates for this problem. $\endgroup$
    – Margaret Friedland
    Commented Dec 10, 2013 at 20:19

You must log in to answer this question.