You have 8 identical looking rods, 2 of which are radioactive, though you don't know which. You also have a box which can test for radioactivity, which can hold any number of rods. After the test, the box will indicate whether or not at least one of the rods inside were radioactive.
What is the fewest number of tests it takes to determine the radioactive pair?
In the worst-case scenario, it requires
six tests
to locate the radioactive rods. Several answers already describe strategies for locating the radioactive rods. I will give another.
Testing strategy: Start by testing two rods. If neither of these rods is radioactive, use the five remaining tests on five of the six remaining rods, one at a time. If two of these rods are radioactive, we are done. If only one is radioactive, then the single untested rod must also be radioactive.
If the first test indicates at least one of the two rods is radioactive, then divide the remaining six rods into two groups of three, and test both groups. If neither group contains a radioactive rod, then the initial two rods tested must both be radioactive. If one of the two groups of three is radiactive, we will use our final three test on a single rod each, one rod from the initial group of two, and two rods from the group of three containing a radioactive rod. Each of these groups has exactly one radioactive rod, so testing all but one of the rods (one at a time) is enough to determine which rod in each group is radioactive.
Proof that this cannot be done with fewer tests: Suppose we have a strategy that is guaranteed to find the radioactive rods with five tests. The first test will involve $k$ rods. Initially, there are ${8\choose 2}=28$ possibilities for the pair of radioactive rods. After the first measurement, there will be either $28-{8-k\choose 2}$ possibilities (if at least one of the tested rods is radioactive), or ${8-k\choose 2}$ possibilities (if none of the tested rods is radioactive). Only four tests will then remain, so we can only distinguish between $2^4=16$ possibilities. This means we need $28-{8-k\choose 2}\leq 16$ and ${8-k\choose 2}\leq 16$. Direct computation shows that this is only satisfied for $k=2$, so our strategy must start by testing exactly two rods.
Suppose that neither of the two rods we test first is radioactive. Our next test will involve $j$ of the remaining rods. At this point, there are ${6\choose 2}=15$ possibilities for the pair of radioactive rods. After the second test, the number of possibilities will either be $15-{6-j\choose 2}$ or ${6-j\choose 2}$. After this test, we will only have three tests remaining, so we need $15-{6-j\choose 2}\leq 8$ and ${6-j\choose 2}\leq 8$. There is no value of $j$ for which both of these inequalities hold.
Let's get a baseline answer:
6 tests
Split the rods into groups of 2, test them (4).
If only one group is hot, you're good.
Otherwise, you have 2 groups of 2, 1 each which is radioactive. Test one of each. (2)
If hot, found; otherwise the other one is hot.
Edit: For a more generalized answer, I think the worst case is $2 * \log_2{N}$
Split the group in half, check both groups.
If one each, do binary search in each.
Otherwise, split the hot half, checking both groups.
Repeat.
Here's another way to get
6 tests
First, split the rods into groups of 4 and test them (2)
If both groups have a radioactive rod, do the following for both groups: take two of the rods and test them. If the test is positive, check one of those two. If the test of two rods was negative, test one of the other two rods. If the check of the single rod is negative, it was the other rod in that pair. If it is positive, obviously you've found the radioactive rod. This takes 4 tests to check both groups.
If only one group has radioactive rods, split the group in two. If the first pair you check is not radioactive, it is the remaining two rods. Otherwise, test one of the two by itself - if it is not radioactive, you know the other one is and the second radioactive rod is in the other pair and can determine which with one more test. If the one you check is radioactive, test the other one. If it is not radioactive, the radioactive rod is in the other pair and can be found with one more test. The worst case scenario is 4 tests.
I guess I'll just add another answer for:
6 tests in a worst-case-scenario
But for a lowest average number of tests over many scenarios:
Label your rods A,B,C,D,E,F,G,H
To make use of all possible outcomes, test two equal groups, but leave two behind, so...
P(done after step 1) = 1/28
P(done at step 2) = P(both in same trio) + P(trio and G,H) = 3/14 + 6/14 = 9/14
P(done at step 3) = P(one in each trio) = 9/28
I haven't worked through the probabilities/combinatorics completely, but this seems to have a lower average number of tests. If you had to stick with an algorithm from the beginning, this technically works better than some other algorithms, though the worst-case-scenario will still be 6 tests.
I'd be really interested to see someone prove that their answer is correct, which would involve calculating the probabilities of each test scenario to find the lowest average test number via Monte Carlo. If someone wants to do that, I'll owe them a lifetime's reputation.
Just because a test is successful doesn't mean we can eliminate the unchosen rods. Therefore, we always have to cover every group not yet confirmed to fail the test (if there aren't already 2 "successful" groups with no common rods), and their rods. The larger the groups that can be confirmed to fail are, the better. If the rods aren't divided equally, the smallest group might fail and the biggest ones succeed, so it doesn't give the best worst-case scenario.
After doing these, you'll know which quarter(s) has/have the radioactive rods. Even if they're two different quarters, you'll only need 2 more tests, which makes 6:
Take the other 4.
Take half of both groups.
Take the other halves.
|
asked |
|
|
viewed |
1,461 times |
|
active |
