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?

If you take 1 from bag 1 and 2 from bag 2 etc., up through bag n, you will have 12(n^2+n)/2 grams on the scale. This shouldn't exceed 1500, so n^2+n shouldn't exceed 1500/6 or 250. Solving n^2+n-250 = 0, gives n=15.319..., so we could go up to bag 15 in one weighing. Or in 3 weighings we could go up to 45. Actually it comes out to 45.95..., but our method would be to do 15 bags in one weighing, anotehr 15 in a second weighing and another 15 in another.

But hold on. With 15 bags represented we use only 1440 grams. We have 60 left to play with. That would be enough to do two extra bags if done by itself (1+2 = 3 coints; 3x12=36 grams--which is within the 60). The trick though is to weigh two extra bags in each of the three weighings--not only that, but make it a different pair each time but make sure that each of the extras is in two of the weighings, so we need only include 2 extra coins in each weighing--one from each of 2 bags selected from bags 46,47 and 48. Now we still have 60-24=36 grams left to play with. Use it to include 1 from bag 49 and 2 from bag 50 on each of the weighings.

So in sum:
First weighing: 1 from bag 1 through 15 from bag 15, and 1 from bag 46, 1 from bag 47, 1 from 49 and 2 from 50.

Second weighing: 1 from bag 16 through 15 from bag 30, and 1 from bag 46, 1 from bag 48, 1 from 49 and 2 from 50.

Third weighing: 1 from bag 31 through 15 from bag 45, and 1 from bag 47, 1 from bag 48, 1 from 49 and 2 from 50.

If only one weighing comes out lighter than expected (lighter than 1500 grams), the bad bag is 15(w-1)+g, where w is the number of the weighing and g is the number of grams short.

If two weighings come out light, then the bad bag is the one that has representatives in the two bags involved. Weighings 1 and 2 mean bag 46; 1 and 3 mean 47; 2 and 3 mean 48.

That leaves the possibility that all three come out light. If each is light by 1 gram, it's bag 49; if each is 2 grams short, that makes it bag 50.

The answer is 50 bags.

Posted by Charlie on 2003-07-25 11:08:52