YoursFalsey wrote:Since this topic has been quiet for a few days, a new puzzle.
Jerrod the Jeweler is going into a new sideline of assaying ore samples. He intends to weigh ore samples with an old fashioned balance scale, placing the samples on one side and his weights on the other side until a balance is achieved. If he wishes to be able to balance all possible samples with an integral weight in grams between 1 and 1000, what is the smallest number of weights he will need?
(Oh, this isn't school, so a stringently rigorous proof isn't necessary, but by the same token, give some explanation so we can follow your answer...)
Nine weights covering gram weights of 1, 2, 4, 8, 16, 32, 64, 128, 256, and 512 should suffice. In fact, these weights would cover all integral weights in grams up to and including 1023. The weights used to balance a sample correspond to the "1" digits in a binary number system representation of the weight in grams.
Any set of weights in effect represents the weight of the sample in some number system or other. A straightforward set of decimal weights could include 1 through 9 by 1's, 10 through 90 by 10's, 100 through 900 by 100's, and a single 1000 gram weight, for a total of 28 different weights. This could be reduced in each range by using a 5, a 2 and two 1's (times each appropriate power of ten), but that still adds up to 13 different weights.
Looking at it from the other end, so to speak, if I have a single 1g weight, I can exactly weigh just one sample. If I add the 2g weight, I can now weigh 1, 2, or 3 gram samples. Add the 4g weight and my limit goes to 7g. In general, if I have all the power-of-2 weights up to 2-to-the-n, I can weigh all samples up to one less 2-to-the-n-plus-one. Each additional weight approximately doubles the number of sample weights that can be balanced, and I don't think that can be improved upon.
