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

Home > Logic > Weights and Scales
Radioactive Coins (Posted on 2006-10-17) Difficulty: 5 of 5
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.)
Solution Generalisation | Comment 13 of 20 |

Let N(R, T) = # of weighings neede to identify R radioactive coins from among a set of T coins.

If R=1 we begin by testing [T/2] coins. This reduces the search space to at most [(T+1)/2]. Hence

N(1,T) = 1 + N(1, [(T+1)/2])   so

N(1,T) = {log2T}

where {y} = smallest integer >= y

If R= 2 we also begin by testing [T/2) coins. If the test shows 1 radioactive in this pile then our further work will require N(1, [T/2]) + N(1,[(T+1)/2]) additional tests. If otoh the test comes up with zero or two coins, our further work will require up to N(2,[(T+1)/2]) additional tests, so that

N(2,T) = Max(1+ N(1,[T/2])+ N(1,[(T+1)/2]), 1+N(2,[(T+1)/2]))

N(2,T) = 2{log2T} - 1

We could repeat this induction like method to derive formulas for general R.

For our specific problem, the answer is 32 coins, as 9 tests suffice to identify the 2 radioactive coins within a group of 32 coins. 11 tests would be needed to detect to radioactive coins if the group size is 33.


  Posted by FrankM on 2008-02-03 11:20:29
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (8)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information