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.)
Not opimum: 48 | Comment 5 of 18 |

Lets start with a simpler problem of having only on radioactive coin.
The smallest set of coins that can be solved in one test is 2.
The smallest with two tests is 4.
The smallest with N tests is 2^N.

With two radioactive coins, test half of them.  If both end up in the same half you can keep halving the subset with them until they do end up split.  At some point they will end up in different groups.  At this point you end up with two separate problems with a single radioactive coin.

The worst case scenario is that they end up being split on the first test.  This leaves you with only 9 tests.  4 tests can find a single coin from a set of 16 and 5 tests can find a single coin from a set of 32.

You can find the coins from among a set of 48 with this scheme.

This seems wasteful because if the first weighing doesn't split the two coins up it will end up taking less than 10 weighings.


  Posted by Jer on 2006-10-19 11:44:36
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 (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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