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 2008-02-03 11:20:29