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 re: New high - Marvelous by Leming)

I really have to stop working on this, but it looks to me like the final answer will actually be around 200.

I spent quite a while on a computerized solver than has run out of steam at 8 tests.

Here is the higest I can get for each number of tests:

2 : 3     (test 1)
3 : 5     (test 2)
4 : 8     (test 3)
5 : 13   (test 6)
6 : 22   (test 11)
7 : 38   (test 19)

This immediately gives a new lower bound of 152 using the tests for 3,5 and 19,19.  However, it appears to me that an asymptotically optimal S(n) = about sqrt(3)S(n-1) is being reached which would put S(10) at somewhere just short of 200.  I don't see a nice explanation, but I might be able to get program to at least provide a solution breakdown for what it can find.

Anyway, I really do have to give up.

Posted by Joel on 2006-10-20 13:24:22