You have N large bags of coins. All of the bags contain real 12 gram coins except for one, that one contains fake 11 gram coins.

To help you find the bag of fake coins, you have a digital scale which will give you the exact weight of any amount of coins up to 1500 grams. Any amount over 1500 grams will cause the scale to spit out a random value.

How many bags (N) can you have and still be able to tell which bag contains the fake coins if you can only use the scale three times?

(In reply to re(3): solution (plus one) by Brian Wainscott)

Start with 125 bags.

At the beginning, set aside 45 instead of just one. Split the remaining 84 into two groups A and B, with 45 in group A and 40 in group B. Again take one from each of A and two from each of B. The total weight should be 1500. If it is, one of the 45 you set aside is light, otherwise you can tell if one of group A or one of group B is light by whether the weighing is light by 1 or 2. In the case of A you also have 45 from which still to determine the fake; in the case of B, 40.

In either case, as before, split the 45 or 40 into 3 groups a,b,c. Again take 1 from each of a, 2 from each of b and 3 from each of c. There'll be at most 15 in each group, and again you can immediately determine which group is light. With 15 you can still use the 1,2,3,...,15 trick, and you are done.

Posted by Charlie on 2003-07-28 15:50:13