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