All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

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?

 No Solution Yet Submitted by David Shin Rating: 4.5000 (6 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 re: Fibonacci Connection | Comment 15 of 18 |
(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
 Posted by Brian Smith on 2016-02-14 12:00:22

 Search: Search body:
Forums (0)