Odd marble out in $m$ weighings on a balance

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$ ...

-
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
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
Interesting pointer on a slightly different problem: cs.mcgill.ca/~colt2009/papers/004.pdf – minar Aug 26 '13 at 20:09
@MarkBennet See problem 3.12 – rschwieb Aug 26 '13 at 20:11
I think this is what you are looking for: jstor.org/discover/10.2307/… – minar Aug 26 '13 at 20:12

1 Answer

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.

-