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?

Ten uses of the detector can have 3^10 sets of outcomes, since there are 3 possibilities for each measurement.  That's 59049.  The number of possibilities for which two of the coins are radioactive is C(n,2). C(344,2) = 58,996, but C(345,2) = 59,340.  Therefore it's theoretically possible that a method could be devised to test 344 coins, but no more than that.

The difficulty lies in actually devising such a plan. Ideally, each measurement should have equal likelihood (cover an equal number of possibilities) of any of the three measurements: 0, 1 or 2 radioactive coins; that is, each result leaves the same number of possibilities still remaining--1/3 of the possibilities left at the preceding step.

If you chose a sample of size x from among the 344 coins, there'd be a probability of (342!/(342-x)!) / (344!/(344-x)!) of getting a zero reading. The following choices for testing result in probabilities of about 1/3 of getting a zero reading:

143                    .3407010644789477
144                    .3373110041358736
145                    .3339378940945149
146                    .3305817343548715

The probability of the reading being 1 is 2*x*(342!/(342-x+1)!) / (344!/(344-x)!). For the numbers being tested shown above, this comes out to:

143                    .4872025222048952
144                    .4881686894026714
145                    .4891009559970168
146                    .4899993219879314

none of which is also close to 1/3.

So it looks impossible to divide into equally likely thirds by means of the detector readings, and therefore impossible to get the information-theoretically possible result.

Posted by Charlie on 2006-10-17 15:25:05