Odd marble out in $m$ weighings on a balance

111 Views Asked by At

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

1

There are 1 best solutions below

0
On BEST 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.