5
$\begingroup$

There are $n$ balls out of which $k$ are defective, where $k<n/2$. All defective balls have the same weight $w$, and all non-defective balls have the same weight $v$ with $v<w$.

Determine all defective balls with the smallest possible number of weighings on a two-armed balance.

$\endgroup$
  • $\begingroup$ I'm not convinced this makes a good question here. The specific case n=12, k=1 is a famous and accessible puzzle. The general case is a good topic for a combinatorics paper. $\endgroup$ – Colonel Panic Oct 15 '15 at 14:52
  • $\begingroup$ @ColonelPanic: I think it is fine assuming the question asker doesn't know that it is an unsolved problem in mathematics, and a good answer would be a reference like Gamow posted. It would be beneficial if question askers would say when they do not know if there is a nice solution. $\endgroup$ – Tyler Seacrest Oct 15 '15 at 15:14
  • $\begingroup$ This has been tagged as a job-interview-question. Does this mean that you were asked it during a job interview, or were you planning on asking it when interviewing someone else? $\endgroup$ – Gordon K Oct 16 '15 at 12:24
3
$\begingroup$

1.) It is easy to see that you can always do with $n-1$ weighings: put the first ball into the left pan, and in $n-1$ steps try each of the remaining $n-1$ balls in the right pan. This divides the balls into two groups (balls thta have equal weight as the first ball, and balls that have different weight). The smaller group are the defective balls.

2.) It is easy to see that any deterministic weighing strategy needs at least $\log_3{n\choose k}$ weighings by the standard information theoretic argument: There are ${n\choose k}$ possible scenarios for choosing $k$ defective ones out of a total of $n$ balls, and every weighing only has three possible outcomes (left pan heavier; right pan heavier; both pans equally heavy).

3.) Laszlo Pyber has designed a strategy that in the worst case uses at most $\log_3{n\choose k}+15k$ weighings (L. Pyber, "How to find many counterfeit coins? Graphs and Combinatorics 2 (1986), pages 173–177). Note that Pyber's result is strong if $k$ is very small in comparison to $n$ (like the cases with $k=\log\log n$), but weak if $k$ is large (like $k>n/15$).

4.) The exact optimal number of weighings for every combination of $n$ and $k$ is an unsolved problem in combinatorial search theory.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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