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

Home > Logic > Weights and Scales
Ninety nine coins plus one catch (Posted on 2014-06-01) Difficulty: 3 of 5
You are given a task of locating one faulty coin out of 99 identical in appearance coins i.e. 98 of equal weight and one of a lesser weight; and to achieve it within seven weighings, using a balance scale.

Sounds familiar and easy (37>99)?

Familiar? Yes.

Easy? Not quite!

How can you accomplish it if no coin may be weighed more than twice ?

Bonus task: After devising the requested procedure please generalize:
How many coins (n-1 normal and one lighter) can be resolved within k weighings?

No Solution Yet Submitted by Ady TZIDON    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution Solution, explained | Comment 6 of 7 |
(In reply to re(3): Any thoughts on this one? small hint - open to all by Ady TZIDON)

Ah, thanks Ady!  It's obvious now, very well done.

So you start with 97 coins.  Take two piles of 13 and weigh them against each other. 

If one is lighter than the other, then you know the fake coin is in that pile.  You now have 6 weighings to find it among the 13, so select pairs and weigh one against another until you find one that's lighter.  If you go through the 6 weighings and don't find it among the 12 coins you weighed, then the fake coin must be the 13th.

If, on the other hand, the two piles of 13 coins are the same weight, then you know the fake coin is among the remaining 97 - 2*13 = 71 coins.  This time choose two piles of 11 coins instead of 13.  If one of the piles is lighter than the other, use the five remaining weighings to find the fake coin just as above.

If the two piles of 11 coins are the same weight, then you know the fake coin is among the remaining 71 - 2*11 = 49 coins.  This time, choose two piles of 9 coins. 

Continue this process.  You'll eventually find the fake, because:

97 = 13 + 13 + 71

71 = 11 + 11 + 49

49 = 9 + 9 + 31

31 = 7 + 7 + 17

17 = 5 + 5 + 7

7 = 3 + 3 + 1

If after all of these weighings you don't find the fake then there will be only one left, which must be the counterfeit coin. 


  Posted by tomarken on 2014-07-02 12:57:46
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 (3)
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