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?

(In reply to

Fibonacci Connection by Brian Smith)

My previous algorithm is not optimum. By replacing phi with specific constants I have come up with five potential optimum variations:

Let the four constants be k1, k2, k3, and k4 then the calculations are:

L = [k1*T], S = T-L

B = [k2*S], A = S-B

R = [k3*L], C = L-R

D = [k4*R], E = R-D

The square brackers represent rounding to the nearest integer.

Plan 1: {k1, k2, k3, k4} = {1/3, 1/3, 1/3, 1/2} This minimizes the largest of the three possible outcomes when a set of coins is tested in Stage 1 and Stage 2.

Plan 2: {k1, k2, k3, k4} = {1/2, 1/2, 1/2, 1/2} This maximizes the smallest of the three possible outcomes when a set of coins is tested in Stage 1 and Stage 2.

Plan 3: {k1, k2, k3, k4} = {2/5, 1/2, 1/3, 1/2} This tries to keep A=B=C=D=E, guaranteeing that Stage 3 splits into three equal parts.

Plan 4: {k1, k2, k3, k4} = {1/3, 2/5, 1/4, 1/2} This combines Plans 1 and 3 - minimizing the largest of the three possible outcomes when a set of coins is tested in Stage 1 and Stage 2 while guaranteeing that Stage 3 splits into three equal parts.

Plan 5: {k1, k2, k3, k4} = {1/2, 2-sqrt(2), sqrt(2)-1, 1/2} This combines Plans 2 and 3 - maximizing the smallest of the three possible outcomes when a set of coins is tested in Stage 1 and Stage 2 while guaranteeing that Stage 3 splits into three equal parts.

Plans 3, 4, and 5 look the most promising. They seem to agree with Joel's earlier speculation that S(n) = S(n-1)*sqrt(3) for large n. The worst case scenario (slowest reduction in search space) occurs when cycling between stages 2 and 3, which shows a reduction of a factor of 3 for two tests - effectively sqrt(3) per test. Explicitly writing S(n) = floor[S(n-1)*sqrt(3)] with S(2)=3 generates 3,5,8,13,22,38,65,112,193,... of which the terms S(3)-S(8) agree with Joel's earlier findings. This implies the ultimate answer is S(10)=193.

*Edited on ***February 14, 2016, 12:04 pm**