12
$\begingroup$

There are $n$ balls, and $m$ of them are radioactive. You can test any set of balls and find out whether there is at least one radioactive ball in this set (but it is impossible to know how many of them are radioactive). What is the minimal possible number of tests that can guarantee finding of all radioactive balls?

It is clearly $\geq \lceil \log_2(C_n^m) \rceil$ by pigeonhole principle. Indeed, there are $C_n^m$ possible combinations of radioactive balls but a sequence of $k$ binary tests can only have $2^k$ distinct outcomes.

That bound is tight for degenerate cases $m = 0$ and $m = n$ (we do not need to test anything in that case) and for case $m = 1$ (use binary search here). However, it not tight in general. For example, the minimal possible number of tests for $m = n - 1$ is $n-1$. That is because in that case we can only test individual balls (otherwise the test will return true no matter what) and there are $n$ of them. Therefore we need something better.

$\endgroup$
4
  • 1
    $\begingroup$ Can we take $n$ and $m$ as known? $\endgroup$ May 13, 2021 at 13:17
  • 1
    $\begingroup$ @GerryMyerson, yes $\endgroup$ May 13, 2021 at 13:41
  • 4
    $\begingroup$ This is the noiseless group testing problem - this survey gives a pretty exhaustive account. $\endgroup$ May 16, 2021 at 11:54
  • $\begingroup$ Thanks for link, but oof, guess I missed. FYI: en.wikipedia.org/wiki/Group_testing also decent. $\endgroup$
    – Trevor
    May 16, 2021 at 20:23

1 Answer 1

2
$\begingroup$

It does seem it's better to think about this as identifying the cold (non-radioactive) balls rather than hot balls, though it's logically equivalent. I think I found a way to solve the $n=14,m=3$ case with $9$ checks. Again, I assume we can simulate a worst case by having all tests come back positive, provided a negative result would tell us even more.

  1. Try 1-4, we get positive.
  2. Try 5-8, positive.
  3. Try 9-11, positive. So we know 12-14 are cold.
  4. For each of the first three groups, two binary checks will narrow down which ball is hot, adding six more for a total of 9 checks.

Clearly better than the $12$ I suggested originally. In general, the approach here is to initially divide the balls into $m+1$ groups, where we test all but one of them. One or more of those groups will be shown to be negative, and we drill down with binary search on the remaining groups as required.

I believe there's a good chance this approach is optimal. In particular, it naturally handles the $m=n-1$ case and the $m=1$ case, as well as a handful of other cases I could verify. This can be represented as

$$m+(n\bmod (m+1))\left\lceil\log_2\left\lceil\frac{n}{m+1}\right\rceil\right\rceil+(m-(n\bmod (m+1))\left\lceil\log_2\left\lfloor\frac{n}{m+1}\right\rfloor\right\rceil\ ,$$

though there's probably a cleaner way to write that. The issue here which makes it uglier is that e.g. with $n=14,m=3$, we want to split into groups of $\{4,4,3,3\}$, and make sure we account for the required moves to binary-search all but the last entry, which we assume has been implied to be cold. Note that in this example, the first two $4$s don't take an extra check to binary-search compared to the $3$, but it won't always work out that way.

Some results using this approach:

$\endgroup$
1
  • $\begingroup$ At least, we need to modify the binary search. Let $c=n-m$, so $c$ is the number of "cold" (non-radioactive) balls. There's no point testing groups larger than $c$. If during the search we identify any cold balls, we can update $c$. $\endgroup$
    – PM 2Ring
    May 14, 2021 at 11:17

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.