Searching for tagged balls under constraints

Question

(This is a modification of this problem.)

You have $k$ white balls and $k$ black balls, and know that exactly one of each color is radioactive. You can place any number of balls of your choosing in a radiation detector that reveals only whether $0$, $1$ or $2$ measured balls are radioactive.

Specify an algorithm that identifies the two radioactive balls in as few such measurements as possible in the worst case.

---

Some thoughts:

The total uncertainty in the initial system, in bits, is $\log_2 k + \log_2 k = 2 \log_2 k = \log_2 k^2$.

(Sparked by a comment by @leonbloy.) The selection is a Bernoulli process and the most information one can obtain is $3/2$ bits. Thus in principle the total number of needed measurements is bounded by:

$$\left\lceil \frac{2\log_2 k}{3/2}\right \rceil.$$

Here is a decision tree for the small case $k=2$. We label the balls $b_1, b_2, w_1, w_2$ and first measure $b_1$ with $w_1$. (I'm pretty sure that testing one black and one white provides the maximum information.) The arcs denote the output of the measurement. In the case of $0$ or $2$ detected radioactive balls, we are done and the red boxed leafs are our answers.

If the result is $1$, we then measure $b_1 w_2$ which can only give a $0$ or $2$ output, and our final conclusions are shown at the bottom leafs.

The expected number of measurements is ${\cal E}[m] = \frac{1}{2} \cdot 1 + \frac{1}{2} \cdot 2 = 1.5$.

Of course there are other ways to guarantee an answer in two measurements, for instance one measurement on a single black, then one measurement on a single white. But that algorithm guarantees you will need two measurements, i.e, ${\cal E}[m] = 2$. (Admittedly, both algorithms have the same worst case performance.) The decision tree above gives you an answer half of the time with just a single measurement--it exploits more from the three-way answer than would a two-way answer.

(I have a feeling this problem has been solved in the literature, but I couldn't find it on SE nor with a cursory search online.)

Answer 1

Sub-optimal attempts. Hopefully others can improve these...

Assume for now $k=2^m$, i.e. $k$ is a power of $2$.

Algorithm $A$ is based on the $(1/4, 1/2, 1/4)$ split suggested by @leonbloy. My contribution here is merely to turn the split into an actual recursive algorithm.

Since $(1/4, 1/2, 1/4) \rightarrow 1.5$ bits, this suggests an average no. of rounds of ${\log_2 k^2 \over 1.5} = {4\over 3} \log_2 k$. Since the biggest subset has size $1/2$, this also suggests a worst-case no. of rounds of $\log_2 k^2 = 2 \log_2 k$. However, both of these are just lower-bounds -- their achievability is contingent on finding an actual algorithm.

Algorithm $A$ achieves ${3\over 2} \log_2 k$ average (worse than the ${4\over 3}$ bound), and $2 \log_2 k$ worst case (equal to the bound).

Algorithm: Partition the white balls into two halves $W_1, W_2$ and the black balls into two halves $B_1, B_2$. Test $W_1 \cup B_1$.

• If test result $=0$, we know the radioactive balls are in $W_2, B_2$. We have reduced the problem to half the size $k \rightarrow k/2$ in one test.

• If test result $=2$, we know the radioactive balls are in $W_1, B_1$. We have reduced the problem to half the size $k \rightarrow k/2$ in one test.

• If test result $=1$, then we test $W_1$. (Note: this is a point of inefficiency.) If new test result $=1$, we know the radioactive balls are in $W_1, B_2$. If the new test result $=0$, we know the radioactive balls are in $W_2, B_1$. In either case we have reduced the problem to half the size $k \rightarrow k/2$ in two tests.

I.e., when reducing $k \rightarrow k/2$, we either need $1$ test (prob $=1/2$) or $2$ tests (prob $=1/2$). There are $m= \log_2 k$ such "rounds", each needing $1$ or $2$ tests, and each round is independent. The average-case ${3\over 2} m$ and worst-case $2m$ follow immediately.

If $k$ is not a power of $2$, then no. of rounds $m= \lceil log_2 k \rceil$. It turns out (algebra omitted), if we divide the balls as evenly as possible, prob of needing $1$ test $\ge 1/2 \ge$ prob of needing $2$ tests, so the average-case is in fact very slightly better than ${3\over 2} m$.

---

UPDATE: After ruminating for another hour or so, here's a better Algorithm $B$.

It achieves a worst-case of $1.63 \log_2 k$ and an average case of $1.32 \log_2 k$. Both of these growths are better (i.e. slower) than the "lower-bounds" predicted by the $(1/4,1/2,1/4)$ splits (which were $2 \log_2 k$ and ${4 \over 3} \log_2 k$ respectively) because algorithm $B$ achieves $(1/3, 1/3, 1/3)$ splits in some of the tests.

Again assume for now $k=2^m$.

There are two stages. In the first stage, we run exactly $m$ tests. Let the white balls be named by $m$-bit vectors $\{0,1\}^m$, and similarly for the black balls.

For $j \in \{1, 2, ..., m\}$, test number $j$ will have all the balls (white and black) whose $j$th bit is $1$. I.e. there will be half the white balls and half the black balls, thus implementing a $(1/4, 1/2, 1/4)$ split.

• If test result $=0$, we know both radioactive balls have the $j$th bit $0$.

• If test result $=2$, we know both radioactive balls have the $j$th bit $1$.

• If test result $=1$, we know the two radioactive balls have $j$th bit values which are different. I.e. either the white ball has $0$ and the black ball has $1$, or vice versa, at the $j$th bit.

And the end of this first stage (all $m$ tests), we can collect the results into an $m$-symbol vector $\{0, 1, ?\}^m$. For instance: $01??1?0$. In this example, we know the beginning two bits are $01$, the $5$th bit is $1$, and the last bit is $0$. We dont know bits at positions $j = 3, 4, 6$ but we know that, whatever these values are for the white radioactive ball, the values for the black radioactive ball are the bitwise negation. E.g. if the white radioactive ball turns out to be $01\color{red}{00}1\color{red}{1}0$ then the black radioactive ball must be $01\color{blue}{11}1\color{blue}{0}0$. We will call such two balls partners -- they are either both radioactive or both non-radioactive.

So we can run a very efficient second stage: Let $X$ be the number of undetermined bits (number of $?$ symbols). Let $P =$ the set of candidates for radioactive white balls, and initially $|P| = 2^X$. Divide $P$ into three equal groups (as equal as possible) $A,B,C$. Test together white balls in $A \cup B$ and black balls which are partners of $A$.

• If test result $=2, 1, 0$ respectively, then the radioactive white ball is $\in A, B, C$ respectively.

Thus we can reduce the size of the candidate set by a factor of $3$ every time.

Worst-case analysis: In the worst case, all $m$ tests of the first stage return a $?$. Then the second stage requires $\log_3 2^m = m \log_3 2$ tests. The total is $m (1 + \log_3 2) \approx 1.63 m = 1.63 \log_2 k$.

Average-case analysis: I am not absolutely sure the following is OK, but here it goes... the second stage requires $\log_3 2^X = X \log_3 2$ tests, where $X \sim Binomial(m, 1/2)$. Thus $E[X] = m/2$ and the average total number of tests is $m + {m \over 2} \log_3 2 \approx 1.32 m = 1.32 \log_2 k$.

The fact that in some tests you cannot divide evenly (e.g. into $A,B,C$)... I imagine that can be handled by adding $O(1)$ to the growths, but I'm too lazy to track those down for now.

Answer 2

The following algorithm finds both radioactive balls in $\mathcal O(\log_\phi k)=\mathcal O(1.44\log_2 k)$ tests, at worst. Each test eliminates $2/1.44\approx 1.39$ bits of uncertainty on average.

Assume first that $k=F_n$ is a Fibonacci number. Let $S_n$ be the state where there are $F_n$ white balls and $F_n$ black balls which could be radioactive.

If you are in the state $S_n$, test $F_{n-1}$ black balls and $F_{n-1}$ white balls.

• If there are two radioactive balls, we move to state $S_{n-1}$.

• If there are zero radioactive balls, we move to state $S_{n-2}$.

• If there is one radioactive ball, then there are $2 \times F_{n-1}\times F_{n-2}$ possibilities. The white balls and black balls are partitioned into sets of size $F_{n-1}$ and $F_{n-2}$ so that one color has its radioactive ball in the large set, and the other has its radioactive ball in the small set. Call this state $T_{n-1}$.

Suppose you are in state $T_{n}$, so the white ball and black balls are in two parts of size $F_n$ and $F_{n-1}$, so that one radioactive ball is in a large part an the other is in a small part. Test $F_{n-1}$ white balls from the large part, all the black balls from the small part, and $F_{n-2}$ black balls from the large part (see diagram for a good visualization).

• If there are two radioactive balls, we move to state $S_{n-1}$.

• If there are zero radioactive balls, we move to state $S_{n-1}$.

• If there is one radioactive ball, we move to state $T_{n-1}$.

We start in state $S_n$, and from $S_k$ or $T_k$ we move to either $S_{k-1}$ or $T_{k-1}$ at worst. Therefore, after at most $n-2$ tests, we will be in either $S_2$, in which case we are done, or $T_2$, in which case one more test suffices. Therefore, we can solve $k=F_n$ in at most $n-1$ tests.

In general, if $k$ is not a Fibonacci number, then we can add "dummy" balls to make it a Fibonacci number, so $n-1$ tests suffice where $n$ is the smallest integer so $F_n\ge k$.

Using the approximation $F_n\approx \frac1{\sqrt 5}\phi^n$, we can compute the worst case number of tests as a function of $k$ almost exactly: \begin{align} F_{n-1}<k\le F_n &\implies \frac1{\sqrt5}\phi^{n-1}\lesssim k\lesssim\frac1{\sqrt5}\phi^{n} \\&\implies \log_\phi(k\sqrt{5})\lesssim n\lesssim \log_\phi(k\sqrt{5})+1 \\&\implies n \approx \Big\lceil \log_\phi k+\log_\phi\sqrt{5}\Big\rceil \\&\implies \text{# tests}=n-1 \approx \Big\lceil \log_\phi k+0.672\Big\rceil \end{align}