Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.
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.
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.
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.
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
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.
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.
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:
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 :
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
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
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 :
We are doing 3rd measurement ball N1 + rest -> ball N1 , N10 , N11 , N12 , N13 , N14, N15 - 6+1 balls
Variant 3.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...
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+DIf '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 only A is pos, test C
If 'a'+C+D is neg, find 1st poison in (b-e), 2nd poison in (f-i) in 4 more tests (T=7)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 DIf 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)
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
