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(6): solution (plus one)--Still more by Brian Wainscott)
169
Divide the coins into piles A=71, B=71, C=27 coins. Set aside A. Take one coin each from B, two coins each from C, and weigh these. The total is either 1500 (in which case A is light), 1499 (B is light), or 1498 (C is light).
Suppose A is light (B is handled the same way). Create 5 piles a, b, c, d each with 16 bags, and e with 7. Set aside a, take 1 each from b, 2 each from c, 3 each from d, and 4 each from e. If the total weight is 1488, then a is light. If b is light the total is 1487, c gives 1486, d 1485, and e gives 1484.
Set e is easy: the 1,2,3,...,7 trick works fine. For the others, set aside one bag and use the 1,2,3,....,15 trick on the other 15. If the total is 1440 then the bag set aside is light.
If the original set C was light, it is easy. Since it only has 27 bags you can just do the 1,2,3 trick on half of them, then on the other half.
My best so far
