Problem 1875

Solution:

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$;
- four 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 cases we check any pair and the taken ball (if $\varepsilon=1$) for radioactivity. Two cases are possible.

1. There is one set with two radioactive balls and one set with one radioactive ball.
2. There are three sets with one radioactive ball.

In both cases three measurements are enough to find the radioactive balls. The total number of the measurements is $t-1+3=t+2$. Since
$$\left[\frac{n+5}{2}\right]=\left[\frac{2 t-\varepsilon+5}{2}\right]=t+2+\left[\frac{1-\varepsilon}{2}\right]=t+2$$
we get that $L(n) \leq\left[\frac{n+5}{2}\right]$.