An old general store had a 40-pounk stone that it used to weigh flour on a two-pan balance. Of course this worked fine only for people buying 40-pound quantities of flour. One day, the sales clerk dropped the stone as he lifted it from the scale and it broke into four pieces. The owner chewed out the young man, who promptly noted in his defense that 40-pound measures could also be weighed by placeing all four pieces on the scal. In fact, he noted that now other measures could also be weighed by using one, two, or threee of the stone pieces at one time. The owner decided that the clerk had a point and instructed him to have the stone pieces weighed carefully and then prepare a new sign indicating all the various weights of flour that could now be purchased. When the young man finished with his work, he reported that all whole number weights from 1 through 40 could now be sold. The owner was amazed and immediately asked for the weights fo the four pieces to see for himself if it was true. What are the weights of the four pieces?
What is the least number of weights that can be used to weigh items from 1 to N, the sum of 1 through N being a maximum.
It is well known that the powers of 2 can be used to represent every number from 1 on up. From 1, 2, 4, 8, 16, 32, etc., 1 - 1, 2 = 2, 3 = 4 - 1, 5 = 1 + 4, 6 = 2 + 4, 7 = 1 + 2 + 4, and so on. Therefore, weights of 1, 2, 4, 8, 16, 32, etc. can be used to balance any weight as long as the weights are only on one side of the balance scale.
It is similary well known that powers of 3 can be used to balance any weight from 1 on up by placing the weights on both sides of the scale.
To compare, consider various weights, "w", that can weigh all items from 1 to W. W1 is the maximum weight possible with the weights placed on one side of the scale. W2 is the maximum weight possible with the weights placed on both sides of the scale.
..Wts......................W(os).......W(bs)
..1 & 2.......................3
..1 & 3.......................................4
..1, 2 & 3...................6
..1, 2 & 4...................................7
..1, 2, 3 & 4..............10
..1, 3 & 4...................................8
..1, 3 & 5...................................9
..1, 3 & 6..................................10
..1, 3 & 7..................................11
..1, 3 & 8..................................12
..1, 3 & 9..................................13
..1, 3 & 10.................................--
..1, 2, 4, 8 & 16.........................31
..1, 3, 9 & 27............................40
Consider the three weights that add up to 13.
Do you see the patterns?
1 + 2 = 3
1 + 2 + 4 = 7
1 + 2 + 4 + 8 = 15
1 + 2 + 4 + 8 + 16 = 31
The weights form a geometric progression with 2 as the common factor. The sum of the sequence of weights is given by S = a(r^n - 1)/(r - 1) where a = the first term, r = the common factor and n = the number of terms. Therefore,
S(1+2) = 1(2^2 - 1)/1 = 3.
S(1+2+4) = 1(2^3 - 1)/1 = 7
S(1+2+4+8) = 1(2^4 - 1)/1 = 15
S(1+2+4+8+16) = 1(2^5 - 1)/1 = 31
Might there be a similar relationship for the weights that are distributed on both sides of the scale? 1, 3 and 9 are 3^0, 3^1 and 3^2. Might the next terms be 3^3 = 27, 3^4 = 81, etc.? Check it out.
Note that they also form a geometric progression with 3 as the common factor. Note also that the sum also equals S = a(r^n - 1)/(r - 1) where a = the first term, r = the common factor and n = the number of terms.
S(1+3) = 1(3^2 - 1)/2 = 4
S(1+3+9) = 1(3^3 - 1)/2 = 13
S(1+3+9+27) = 1(3^4 - 1)/2 = 40
S(1+3+9+27+81) = 1(3^5 - 1)/2 = 121
Lets look at the case of weights on both sides of the scale in a more general way. Might you be able to determine the required weights without recognizing the traditional pattern?
Assume that a + b = W.
If we are to be able to weigh all items from 1 through W, then b = W - 1. Subtracting from a + b = W yields a = 1 and b = W - 1. With only 2 weights, what must b and W be? If b = 2, you can weigh items weighing 1, 2 and 3 by placing the weights on one side only. If b = 3, you can weigh items weighing 1, 2, 3 and 4 by placing the weights on both sides of the scale. If b = 4, you cannot weigh an item weighing 2.
So, 1 and 3 are the least number of weights that be used to weigh items fro 1 through 4 units. The limit of 4 also derives from S = a(r^n - 1)/(r -1).
Assume that a + b + c = W.
Of necessity, b + c = W - 1.
Subtracting, a = 1.
By definition, from the previous assumption, b must equal 3.
Thus, 4 + c = W.
What value of c will result in the maximum number of weights that can be balanced?
c.....5....6....7....8....9....10
W....9..10...11..12..13....14 but an item weighing 5 units cannot be weighed.
Therefore, 13 is the maximum W possible with 3 weights making c = 9.
Note that 13 also derives from S = 1(3^3 - 1)/2.
Note also that the next weight in the series derives from c = 2(b) + 1 or, generally speaking, the next possible weight in an increasing set of weights derives from N = 2(n) + 1, n being the highest weight from the previous series of weights.
Given, a + b + c = 13.
b + c = 12
Subtracting, a = 1
Also, a + 11 = b + c, also making a = 1
By definition, b - a = 2 making b = 3
Thus, c = 9.
SInce we have definitely established the pattern, let
a + b + c + d = 1(3^4) - 1)/2 = 40.
b + c + d = 39
Therefore, a = 1
a + 38 = b + c + d = 39, also making a = 1
By definition, b - a = 2 making b = 3
SInce we have already established that c = 9, d must be 27.
By now, you might also have noticed that the weights themselves sre defined by N = 3^(n - 1), n being the number of weights.
