4

Thinking that this may be as poorly known as it was $35$ years ago when I first knew the truth - based on How can you pick the odd marble by 3 steps in this case? and others, I pose two closely related questions in one for general edification. You have $n$ marbles, one of which is lighter or heavier than the others, but you don't know which. You also have a fair, perfect, balance with which you are allowed to make $m$ weighings.

(i) If you need to know whether the "different" marble is heavy or light, as well as which one it is, what is the maximum value for $n$ given a fixed $m$? [The answer is $n=12$ for $m=3$]

(ii) If you only need to know which is the "different" marble, what is the maximum value of $n$ as a function of $m$? [We can achieve $n=13$ for $m=3$, but not many people seem to know that - see my answer to the linked question]

But I want to know for general $m$ ...

Community
  • 1
Mark Bennet
  • 100,194
  • 1
    This might be totally out of your interest, but a coding theory book I have has an interesting exercise about solving these sorts of weighing problems using the parity check matrix for a linear code. It would be a powerful tool since linear codes are so well-studied (if it applies to your setup). As you read you might keep your eyes open for such solutions. – rschwieb Aug 26 '13 at 19:53
  • @rschwieb Which book would that be? The thing is interesting, because for $m=3$ the answer $12$ seems to be everywhere, and the possibility of $13$ has few advocates. – Mark Bennet Aug 26 '13 at 19:56
  • 2
    Your formulation of (i) is ambiguous. If you only need to know whether the different marble is heavy or light without finding which one it is, you can do it with a constant number of weightings. The simple case occurs when the number of marbles $n$ is a multiple of 3. Then you can group the marbles into $3$ supermarbles containing $n/3$ marbles. Thus, you can solve the heavy/light question on 3 supermarbles. – minar Aug 26 '13 at 19:57
  • @minar will edit – Mark Bennet Aug 26 '13 at 19:59
  • 1
    Interesting pointer on a slightly different problem: http://www.cs.mcgill.ca/~colt2009/papers/004.pdf – minar Aug 26 '13 at 20:09
  • 1
    @MarkBennet See problem 3.12 – rschwieb Aug 26 '13 at 20:11
  • 2
    I think this is what you are looking for: http://www.jstor.org/discover/10.2307/2975353?uid=3738016&uid=2129&uid=2&uid=70&uid=4&sid=21102583717863 – minar Aug 26 '13 at 20:12
  • @minar That deals with the first of my questions, but not the second (as the examples given assume a known good coin is available). And what I was really looking for in an answer was an explicit algorithm, so that future questions on the same topic could be referred to this one. The three coin problem seems to be repeated often, without generalisation. – Mark Bennet Aug 26 '13 at 20:19
  • Also look at: http://www.numericana.com/answer/weighing.htm (scroll all the way down to the table: Maximum Number of Coins Allowing Detection) – minar Aug 26 '13 at 20:31
  • This last reference really answers your two questions plus the variations with a good marble in addition. It also contains the sketch of a general algorithm to solve the problem. – minar Aug 26 '13 at 20:45
  • @minar - post it as an answer and highlight the key results so people don't have to go hunting for them - and I'll gladly accept an answer. – Mark Bennet Aug 26 '13 at 20:55

1 Answers1

2

You can find an answer to your question and, in addition, to the variations with a good marble given as reference in: http://www.numericana.com/answer/weighing.htm#counterfeit

With $m\geq 1$, the number of marbles that can be weighted in case (i) is $n=(3^m-3)/2$, in case (ii) it is $n=(3^m-1)/2$. With an extra reference marble, the bounds are improved to $n=(3^m-1)/2$ and $n=(3^m+1)/2.$ [In particular, for $m=3$, the number of marbles are 12, 13 and 13, 14]

The above page also contains the sketch of an algorithm for solving the problem and some useful links.

minar
  • 791