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