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?
Let N(R, T) = # of weighings neede to identify R radioactive coins from among a set of T coins.
If R=1 we begin by testing [T/2] coins. This reduces the search space to at most [(T+1)/2]. Hence
N(1,T) = 1 + N(1, [(T+1)/2]) so
N(1,T) = {log2T}
where {y} = smallest integer >= y
If R= 2 we also begin by testing [T/2) coins. If the test shows 1 radioactive in this pile then our further work will require N(1, [T/2]) + N(1,[(T+1)/2]) additional tests. If otoh the test comes up with zero or two coins, our further work will require up to N(2,[(T+1)/2]) additional tests, so that
N(2,T) = Max(1+ N(1,[T/2])+ N(1,[(T+1)/2]), 1+N(2,[(T+1)/2]))
N(2,T) = 2{log2T}  1
We could repeat this induction like method to derive formulas for general R.
For our specific problem, the answer is 32 coins, as 9 tests suffice to identify the 2 radioactive coins within a group of 32 coins. 11 tests would be needed to detect to radioactive coins if the group size is 33.

Posted by FrankM
on 20080203 11:20:29 