(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