We have n balls where 1 is a little heavier than the others and we want to find that heavier ball. We can only put some balls on one side of the scale and some on the other side and see if it leans and to which side. How can we find lower and upper bounds for this problem? We want upper and lower bounds to be equal.


closed as off-topic by Emil Jeřábek, D.W., Jan Johannsen, Hsien-Chih Chang 張顯之, András Salamon Jun 27 '18 at 19:50

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "Your question does not appear to be a research-level question in theoretical computer science. For more information about the scope, please see help center. Your question might be suitable for Computer Science which has a broader scope." – Emil Jeřábek, D.W., Jan Johannsen, Hsien-Chih Chang 張顯之, András Salamon
If this question can be reworded to fit the rules in the help center, please edit the question.


This is called the "Counterfeit Coin Problem" contributed by E. D. Schell and we have the following theorem according to the paper "Counterfeit Coin Problem", 1977:

Theorem 1: Let $S$ be a set of coins, one lighter than the rest. The least number of weighings on a beam balance in which the light coin can be found is the unique $n$ satisfying $3^{n-1} < |S| \le 3^n$.

This bound is tight.

The paper also studies a more difficult variant of this problem, assuming only that the counterfeit coin is a different weight from the others -- either heavier or lighter.

  • $\begingroup$ Please do not answer off-topic questions. $\endgroup$ – Emil Jeřábek Jun 26 '18 at 7:21

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