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.)
 Fibonacci Connection | Comment 14 of 18 |
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}

 Posted by Brian Smith on 2016-02-10 12:11:57

 Search: Search body:
Forums (0)