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?

Although I arrived at a solution, I cannot completely verify it as the calculations are pretty tedious to do on the resources I have (pencil and paper).  But, I do have an algorithm which is not just randomly trying out combinations.

The solution I arrive at is about N=183.  The upper bound is N=280 which should not be achievable based on arguments below.

First, some upper bound limits are calculated.  The first test of the coins is to divide them into 2 piles and test one pile.  If there is 1 radioactive coin detected then there is 1 coin in each pile.  If there are 2 coins detected then the number of tests needed is reduced because there are fewer number of combinations to test.  So, I will ignore this case because it doesn't affect the maximum number of coins which can be tested.  In other words, if the "1 coin in each pile case" can be handled then the "2 coins in 1 pile case" can definitely be handled.

Going back to the "1 coin in each pile case", there are n^2 possible combinations or "states" if there are n coins in each pile.  Now, the detector can discern 3^m states where m=the number of tests done.  Thus, for m=9 (since one test is used up already to determine the split of 1 coin in each pile), n=140 since n^2=3^9.  Thus, 2*140=280 coins is the maximum number of coins which can be handled if all the states are used.

However, the problem is that not all the states can be used (which I will show shortly).  This means that 280 coins is the upper limit. 

For solving the problem, I used a bottoms up approach.  Essentially, I started with the maximum number of coins which can be tested with 3 tests and used the results of 3 tests to determine the maximum number of coins which can be tested with 4 tests. This can be extended eventually to 9 tests.

It was shown already in previous posts that given 2 piles (1 coin in each pile) and 2 tests done, one can determine which 1 of 3 subpiles 1 coin belongs to, and which 1 of 2 piles the other coin belongs to.  I will abbreviate this case as 3:2 (which also has 3*2=6 states).  So, 2 tests can discern among 6 states.  Similarly, it was shown in previous posts that 3 tests can discern among 15 states (i.e. the 5:3 case).

I will show now that the 8:5 case (40 states) can be done in 4 tests.  I will denote this as a0...a7 sub-piles on one side and b0...b4 sub-piles on the other.  The first thing to do is test a0a1a2a3a4b0b1b2.  This will allocate 15 states into the "2 radioactive coins case", 19 states into the "1 radioactive coin case", and 6 states into the "0 radioactive coins state".  This is shown in my notation as 2-15s,1-19s,0-6s.

Now, the 15 states case is the same as the 5:3 case from the previous results.  So, I know this can be done in 3 more tests.

If the first test comes up 1 then one can perform the following test: a1a0a5a6a7b0b1.  This will further allocate the states into 2-6s, 1-7s, 0-6s.  This is almost the best that can be achieved since the states were divided into 3 almost equal parts.  The 6(3:2) states was shown earlier to require 2 tests. The "1-7s" result is the same as the one which shows up in the "5:3, 3 test case" after performing one test.  So, I know that "1-7s" requires 2 more tests.  Thus, one can see that the "1-19s" result from the 8:5 case can be done in 3 tests using the previous results of the 5:3, 3 test case.

Finally, I think it's obvious that the "0-6s" result can easily be done in 3 more tests.

Now, that the 8:5, 4 test case has been verified. I can use the results to determine a 5 test case maximum number of coins.  The algorithm is as follows:

1) estimate a maximum number of coins for the N test case(like 11:10 for the 5 test case)

2) Use the results from the "x:y, (N-1) test case" to put the same number of states x*y into the "2 radioactive coin case" (like create an 8:5 test to put 40 states into the "2 radioactive coins result" of the 5 test result).  This will force the 1 and 0 radioactive coins results to have a certain number of states. Example: 11:10, 5 tests yields "2-40s,1-55s,0-15s"

3) Find a test to divide the "1 radioactive coin result" into 3 roughly equal subpiles.  These subpiles should be about equal to the "1 radioactive coin result" from the "x:y, (N-1) test case". Use these previous results to show that the current result can be done in N tests.  Of course, you may have to derive new results if the subpiles yield a number of states less than the previous result's case.   Example: 11:10, "1 radioactive coin" result can be binned into "2-19s, 1-18s, 0-18s".  Now, the 19 states previous result can be used to show that 4 more tests are needed.  The 18 states case should be done in 4 tests since it is simpler than the 19 states case.

4) Start again with a new test from step one

Thus, here are the remaining results:

18:18, 6 tests: "2-110s,1-158s,0-56s"

31:31, 7 tests: "2-324s,1-455s,0-182s"

53:53, 8 tests: "2-961s,1-1364s,0-484s"

92:91, 9 tests: "2-2809s,1-4081s,0-1482s"

I have not verified that the method works for 7,8, and 9 tests as it is too much calculation for me to work out by hand right now (perhaps later).  But, I provided the results assuming it does work.

Note that this is approximate and could actually be just an upper bound if the method breaks down.  If the method works out then the result can actually be a little low.  But, it won't yield more than about 190-195 most likely (if it can be optimized).

Posted by gregg on 2006-10-24 23:04:56