Searching Algorithm among 2 color balls.

Question

You have $2^k + 1$ white and $2^k - 1$ black balls. Each group of balls have exactly one radioactive ball. You have a device which measures group of balls (quantity and color doesn't matter) and says whether there is at least one radioactive ball among them. Find an algorithm that sorts out the 2 radioactive balls with complexity of $2k$. Complexity is the count of steps in worst-case scenario.

I have solved this problem for simpler case, like having n balls, and only one of them is radioactive. With binary search it gives complexity of $\lceil \log_2n\rceil$. But now I am stuck. Also please give advice, like how should I approach to solve this kind of problems in general. Thanks.

Answer 1

The number of possibilities for the two radioactive balls is $(2^k+1)(2^k-1)=2^{2k}-1$. With $2k$ tests, we can distinguish among at most $2^{2k}$ possibilities. Therefore, this problem is tight; we will have to divide the number of possibilities pretty much in half at every step. So the general strategy for this problem is to come up with a test, then count how many possibilities would remain under each outcome. If those do not differ by at most one, try a different test until they do.

Suppose you initially set aside $w$ white balls and $b$ black balls, and test everything else. If the tested balls are not radioactive, then there are now $w\times b$ possibilities for the pair of radioactive balls. From the first paragraph, we need to have $b\times w=2^{2k-1}$ or $b\times w=2^{2k-1}-1$. The first one is easier to solve; in fact, the only way to achieve $b\times w=2^{2k-1}$ is to have \begin{align} w&=2^k\\ b&=2^{k-1} \end{align} This means the first test would consist of one white ball and just under half of the black balls. See if you can solve the puzzle from here.

It may help to visualize the set of states as a $(2^k-1)\times (2^k+1)$ grid. The rows are labeled with black balls, the columns with white balls, and you want to find the square corresponding to the radioactive balls. When you do a test, you select several rows and several columns. If the test comes back negative, then you get a smaller rectangle. If it comes back positive, then you remove a rectangle, leaving an $L$ shaped region.

Solution:

If the tested balls are not radioactive after doing the first test described above, then you can do binary search on the white balls $2^{k}$ white balls, then binary search on the $2^{k-1}$ black balls.

If the first test is radioactive, then your next test should have $2^{k-2}-1$ black balls which were in the first test, plus the white ball which tested the first time. If this test comes back negative, you perform two binary searches on the black and white balls.

If this second test is radioactive, then the next test should be $2^{k-3}-1$ black balls which were in the last test, and that same white ball. And so on...

Until you get a negative test, you keep dividing the tested black balls into two almost equal halves and testing the smaller one, plus the initial white ball. This continues until there is one black ball left, with $k-1$ tests used.

At this point, you should test that white ball by itself. If it is radioactive, then you should to binary search on all the black balls, and if note, you should do binary search on the remaining $2^k$ white balls.