Number Theory – Least Number of Weights Required to Weigh Integer Weights

Question

In a number theory book, I found the following problems,

"What is the least number of weights required to weigh any integral number of pounds up to 63 pounds if one is allowed to put weights in only one pan of a balance?"

and "Determine the least number of weights required to weigh any integral number of pounds up to 80 pounds if one is allowed to put weights in BOTH pans of a balance".

Now, I realize these are very simple questions, I know the answers, and I know that I can find similar questions here.
BUT THIS QUESTION IS NOT A DUPLICATE.

I know, its easily solved by using bases 2 and 3 to write the maximum weight to be measured. What I don't understand is why?
I must be overlooking a simple fact.
Could someone explain me the reasoning primarily?

Answer 1

Revised in response to comments.

Let’s look at the case in which you can put the weights on both pans. Suppose that you have weights $w_0,w_1,w_2,\ldots\,$, where $w_0<w_1<w_2<\ldots\;$. You want to weigh an $n$-pound object. Let’s say that the scales balance when you have $w_3$ and $w_0$ in one pan, and the object and $w_1$ in the other pan. This tells you that $$w_3+w_0=n+w_1\;,$$ i.e., that $$n=w_3-w_1+w_0\;.\tag{1}$$ In general you’ll find that you have some weights in the pan that does not contain the object being weighed (like $w_3$ and $w_0$ in the example), some weights that aren’t used (like $w_2$ and all $w_k$ with $k>3$ in the example), and possibly some in the same pan as the object being weighed (like $w_1$ in the example). The weight of the object is the sum of the weights in the opposite pan minus the sum of the weights in the same pan, just as in $(1)$.

More generally, say we’re weighing an $n$-pound object, and the heaviest weight that we use is $w_m$. Of course it will be in the pan opposite the object. Each of the lighter weights, $w_0,\ldots,w_{m-1}$, will either be in the same pan as $w_m$, in the same pan as the object, or not used at all. We can represent this as a string of plus signs for weights in pan opposite the object, minus signs for the weights in the pan with object, and zeros for the weights that aren’t used at all. In the little example above, for instance, $m=3$, and we can represent the way the weights $w_3,w_2,w_1$, and $w_0$ (in that order) are used by the string

                                      +0-+

This says that $w_3$ is opposite the object, $w_2$ isn’t used, $w_1$ is with the object, and $w_0$ is opposite the object. Alternatively, we could use the symbols $1$ for $+$ and $\bar1$ for $-$ and write $$10\bar11\;,$$ where $\bar1$ is supposed to suggest $-1$. This now looks a bit like a number written in some weird base.

We want each positive integer amount to be weighable, so we want each positive integer to have a representation in this odd system. What does that tell us about the weights that we need? We certainly need $w_0=1$. Do we need a $2$-pound weight? Not if we have a $3$-pound weight, because $2=3-1$. If $w_1=3$, we can weigh a $2$-pound object by putting $w_1$ in the other pan and $w_0$ in the same pan: $3=2+1$, or $2=3-1$. This gives us the shorthand representations +- and $1\bar1$. With these two weights we can get all of the following combinations with the heaviest weight opposite the object (and from now on I’ll stick with the $1,0,\bar1$ scheme): $1,1\bar1,10$, and $11$. They represent, respectively, the setups for weighing a $1$-pound, a $2$-pound, a $3$-pound, and a $4$-pound object. To go any higher, we’ll need $w_2$; what should it be?

If you play with different possibilities, you’ll find that taking $w_2$ to be $5,6,7$, or $8$ pounds is inefficient, because in every case there will be some object that can be weighed with more than one combination of weights. For instance, if $w_2=8$, we can weigh an $4$-pound object by balancing it and the $1$-pound and $3$-pound weights against $w_2$ as well as by balancing it against the $1$-pound and $3$-pound weights. You also won’t be able to weigh a $13$-pound object. You’ll also find that if $w_2>9$, you can’t weigh a $5$-pound object. If $w_2=9$, however, you can balance every weight from $1$ through $13$, and each of them in only one way:

$$\begin{array}{|c|c|c|}\hline 1&2&3&4&5&6&7&8&9&10&11&12&13\\ \hline 1&1\bar1&10&11&1\bar1\bar1&1\bar10&1\bar11&10\bar1&100&101&11\bar1&110&111\\ \hline \end{array}$$

Note that we can also weigh an object weighing $-8$ pounds, say. That sounds a bit weird, but imagine an object that pulls the pan upward with a force of $-8$ pounds: that’s a $(-8)$-pound object. How? Take the arrangement of weights that balances an $8$-pound object, and move each of the weights that you’re using to the other pan. Since an $8$-pound object is balanced by the arrangement $10\bar1$, a $(-8)$-pound object is balanced by the arrangement $\bar101$: with the object we have the $9$-pound weight, and opposite it we have the $9$-pound weight, so the two pans contain $(-8)+9$ and $1$ pounds, respectively, and do indeed balance. The same reasoning shows that by turning $1$s into $\bar1$s and vice versa we can weigh any object with an integral weight between $-13$ and $13$, inclusive.

Now suppose that we add $w_3=3^3=27$ to our weights. By putting it on the side not containing the object and combining it with the amounts from $-13$ to $13$ that we can weigh without it, we can balance every integral weight from $27-13=14$ through $27+13=40$. Moreover, by using it in the ‘wrong’ pan to balance $-27$ pounds, we can get everything from $-27-13=-40$ through $-27+13=-14$. Put all of that together, and you’ll see that with $1,3,9$, and $27$ we can balance everything from $-40$ to $40$, inclusive. (I recommend that you actually experiment with this, writing out at least a substantial part of the continuation to $40$ of the table above. That will give you a clearer picture of what’s going on here.)

Now suppose that with weights $1,3,3^2,\ldots,3^k$ we can weigh every integer amount from $-\frac12(3^{k+1}-1)$ through $\frac12(3^{k+1}-1)$, where the largest of these numbers is represented by the weighing $$\underbrace{11\ldots11}_{k+1\text{ ones}}$$ and the smallest by $$\underbrace{\bar1\bar1\ldots\bar1\bar1}_{k+1 \bar1\text{s}}\;.$$

Set $w_{k+1}=3^{k+1}$. By putting this new weight on the side not containing the object and combining it with every possible combination of the old weights, we can balance any integral weight from

$$3^{k+1}-\frac12(3^{k+1}-1)=\frac12(3^{k+1}-1)+1\tag{2}$$

through

$$3^{k+1}+\frac12(3^{k+1}-1)=\frac12(3^{k+2}-1)$$

pounds. Note that the lower bound in $(2)$ is exactly one pound more than the largest amount that we could weigh without the new weight $w_{k+1}$, so we can now weigh everything from $-\frac12(3^{k+1}-1)$ through $\frac12(3^{k+2}-1)$. Moreover, by putting the new weight in the pan with the object being weighed, so that it contributes $-3^{k+1}$ to the net weight on the other side of the balance, we can weigh everything from

$$-3^{k+1}-\frac12(3^{k+1}-1)=-\frac12(3^{k+2}-1)$$

through $$-3^{k+1}+\frac12(3^{k+1}-1)=-\frac12(3^{k+2}-1)-1\;.\tag{3}$$

The amount in $(3)$ is exactly one pound less than $-\frac12(3^{k+1}-1)$, the smallest (i.e., most negative) amount that we could balance without the new weight, so altogether we can now balance any integral weight between $-\frac12(3^{k+2}-1)$ and $\frac12(3^{k+2}-1)$, inclusive. Notice that we’re back where we started at the beginning of this highlighted section, except that instead of having weights $1,3,3^2,\ldots,3^k$ that can handle every integral weight from $-\frac12(3^{k+1}-1)$ through $\frac12(3^{k+1}-1)$, we have weights $1,3,3^2,\ldots,3^{k+1}$ that can handle every integral weight from $-\frac12(3^{k+2}-1)$ through $\frac12(3^{k+2}-1)$. We can repeat the argument with every $k$ replaced by $k+1$ (and hence every $k+1$ replaced by $(k+1)+1=k+2$, etc.) to conclude that if we add $w_{k+2}=3^{k+2}$ to our collection of weights, we’ll be able to handle every integral amount from $-\frac12(3^{k+3}-1)$ through $\frac12(3^{k+3}-1)$. Indeed, we can repeat it ad infinitum to see that if we have the full set of $3^k$-pound weights for $k=0,1,2,\ldots$, we can handle every integral weight, positive or negative (or zero). (Technically this is a proof by mathematical induction, but I’ve tried to avoid technicalities as much as possible.)

In case you’re wondering where the number $\frac12(3^{k+1}-1)$ came from in the first place, it’s from the formula for the sum of a finite geometric progression. The largest amount that we can balance with weights of $1,3,3^2,\ldots,3^k$ pounds is

$$1+3+3^2+\ldots+3^k=\frac{3^{k+1}-1}{3-1}=\frac12(3^{k+1}-1)\;.$$

If you think that this is looking an awful lot like some weird variant of ternary (base three) notation, you’re right: it is a base three system, but instead of using the digits $0,1$, and $2$, it uses the digits $-1$ (represented by $\bar1$), $0$, and $1$. It even has a name: it’s called the balanced ternary system of representing numbers, and Wikipedia has an extensive article on it. In some ways it’s very elegant. It has a very simple addition table, for instance:

$$\begin{array}{c|ccc} +&\bar1&0&1\\ \hline \bar1&\bar11&\bar1&0\\ 0&\bar1&0&1\\ 1&0&1&1\bar1 \end{array}$$

As we saw above, to get the negative of a number you just replace each $1$ by $\bar1$ and each $\bar1$ by $1$. This makes subtraction very easy: to calculate $a-b$, you just convert $b$ to $-b$ by changing $1$s to $\bar1$s and vice versa, and then add that to $a$ using the addition table above.

If you want to explore further, you can start with the Wikipedia article, and a search on ‘balanced ternary’ will turn up many web pages on the subject.

You can apply the same kind of analysis to the single-pan balance. If you do, you’ll find that in order to weigh each integral amount without gaps or overlaps, you need the weights to be powers of $2$ instead of powers of $3$. And if you use the same kind of scheme for representing weighings, with $1$ for weights that you use and $0$ for weights that you don’t use, you’ll get exactly the ordinary binary (base two) representations of the amounts that you’re weighing.