Finding algorithm among 3 color balls

Question

You have $5$ white, $5$ black, and $5$ red balls. There is exactly $1$ radioactive ball among each group. There is a device, which says if there is at least one radioactive ball among some group of balls (quantity and color doesn't matter). You have to give an algorithm that sorts out the $3$ radioactive balls with only $7$ measurements.

So I thought there are $5*5*5=125$ possibilities, and if I imagine the algorithm as a Boolean tree, I have to balance it as equal as possible. So I took for first measurement $a_1, b_1, c_1$. If the device gives negative, that means, on one side of the tree there are $4*4*4$ possibilities left, so on the other side $61$. If we take the path of positive result ($61$ possibilities), for next measurement I take $a_2, a_3, b_2, b_3$, which divides the outcomes to $31$ (in case of positive result of second measurement) and $30$ (when the result is false). From here it's getting very messy and can't actually think how to continue. So any help will be appreciated.

Answer 1

Here is a solution. I started with the same initial test you did, but a different second test.

Here was my general strategy in solving. I envisioned the solution space as a cube; a test corresponded to selecting a subset which is shaped like a rectangular block. You either eliminate all the squares inside the block, or outside the block, both cases must have at most $2^k$ elements, if there are $k$ tests left. I think you knew all that. The only other basic principle I adhered to was to try to make the resulting shapes as simple as possible, like a union of a couple rectangular blocks.

1. Test $a_1,b_1,c_1$. If positive, go to $2$.
   • If negative, perform binary search on the other $12$ balls.
2. Test $a_5$ and $c_1$. If positive, go to $3$.
   • If negative, you know either $a_1$ or $b_1$ is radioactive. Test $b_1$.
     • If $b_1$ is not radioactive, perform binary search on $\{b_2,b_3,b_4,b_5\}$ and $\{c_2,c_3,c_4,c_5\}$.
     • If $b_1$ is radioactive, perform binary search on $\{a_1,a_2,a_3,a_4\}$ and $\{c_2,c_3,c_4,c_5\}$.
3. Test $a_1,b_1,c_2,c_3,c_4,c_5$. If positive, go to $4$.
   • If negative, you know $c_1$ is radioactive. Binary search on $\{a_2,a_3,a_4,a_5\}$ and $\{b_2,b_3,b_4,b_5\}$.
4. Test $a_1$. If negative, go to $5$.
   • If positive, you know $c_1$ is radioactive (from test $2$). Perform binary search on the $b$ balls.
5. From tests $1,3$ and $4$, you know $b_1$ is radioactive. Test $c_2,c_3,c_4,c_5$.
   • If positive, test $2$ implies $a_5$ is radioactive. Binary search on $\{c_2,c_3,c_4,c_5$}.
   • If negative, you know $c_1$ is radioactive. Binary search $\{a_2,a_3,a_4,a_5\}$.