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.)
Some Thoughts information theory vs. practicalities | Comment 2 of 18 |

Ten uses of the detector can have 3^10 sets of outcomes, since there are 3 possibilities for each measurement.  That's 59049.  The number of possibilities for which two of the coins are radioactive is C(n,2). C(344,2) = 58,996, but C(345,2) = 59,340.  Therefore it's theoretically possible that a method could be devised to test 344 coins, but no more than that.

The difficulty lies in actually devising such a plan. Ideally, each measurement should have equal likelihood (cover an equal number of possibilities) of any of the three measurements: 0, 1 or 2 radioactive coins; that is, each result leaves the same number of possibilities still remaining--1/3 of the possibilities left at the preceding step.

If you chose a sample of size x from among the 344 coins, there'd be a probability of (342!/(342-x)!) / (344!/(344-x)!) of getting a zero reading. The following choices for testing result in probabilities of about 1/3 of getting a zero reading:

143                    .3407010644789477
144                    .3373110041358736
145                    .3339378940945149
146                    .3305817343548715

The probability of the reading being 1 is 2*x*(342!/(342-x+1)!) / (344!/(344-x)!). For the numbers being tested shown above, this comes out to:

143                    .4872025222048952
144                    .4881686894026714
145                    .4891009559970168
146                    .4899993219879314

none of which is also close to 1/3.

So it looks impossible to divide into equally likely thirds by means of the detector readings, and therefore impossible to get the information-theoretically possible result.


  Posted by Charlie on 2006-10-17 15:25:05
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 (0)
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