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?
For a low number of coins it looked like the Fibonacci sequence was the solution. (N=2,3,5,8,13 for tests=1,2,3,4,5) I have an algorithm based off of that notion. It guarantees a lower bound of N = kth Fibonacci number for k tests, specifically k=10 means that at least N=144 can be resolved within 10 tests.
This algorithm is recursive with three stages and works for any amount of coins >= 5. When the number of coins falls below 5, then those cases are small enough to handle manually.
Let phi be the constant (sqrt(5)-1)/2 = 0.6180339887. Let [x] denote rounding to the nearest integer. Ex: [1.4999]=1 and [1.50]=2
Note that if X is a Fibonacci number greater than 1, then[phi*X] is the preceding Fibonacci number, and subsequently X-[phi*X] is the second preceding Fibonacci number.
Stage 1: One pile of T coins has both radioactive coins
Let L=[phi*T], S = T-L
Test set S
If the result is 0, then goto Stage 1 with set L
If the result is 2, then goto Stage 1 with set S
If the result is 1, then goto Stage 2 with sets {S,L}
Stage 2: Two piles of coins, {S and L}, each have one radioactive coin
Let B=[phi*S], A = S-B, R = [phi*L], C=L-R
Test the union A+C
If the result is 0, then goto Stage 2 with sets {B,R}
If the result is 2, then goto Stage 2 with sets {A,C}
If the result is 1, then goto Stage 3 with sets {A,B,C,R}
Stage 3: Four piles of coins, {A, B, C, and R}, such that either B and C each have one radioactive coin or A and R each have one radioactive coin.
Let D=[phi*R], E=R-D
Test the union A+D
If the result is 0, then goto Stage 2 with sets {B,C}
If the result is 2, then goto Stage 2 with sets {A,D}
If the result is 1, then goto Stage 2 with sets {A,E}
Fibonacci Connection
