[Math] how to find the balls

puzzle

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.

Best 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.

Related Question