# Finding algorithm among 3 color balls

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.

• These are hard problems! I am finding it hard to give hints... – Mike Earnest Apr 6 '19 at 19:49
• Well, we will have this kind of questions at our midterm :D – Vahe Karamyan Apr 6 '19 at 21:15

## 1 Answer

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\}$$.
• yeah, that is a good way. The thing is, when I do some weightings, I am not feeling that I am on the right path, so I don't want to continue :"D – Vahe Karamyan Apr 9 '19 at 7:12