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?

Lets start with a simpler problem of having only on radioactive coin.
The smallest set of coins that can be solved in one test is 2.
The smallest with two tests is 4.
The smallest with N tests is 2^N.

With two radioactive coins, test half of them.  If both end up in the same half you can keep halving the subset with them until they do end up split.  At some point they will end up in different groups.  At this point you end up with two separate problems with a single radioactive coin.

The worst case scenario is that they end up being split on the first test.  This leaves you with only 9 tests.  4 tests can find a single coin from a set of 16 and 5 tests can find a single coin from a set of 32.

You can find the coins from among a set of 48 with this scheme.

This seems wasteful because if the first weighing doesn't split the two coins up it will end up taking less than 10 weighings.

Posted by Jer on 2006-10-19 11:44:36