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

Home > Logic > Weights and Scales
One out of ninety (Posted on 2013-12-17) Difficulty: 3 of 5
You are presented with a set of 90 coins, appearing identical.
Actually, 89 of them are identical, but one has a different weight.
Using balance scales you have to find the odd coin,
paying $10 each time you use the scales.

What is the maximal (i.e. the worst case) cost to accomplish it?

See The Solution Submitted by Ady TZIDON    
Rating: 4.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Minimum of the minimum of the maximum | Comment 2 of 7 |
I realize that I could have been more assertive in my earlier post, using an information theory argument that was within my grasp.  Even if we knew whether the odd coin was heavier or lighter, we could not guarantee isolating it in 4 weighings for anything more than 81 coins.  This is because the balance scale only has 3 different results, so 4 weighings can at best distinguish among 3^4 = 81 things.  So 5 is a minimum lower bound of the minimum of the maximum cost across all methods. Given that is achievable, is is also the actual minimum of the minimum of the maximum across all methods.  

It is actually a little amazing to me that $50 (5 weighings) is sufficient for 90 coins, given that we do not know if the odd coin is lighter or heavier. 

  Posted by Steve Herman on 2013-12-17 16:27:22
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 (4)
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