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 (3⁷>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?

(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