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.
On
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.
On
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.
On
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.
On
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.
On
This is similar to https://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
On
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.
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.