Problem 10.3. Three of $n$ equal balls are radioactive. A detector measures radioactivity. Any measurement of a set of balls gives as a result whether 0 , 1 or more than 1 balls are radioactive. Denote by $L(n)$ the least number of measurements that one needs to find the three radioactive balls.

a) Find $L(6)$.

b) Prove that $L(n) \leq \frac{n+5}{2}$.

Emil Kolev
10.3. a) We shall prove that 4 measurements are enough. Denote the balls by $1,2,3,4,5,6$ and measure consecutively $\{1,2\},\{1,3\},\{1,4\}$ and $\{1,5\}$.

Case 1. If all the measurements show radioactivity, then 1 is a radioactive ball. If $\{1, a\}, a=2,3,4,5$, contains two radioactive balls, then $a$ is radioactive; otherwise, it is not. Hence we know which of the balls $1,2,3,4,5$ are radioactive and hence we also know whether 6 is radioactive or not.

Case 2. If some of the measurements shows no radioactivity, then 1 is not a radioactive ball. Hence we again know which of the balls $1,2,3,4,6$ are radioactive and then whether 6 is radioactive or not.

Assume that $L(6) \leq 3$, i.e, three measurements are enough. After two measurements we have $3^{2}=9$ possibilities. After the first measurement $1,2,3,4,5$ or 6 balls can be chosen. It is clear that among any 5 or 6 balls there are at least 2 radioactive; so a measurement with 5 or 6 gives no information.

Let $x, x \leq 4$, balls are chosen in the first measurement. If $x=1$ and the answer is "one radioactive ball", then the possibilities for the radioactive balls are $\binom{5}{2}=10$. On the other hand, the number of the possibilities for the other two measurements are $3^{2}=9$. Analogously, for a first measurement of:

- two balls and answer "one radioactive ball", the number of the possibilities is $\binom{2}{1}\binom{4}{2}=12>9$;
- three balls and answer "more than one radioactive ball", the number of the possibilities is $\binom{3}{2}\binom{3}{1}+\binom{3}{3}=10>9$;
- three balls and answer "more than one radioactive ball", the number of the possibilities is $\binom{4}{2}\binom{2}{1}+\binom{4}{3}=13>9$.

Thus three measurements are not enough and so $L(6)=4$.

b) We shall show that $\left[\frac{n+5}{2}\right]$ measurements are enough for finding the three radioactive balls which will imply the desired inequality. Let $n=2 t-\varepsilon$, where $\varepsilon \in\{0,1\}$. Let us either pair the balls (if $\varepsilon=0$ ) or take a ball and pair the remaining (if $\varepsilon=1$ ). In both case we check any pair and the taken ball (if $\varepsilon=1$ ) for radioactivity. Two cases are possible.