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