Searching radioactive balls
Solution 1:
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.
- Try 1-4, we get positive.
- Try 5-8, positive.
- Try 9-11, positive. So we know 12-14 are cold.
- 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:
