Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

You have 15 balls, 2 of them are radioactive. You have to run 7 tests (no more) on the balls which will sort out the 2 radioactive ones guarenteed every time. You can test them in groups, or even one by one.

A "test" comprises of taking a subset of the balls and checking if this subset contains a radioactive ball (one or more) or not. The test does not determine the number of radioactive balls in the tested subset.

share|improve this question
8  
Presumably, what the test will do is tell you whether there is at least one radioactive ball among the balls you are testing, and this test will be 100% accurate each time. (The way you phrased it, it would seem that you can just test all 15 balls together, and the test will tell you which two are radioactive) –  Arturo Magidin Jun 6 '11 at 18:46
1  
You need n tests (at most) to find out one radioactive ball in a set of 2^n balls. It seems to me, then, that in this scenario 7 tests are enough to solve a stronger problem : 16 balls, always dividing the radioactive sets by two. –  leonbloy Jun 6 '11 at 19:28
1  
@leonbloy, why is that? If you have 4 balls there are 6 possible scenarios, but 2 tests can only yield 4 possible answers so I don't see how this can suffice. –  Alon Amit Jun 6 '11 at 19:31
    
@Alon: I meant 'one ball in a set with (just) one ball'. Then, say, in the first split (16 balls in two 8 sets), the test can return two types of result: if both sets are radiocative, then we need 3 tests for each set (ok); elsewhere, we continue splitting the (doubly) radioactive set –  leonbloy Jun 6 '11 at 19:38
2  
A more common version of this problem: You have some balls that are all the same weight except for one. Using a scale, find the heavy ball using as few weighings as possible. Searching keywords like "heavy ball scale" bring up some solutions that might be useful for you. –  Austin Mohr Jun 6 '11 at 19:46

10 Answers 10

Having two target objects actually makes this problem considerably more difficult. There are ${15 \choose 2} = 105$ possible results, and with 7 binary tests you can only distinguish among a total of 128 possibilities. So you don't have a lot of room for error; you pretty much have to cut the solution space in half with each test.

That said, I think the best algorithm starts by testing objects 12 through 15. If this test gives "no", then you know both target objects are in the remaining 11 objects (55 possibilities). Otherwise, at least one of the targets is in these four (50 possibilities). After that it gets a lot more complicated, but basically, each time try to make a test that splits the remaining possible results as exactly in half as possible. For example, if you've narrowed down to 11 objects, test objects 9-11 (28 no vs. 27 yes). If at least one of 12-15 is radioactive, test 8-12 (24 no vs. 26 yes).

I can't think of a simple way to explain the complete algorithm, like the balanced-ternary representation for the traditional weighing problem. But continuing in this pattern should give you the answer.

share|improve this answer

Some extra thoughts:

By sampling of balls, I mean a vector in $\mathbb F_2^{15}$. A test is a function $T: \mathbb F_2^{15} \to \mathbb F_2$, which is a polynomial that takes in a sample and returns if its radioactive or not. Now, if a solution to the puzzle exists, then by just evaluating $T$ at 7 points in $\mathbb F_2^{15}$, I am able to reconstruct the whole polynomial. So the kinds of polynomials that are allowed must be special and also connected to the fact that two of the balls are radioactive. Now, after a bit more thinking, I am stuck. Can anyone help me with this line of thought?


Just saw the other answer. So is mine wrong? In the sense, I don't know what binary testing etc. is or anything about algorithms.

There are 15 balls. Pair them in all possible ways. There are 105 possible choice of pairings. Label each such pairing with a binary number. There will be 7 places required. Test all those pairs which have 1 in the unit place and so on so forth for all the 7 places. We'll get a unique number at the end.

share|improve this answer
7  
Unfortunately, you have to put balls in the bin. Imagine 4 balls, two radioactive. There are six pairs, say 0=12, 1=13, 2=14, 3=23, 4=24, 5=34. Which balls go in the bin for the first test? –  Ross Millikan Jun 6 '11 at 21:05
    
Binary testing works when you have only one radioactive ball in a group. If there are eight, test four and you know which group of four it is in. Then split that four in half to get two and test a pair. n tests suffice for 2^n balls. Having two to find makes it much harder. –  Ross Millikan Jun 6 '11 at 22:13
    
With respect to your extra thought, the kinds of polynomials which are allowed are $P(x_0, ..., x_{14}) = x_i + x_j - x_i x_j$ for distinct $i$, $j$. –  Peter Taylor Jun 7 '11 at 16:28

I don't believe it can be done, but my proof is not complete. As Paul Z says, it looks right to test 12, 13,14, 15 first as you split the possibilities as evenly as possible-50/55. If the first test finds radioactivity you can succeed. Now test 5, 6, 7, 8, 9, 10, 11. If you again find radioactivity, you can do binary searches of 4 and 7 with 5 tests. If you don't, test 1, 2, 3, 4. If you find radioactivity you can do binary searches of 4 and 4 with 4 tests. If you don't, you have 4 tests to find 2 among 12, 13, 14, 15 and can just go one by one.

If the first test fails, you have 55 possibilities and 6 tests left. You now have to test 9, 10, 11, leaving 28 possibilities if the test fails and 27 if it finds radioactivity. Testing 10, 11 leaves 36 if it fails and testing 8, 9, 10, 11 leaves 34 if it succeeds, in both cases greater than 2^5=32. Focusing on the case the test of 9, 10, 11 fails you have to test 7,8 by similar logic. Again in the failure case there are 15 possibilities. If you test only 6 and fail there are 10 possibilities and if you test 5,6 and succeed there are 9. In either case 3 more tests are not enough.

The hole is to prove you cannot succeed by testing 11, 12, 13, 14, 15. If the test succeeds you have 60 possibilities, so it seems unlikely you can get there, but I haven't done the specifics.

Added: some more progress. If you test 11,12,13,14,15 and get yes it seems natural to test 5,6,7,8,9,10 next as that splits the 60 possibilities evenly. If you get yes again you are set. Test 5,6,11. If no, you have two groups of 4 and 4 guesses. If yes, test 11. If yes you have a group of 6 and 3 guesses. If no, you have 4+2 and 3 guesses. But if you get no on the test of 5,6,7,8,9,10 it seems natural to test 2,3,4 as that will give you 15 possibilities either way. But a no leaves you with finding 2 out of 6 with 4 guesses and there is no set to test that makes a split of 7/8 possibilities. There may be some better strategy.

If you test 11,12,13,14,15 and get no you are set. Test 8,9,10. If yes, there are 24 possibilities. Test 4,5,6,7. A yes gives you 3+4 with 4 tests left. If no, test 2,3. A yes gives you 2+3 with 3 tests. A no gives you 4 balls with 2 to find and 3 tests. Just test 3 individually. If 8,9,10 gives no, test 6,7. A no gives 5 balls to find 2 in 4 tests-just do 4 individually. If yes test 3,4,5. Yes gives 2+3 in 3 tests. No gives 4 balls with 2 to find with 3 tests.

share|improve this answer
    
miracle173's answer includes testing overlapping subsets, for example starting by testing 1,2,3,4,5 and if that is yes then testing 4,5,6. You would need to exclude that type of pattern too. –  Henry Jun 7 '11 at 13:44
    
@Henry: yes, I see that. I did that in one case, but didn't find the rest. –  Ross Millikan Jun 7 '11 at 13:49

Perhaps the analogy with the binary case (with only one radioactive ball) is restricting ourselves to consider a schema on non intersecting sets for each test. I'm not sure if that is optimal.

Consider for example this (unsuccessful) try:

Form 3 sets of 6 balls (A,B,C), with 1 pair interesection and empty triple intersection. (Venn diagram here). Test the 3 sets.

1) If all three return positive, at least one intersection must be radioactive. Test AB .

1A) If positive, we must find the remaining positive in C (we can do it in 3 tests).

1B) If negative, we seek in BC and, acorrding to the result in A or B (ok)

2) If one return negative, we have to find two balls, one in each of the remaining sets (with 5 elements, 1 intersected). I think this last step cannot be done, but I'm not sure.

share|improve this answer

You should make the measurement in the following way. "[x,...,y] true/false" means radioactivity was found / not found when measuring the balls with number x,...,y. The last two lines of each paragraphs are the tuples wich are possible after the last measurement is true / false. It is easy to process the remaining possibilities

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] true   
    measurement 3: [1,2,7,8,9,10,11] true    
    measurement 4: [1,2,7] true
    measurement 5: [1,6]
    [[1,4],[1,5],[1,6],[2,6]]
    [[2,4],[2,5],[4,7],[5,7]]

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] true   
    measurement 3: [1,2,7,8,9,10,11] true  
    measurement 4: [1,2,7] false  
    measurement 5: [4] 
    [[4,8],[4,9],[4,10],[4,11]]
    [[5,8],[5,9],[5,10],[5,11]]

    measurement 1: [1,2,3,4,5] true   
    measurement 2: [4,5,6] true   
    measurement 3: [1,2,7,8,9,10,11] false    
    measurement 4: [12,13,14,15]
    [[4,12],[4,13],[4,14],[4,15],[5,12],[5,13],[5,14],[5,15]] 
    [[3,4],[3,5],[3,6],[4,5],[4,6],[5,6]]

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] false   
    measurement 3: [7,8,9,10,11] true   
    measurement 4: [1,7] true   
    measurement 5: [7,8]
    [[1,7],[1,8],[2,7],[3,7]]
    [[1,9],[1,10],[1,11]]

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] false    
    measurement 3: [7,8,9,10,11] true    
    measurement 4: [1,7] false 
    measurement 5: [2] 
    [[2,8],[2,9],[2,10],[2,11]]
    [[3,8],[3,9],[3,10],[3,11]]

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] false    
    measurement 3: [7,8,9,10,11] false   
    measurement 4: [1,12]
    [[1,2],[1,3],[1,12],[1,13],[1,14],[1,15],[2,12],[3,12]]
    [[2,3],[2,13],[2,14],[2,15],[3,13],[3,14],[3,15]]

    measurement 1 [1,2,3,4,5] false   
    measurement 2: [6,7,8] true    
    measurement 3: [6]
    [[6,7],[6,8],[6,9],[6,10],[6,11],[6,12],[6,13],[6,14],[6,15]]
    [[7,8],[7,9],[7,10],[7,11],[7,12],[7,13],[7,14],[7,15],
           [8,9],[8,10],[8,11],[8,12], [8,13],[8,14],[8,15]]

    measurement 1 [1,2,3,4,5] false  
    measurement 2: [6,7,8] false    
    measurement 3: [9,10] true   
    measurement 4: [9]
    [[9,10],[9,11],[9,12],[9,13],[9,14],[9,15]]
    [[10,11],[10,12],[10,13],[10,14],[10,15]]

    measurement 1 [1,2,3,4,5] false   
    measurement 2: [6,7,8] false    
    measurement 3: [9,10] false   
    measurement 4: [11]
    [[11,12],[11,13],[11,14],[11,15]]
    [[12,13],[12,14],[12,15],[13,14],[13,15],[14,15]]

Edit:

How can one check this? First of all you should check that these paragraphs are the node of a tree. Then you can check each paragraph by comparing each of the 105 pairs of balls [[1,2],...,[14,15]] with the measurements. Take the first pair [1,2] and the following paragraph

    measurement 1 [1,2,3,4,5] true   
    measurement 2: [4,5,6] false   
    measurement 3: [7,8,9,10,11] true   
    measurement 4: [1,7] true   
    measurement 5: [7,8]
    [[1,7],[1,8],[2,7],[3,7]]
    [[1,9],[1,10],[1,11]]

Measurement 3 must be true but this is wrong for this pair therefore it can be skipped. Take the pair [1,7]. Measurement 1,3,4,5 is true and measurement 2 is false, therefore it is in the last but one line. For the pair [1,9] again measurement 2 is false and measurement 1,3,4 is true, but measurement 5 is false, therefore it is in the last line. so all node of the tree can be checked. You can do these checks with a simple program (I used one written in maxima).

Edit: Maxima-Program

    f(n,ll_found,ll_notfound):=block(
        [
            remaining:[],
            passed
        ],
        for i:1 thru n do (
            for j:i+1 thru n do (
                passed:true,
                for s in ll_found do 
                    if not(member(i,s) or member(j,s)) then 
                        passed:false,
                for s in ll_notfound do 
                    if not(not member(i,s) and not member(j,s)) then 
                        passed:false,
                if passed then
                    remaining:endcons([i,j],remaining)
            )
        ),
        return(remaining)   
    );

    block([u,v],
    for i:1 thru 14 do (
        for j:i thru 15 do (
            u:length(f(15,[[1,2,3,4,5],makelist(k,k,i,j)],[])),
            v:length(f(15,[[1,2,3,4,5]],[makelist(k,k,i,j)])),
            if (u<=32 and v<=32) then print([i,j,u,v])
        )
    )
    );


    /* measurement 1: [1,2,3,4,5] */
    length(f(15,[[1,2,3,4,5]],[]));
    length(f(15,[],[[1,2,3,4,5]]));

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] */
    length(f(15,[[1,2,3,4,5],[4,5,6]],[]));
    length(f(15,[[1,2,3,4,5]],[[4,5,6]]));

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] true
       measurement 3: [1,2,7,8,9,10,11] */
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[])$length(%);
    f(15,[[1,2,3,4,5],[4,5,6]],[[1,2,7,8,9,10,11]])$length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] true
       measurement 3: [1,2,7,8,9,10,11] true 
       measurement 4: [1,2,7] */
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7]],[])$length(%);
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[[1,2,7]])$length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] true
       measurement 3: [1,2,7,8,9,10,11] true 
       measurement 4: [1,2,7] true
       fuenfte Messung: [1,6]
     und fertig, da trivial*/
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7],[1,6]],[]);length(%);
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11],[1,2,7]],[[1,6]]);length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] true
       measurement 3: [1,2,7,8,9,10,11] true 
       measurement 4: [1,2,7] false
       trivial da [4,5] * [8,9,10,11]*/
    f(15,[[1,2,3,4,5],[4,5,6],[1,2,7,8,9,10,11]],[[1,2,7]]);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] true
       measurement 3: [1,2,7,8,9,10,11] false 
       measurement 4: [12,13,14,15] 
       und trivial*/ 
    f(15,[[1,2,3,4,5],[4,5,6],[12,13,14,15]],[[1,2,7,8,9,10,11]]);length(%);
    f(15,[[1,2,3,4,5],[4,5,6]],[[1,2,7,8,9,10,11],[12,13,14,15]]);length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] false 
       measurement 3: [7,8,9,10,11] */
    f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6]])$length(%);
    f(15,[[1,2,3,4,5]],[[4,5,6],[7,8,9,10,11]])$length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] false 
       measurement 3: [7,8,9,10,11] true 
       measurement 4: ,[1,7] */
    f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7]],[[4,5,6]])$length(%);
    f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6],[1,7]])$length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] false 
       measurement 3: [7,8,9,10,11] true 
       measurement 4: ,[1,7] wahr 
       fuenfte Messung: [7,8] arbitrary
       trivial*/
    f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7],[7,8]],[[4,5,6]]);length(%);
    f(15,[[1,2,3,4,5],[7,8,9,10,11],[1,7]],[[4,5,6],[7,8]]);length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] false 
       measurement 3: [7,8,9,10,11] true 
       measurement 4: ,[1,7] false 
       trivial, da {2,3} * {8,9,10,11}*/ 
    f(15,[[1,2,3,4,5],[7,8,9,10,11]],[[4,5,6],[1,7]]);length(%);

    /* measurement 1 [1,2,3,4,5] true
       measurement 2: [4,5,6] false 
       measurement 3: [7,8,9,10,11] false
       measurement 4: [1,12] arbitrary
       trivial */
    f(15,[[1,2,3,4,5],[1,12]],[[4,5,6],[7,8,9,10,11]]);length(%);
    f(15,[[1,2,3,4,5]],[[4,5,6],[7,8,9,10,11],[1,12]]);length(%);

    /* measurement 1 [1,2,3,4,5] false
       measurement 2: [6,7,8]  */
    f(15,[[6,7,8]],[[1,2,3,4,5]])$length(%);
    f(15,[],[[1,2,3,4,5],[6,7,8]])$length(%);

    /* measurement 1 [1,2,3,4,5] false
       measurement 2: [6,7,8] true 
       measurement 3: [6] arbitrary
       trivial*/
    f(15,[[6,7,8],[6]],[[1,2,3,4,5]]);length(%);
    f(15,[[6,7,8]],[[1,2,3,4,5],[6]]);length(%);

    /* measurement 1 [1,2,3,4,5] false
       measurement 2: [6,7,8] false 
       measurement 3: [9,10] */
    f(15,[[9,10]],[[1,2,3,4,5],[6,7,8]]);length(%);
    f(15,[],[[1,2,3,4,5],[6,7,8],[9,10]]);length(%);

    /* measurement 1 [1,2,3,4,5] false
       measurement 2: [6,7,8] false 
       measurement 3: [9,10] true
       measurement 4: [9] arbitrary
       trivial */
    f(15,[[9,10],[9]],[[1,2,3,4,5],[6,7,8]]);length(%);
    f(15,[[9,10]],[[1,2,3,4,5],[6,7,8],[9]]);length(%);

    /* measurement 1 [1,2,3,4,5] false
       measurement 2: [6,7,8] false 
       measurement 3: [9,10] false
       measurement 4: [11] arbitrary 
       trivial */
    f(15,[[11]],[[1,2,3,4,5],[6,7,8],[9,10]]);length(%);
    f(15,[],[[1,2,3,4,5],[6,7,8],[9,10],[11]]);length(%);

Edit:

How did I derive the result? With trial and error. The following Lemma guides our trials


Lemma 1 (without proof): In every step of the algorithm the following is true: Let $S$ be the list of the remaining possible solution and $M$ be the list of balls to be measured and $n$ be the number of allowed measurements. Let $ T(S,M)$ be the list of all pairs of $S$ where at least one element of the pair is in $M$ and let $F(S,M)$ the list of all pairs of $S$ where no element of the pair is in $M$. Then the following is a necessary condition for an algorithm to solve all instances of the problem. $$\begin{align*} |S|&\leq 2^n\\ |T(S,M)|&\leq 2^{n-1}\\ |F(S,M)|&\leq 2^{n-1} \end{align*}$$


After this step the new S is $T(S,M)$ or $F(S,M)$ depending of the result of the measurement $M$. The new $n$ is $n-1$.

Finding two balls with at most k measuremants from n balls we call an (n,k)-problem. We want to find an algorithm for the (15,7)-problem.

The (15,7)-problem therefore $\binom{15}{2}=105$ possible solution pairs and therefore an algorithm to find such a pair must make at least 7 measurements in

the worstcase because $2^6<105<2^7$. We want to investigate the first measurement. Let's arange the list of all possible ball combination in the following

triangle manner

    [1,2] [1,3] [1,4] ... [1,14]  [1,15]         14 pairs    row  1
          [2,3] [2,4] ... [2,14]  [1,15]         13 pairs    row  2
                      .              .                .         .
                       .             .                .         .
                        .            .                .         .
                          [13,14] [13,15]         2 pairs    row 13
                                  [14,15]         1 pair     row 14

if the first measurement is made with the list $[1,\cdots,m]$ then $14+13+(15-m)<=2^6$ and $(15-(m+1))+...+2+1<=2^6$ must hold. $2^6=64$ therefore $m$ can

be $4$ or $5$. if $m=3$ and therefore $M=[1,2,3]$ then $|F(S,M)|=1+2+\cdots + 11=66>2^6=64$, if $k=6$ then $M=[1,2,3,4,5,6]$ and $|T(S,M)|=14+13+\cdots + 9 = 69 > 2^6=64$.

if for the first measurement $m=4$ and therefore $M=[15,14,13,12]$ and the result of the measurement is false then one must find with at most $6$

measurement the radioactive pair in the remaining $11$ balls. so we must save the (11,6)-problem.


Lemma 2: There is no algorithm for the (6,4)-problem.


Proof: If $M=[1]$ then $|F(S,M)|=4+3+2+1=10>8=2^3$. If $M=[1,2]$ then $|T(S,M)|=5+4=9>8=2^3$.


Lemmas 3: There is no algorithm for the (8,5) problem.


Proof: for the first measurement: $M=[1]$ or $M=[1,2,3]$ are not possible using the same arguments as in the (6,4) case. Therefore $M$ must be $[1,2]$. If the result of the measurement is false, the algorithm must solve the (6,4)-problem which is impossible by Lemma 2.


Lemma 4: There is no algorithm for the (11,6)-problem.


Proof: if $M=[1,2]$ then $|F(S,M)|=36>32=2^5$, if $M=[1,2,3,4]$ then $T(S,M)=34>32=2^5$. therefore $M$ must be $[1,2,3]$. Suppose that the first measurement is false 8 balls remains and our algorith must solve the (8,5)-problem wich is impossible by lemma 3.


From Lemma 4 an the reasoning before llemma 2 the following follows:


Lemma 5: If there is an algorithm for the (15,7)-problem its first measurement must measure a list of 5 balls.


We can assume that the first measurement is on the list [1,2,3,4,5]. The second measurement is on a list [x,x+1,...,y] that has zero, one or more elements

in common with [1,2,3,4,5]. First I tried [6,7,8,9,10,11] but had problems to proceed. Therefore I used my program to check each of the 105 N=[x,...,y] if $T(S,N)<=2^5=32$ and $F(S,N) <32$.

the following lists were found by the program [4,5,6]

[5,6,7,8,9]

[6,7,8,9,10,11]

the program also found the lists [7,...,12]

[8,...,13]

[9,...,14] [10,...,15] but these lists are basically the same as [6,...,11] after renaming the balls.

I continued with the list [4,5,6]. The remaining measurements I found by trial an error using my function and lemma 1. If one searches the third measuring after [1,2,3,4,5] and [4,5,6] one can use the fact that the numbers [1,2,3], [4,5], [7,8,9,10,11,12,13,14,15] are equivalent relative to [1,2,3,4,5] and [4,5,6]. this narrows down the cases to investigate.

share|improve this answer
    
Looks great, but how did you derive this? How does one check this? –  ShreevatsaR Jun 7 '11 at 12:37
    
thanks, I added a description how to check the result. currently i have no time to write how i derived this, i will try later to add this –  miracle173 Jun 7 '11 at 13:28
1  
If you used a program for this, why didn't you include the source code? –  Listing Jun 7 '11 at 13:39
1  
added the maxima program, additional remarks I will add later –  miracle173 Jun 7 '11 at 14:40
2  
Fantastic, both the result and the explanation! Thank you. –  Steven Stadnicki Jun 7 '11 at 21:31

This is similar to http://mathoverflow.net/questions/59939/identifying-poisoned-wines

It's not the same, but maybe close enough to derive some inspiration.

As noted at MO, it was here first: Logic problem: Identifying poisoned wines out of a sample, minimizing test subjects with constraints

share|improve this answer

Here's a generalization. Let $n(t)$ denote the maximum number of balls for which 2 radioactive ones can be identified in $t$ tests. miracle173 has effectively shown that $n(4) = 5$, $n(5) = 7$, $n(6) = 10$, and $n(7) \geq 15$.

In "Group testing with two and three defectives" (Annals of the New York Academy of Sciences 576, pp. 86-96, 1989) Chang, Hwang, and Weng give explicit testing procedures showing that $n(8) = 22$, $n(9) = 31$, $n(10) = 44$, and $n(11) = 63$. They also give explicit testing procedures that yield the lower bounds $$n(t) \geq 89 \cdot 2^{\frac{t}{2}-6}, t \text{ even, } t \geq 12;$$ $$n(t) \geq 63 \cdot 2^{\frac{t-1}{2}-5}, t \text{ odd, } t \geq 13.$$

(They take it as known that $n(7) = 15$. See also Chang, Hwang, and Lin, "Group testing with two defectives," Discrete Applied Mathematics 4 (2), pp. 97-102, 1982.)

In Combinatorial Group Testing and Its Applications, by Du and Hwang, it is shown that, for $t \geq 4$, we have the upper bound $$n(t) \leq 2^{\frac{t+1}{2}} - 1/2.$$

The upper and lower bounds imply, for example, that $n(12)$ is either 89 or 90.

This problem goes by the name "adaptive combinatorial group testing with two defectives." The Du and Hwang text appears to be the standard reference for these types of problems.

share|improve this answer
1  
Having learned about non-adaptive combinatorial group testing earlier today, now I also have an idea what "adaptive combinatorial group testing with two defectives" is about. Thanks, Mike! –  t.b. Jun 8 '11 at 22:49

Here is one solution :

1st measurement - ball N1 , N2 , N3 , N4 , N5 - 4+1 balls
2nd measurement - ball N1 , N6 , N7 , N8 , N9 - 4+1 balls

possible results :


Variant 1:

  • 1st measurement - negative
  • 2nd measurement - negative

    From this follow that the 2 radioactive are between the remaining 6(N10,11,12,13,14,15). We have 5 measurements to find 2 out of 6. We can split them on groups by 2 and we can measure each group...


Variant 2 :

  • 1st measurement - positive
  • 2nd measurement - negative

We are splitting remaining 6 in group of 4 and 2. And we are measuring them. Please note that we are measuring first the four group. If we get positive. We are splitting the group on 2 and we are measuring one of the groups, so we can get in which group of 2 , has radioactive ball.

  • Variant 2.1

    • 3rd measurement - negative
    • 4th measurement - negative

    From this follow that the 2 radioactive balls are in the first positive measurement group and we have 3 measurements left to find 2 balls out of 4...so it is easy

  • Variant 2.2

    • 3rd measurement - positive
    • 4th measurement - negative

    We are doing 1 more measurement to find which one is the radioactive of the remaining 2. And we have 2 measurements left to find 1 ball out of 4 in first measurement group.


Variant 3 :

  • 1st measurement - positive
  • 2nd measurement - positive

We are doing 3rd measurement ball N1 + rest -> ball N1 , N10 , N11 , N12 , N13 , N14, N15 - 6+1 balls

  • Variant 3.1

    • 3rd measurement is positive From this follow that ball N1 is radioactive. And we have 4 measurements left to find 1 radioactive ball out of remaining 14 balls. We are doing first 8 balls. If they are positive we are going 4/2/1 . If negative we are doing remaining 6. By first measuring 4... then 2 .. 1
  • Variant 3.2

    • 3rd measurement is negative.

      From this follow that we have one ball in first measurement group(4 balls/We know that N1 is not radioactive) and one ball in second group(also 4 balls). So we have 4 measurements left. 2 measurements left for first group and 2 for the second group. 4/2/1


It messed up the formating... but just follow the points and the logic...

share|improve this answer

IMHO, there is an easy way to explain this puzzle. Name the balls as: a,b,c, .., m,n,o. Split them into 4 groups, with 'a' being in both A&B.

    A=(a,b,c,d,e) B=(a,f,g,h,i) C=(j,k,l,m) D=(n,o)
Test A. Test B.
If both r neg, finish C,D in 5 more tests (Total=7)
If both r pos, test 'a'+C+D
If 'a'+C+D is pos, 'a' is 1st poison. Find the 2nd in (b-e,f-i,C+D) in 4 more tests (T=7)
If 'a'+C+D is neg, find 1st poison in (b-e), 2nd poison in (f-i) in 4 more tests (T=7)
If only A is pos, test C
If C is pos, find 1st poison in (b-e), 2nd poison in C in 4 more tests (T=7)
If C is neg, test D
If D is pos, find 1st poison in (b-e), 2nd poison in D in 3 more tests (T=7)
If D is neg, find 2 poisons in (b-e) in 3 more tests (T=7)


share|improve this answer

Here is a python program along the same lines @miracle173 specified.

It is generic and can handle any number of balls and any number of radioactive balls, and it outputs a nice decision tree.

Its 2 main optimizations are failing fast by taking the harder path first (the one with more possibilities), and permuting only on balls touched by previous selections, as the untouched balls are all symmetrical and we can simply pick the leftmost X.

It takes 20min on my machine for it to solve (15,7)

import itertools

def bin_to_str(m):
    return ("{0:0" + str(NUM_BALLS) + "b}").format(m)
def str_to_bin(n):
    return int(n,2)

def generate_all_possibilities(num_total, num_radio):
    ''' all possible permutations with specified length and number of radioacvite ''' 
    for indices in itertools.combinations(range(num_total), num_radio):
        item = ['0'] * (num_total)
        for index in indices:
            item[index] = '1'
        yield str_to_bin(''.join(item))

def do_the_radio(my_possibilities, my_attempts, touched):
    ''' find radioactive balls out of all my_possibilities, with specified my_attempts
        touched is a xor bitmask of previous selections'''
    if len(my_possibilities) == 0 or 2**my_attempts < len(my_possibilities): return [] # fail fast
    if len(my_possibilities) == 1:
        return "done"
    for selection in do_selection(touched):
        pos = [[],[]]
        res = [[],[]]
        for possibility in my_possibilities:
            if selection & possibility : pos[0].append(possibility) # beep
            else: pos[1].append(possibility) # no beep
        new_touched = touched ^ selection # xor all past selections to know which were touched 
        if len(pos[0]) > len(pos[1]): # fail fast by taking the hard path first
            hard_path, easy_path = 0, 1
        else: hard_path, easy_path = 1, 0
        res[hard_path] = do_the_radio(pos[hard_path], my_attempts - 1, new_touched)
        if len(res[hard_path]) > 0: 
            res[easy_path] = do_the_radio(pos[easy_path], my_attempts - 1, new_touched)
            if len(res[easy_path]) > 0:
                return [bin_to_str(selection), {'beep': res[0], 'no': res[1]}]
    return []

def do_selection(touched):
    ''' touched is a xor bitmask, with ones for balls that were touched by any previous selection.
    permute only on these touched balls, for the rest dont bother, just take leftmost 1..size(u)  '''
    t = [i for i, x in enumerate(bin_to_str(touched)) if x == "1"]
    u = [i for i, x in enumerate(bin_to_str(touched)) if x == "0"]
    for size_from_touched in range(len(t))+[0]:
        for indices in itertools.combinations(t, size_from_touched):
            item = ['0'] * NUM_BALLS
            for t_index in indices:
                item[t_index] = '1'
            for u_index in u:
                yield str_to_bin(''.join(item))
                item[u_index] = '1'

NUM_BALLS = 7
NUM_RADIO = 2
ATTEMPTS = 5

balls = list(generate_all_possibilities(NUM_BALLS, NUM_RADIO))
res = do_the_radio(balls, ATTEMPTS, 0)
print res 
share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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