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 remaining1/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!/(342x)!) / (344!/(344x)!) 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!/(342x+1)!) / (344!/(344x)!). 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 informationtheoretically possible result.

Posted by Charlie
on 20061017 15:25:05 