Suppose you want to create a set of weights so that any object with an integer weight from 1 to 40 pounds can be balanced on a two-sided scale by placing a certain combination of these weights onto that scale.
What is the fewest number of weights you need, and what are their weights?
Answer
It turns out that you need four weights, measuring 1, 3, 9, and 27 pounds.
The trick here is that you can put weights on both sides of the scale. If you have an object of 2 pounds on the left side, you can place the 3-lb. weight on the right side and the 1-lb. weight on the left side for the scale to balance.
Similarly, if the object weighs 5 pounds, you put the 9-lb. weight on the right side and the 3-lb. and 1-lb. on the left side.
If you have a set of weights that can balance any weight from $1$ to $N$ pounds, then they can also balance any weight from $-1$ to $-N$ pounds just by switching the sides of the scale that you place them on. So the next weight you'd want to add would weigh $2N + 1$ pounds, and then you can balance any weight from $1$ to $3N + 1$ pounds on the scale.
So, starting with the 1-lb. weight, which can balance any weight from $1$ to $1$ pounds, we get $2(1) + 1 = 3$ pounds for the next weight, and they can balance anything up to $1 + 3 = 4$ pounds.
Then, for those two weights, we get $2(4) + 1 = 9$, and they can balance up to $1 + 3 + 9 = 13$ pounds.
And finally, for all three of those weights, we get $2(13) + 1 = 27$, and they can balance up to $1 + 3 + 9 + 27 = 40$ pounds, as required.
In general, to measure any weight up to $n$ pounds, you will need at least $\lceil\log_3(2n)\rceil$ weights due to the above formula.
No comments:
Post a Comment