You have N coins, 2 of which are radioactive. You have a radioactivity detector which can test any subset of the coins at a time, and return the number of radioactive coins in the group (i.e. it returns 0, 1 or 2). You have to find the radioactive coins, using not more than 10 tests. What is the largest N for which this is possible?

(In reply to thoughts by siddhesh)

Currently my answer is 108.

I essentially get a factor of 6 reduction out of 4 tests (rather than a factor of 4 out of 4 tests)

The critical part is how to handle the 1 coin in each of 2 piles case.

If I split pile 1 into 2 equal subpiles a,b and pile 2 into 3 equal subpiles c,d,e

test 1) a & c and 2) a & d
results:
00 -> coin in b & e
01 -> coin in b & d
02 can't happen
10 -> coin in b & c
11 -> coin in a & e
12 -> coin in a & d
20 can't happen
21 -> coin in a & c
22 can't happen

Thus, in two tests I split one pile in 3 the other in 2 rather than splitting both in 2.

Applying the x3 alternately to either side yields splitting both sides by 6 in four tests.

Thus, 8 tests will handle 36 on one side and 36 on the other.  I can't seem to do any better than a halving of one side with a single test so 9 tests will handle 72 on one side and 36 on the other.  The tenth test was the one that established the split so 108=36+72.

The next question is whether the other cases (which seem easier) work out.  If I get a 0 when testing 36 coins I can just test half of the remainging 72 to get:
36 coins with 8 tests left  (0 or 2)
36 in one pile and 36 in another with 8 tests left (already did that)

36 coins with 8 tests left : use similar method to get either
12,12 6 tests -> 2,2 2 tests left (test one for each pile)
or 12 with 6 tests -> 6,6 or 6 with 5 tests -> 1,1, extra test or now really easy.

Posted by Joel on 2006-10-17 22:32:55