3
$\begingroup$

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.

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

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\}$.
$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Vahe Karamyan Apr 9 '19 at 7:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.