Least number of weights required to weigh integer weights

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?

Solutions Collecting From Web of "Least number of weights required to weigh integer weights"

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.

Let’s generalize the case where we are using only one pan. Say we have to weigh from 1 to n pounds(integer). We assume that a set of positive integral weights, A, exist so that we can combine them to accomplish our task. And we let |A|, the cardinality of A, be j. In other words we assume that j is the least number of weights required to weigh pounds up to n-pounds. We can combine those weights on one side of the pan in:
$
\begin{pmatrix}
j \\
1 \\
\end{pmatrix}
$ + $
\begin{pmatrix}
j \\
2 \\
\end{pmatrix}
$ +…+$
\begin{pmatrix}
j \\
j-2 \\
\end{pmatrix}
$+ $
\begin{pmatrix}
j \\
j-1 \\
\end{pmatrix}
$ +$
\begin{pmatrix}
j \\
j \\
\end{pmatrix}
$ ways. Where $
\begin{pmatrix}
j \\
1 \\
\end{pmatrix}
$ represents the number of ways of choosing 1 weight from j to place on one side of the pan.
Now, since there are n integers between 1 and n we want the total number of combinations to be n, in other for them to possibly weigh n different pounds. So we want $ n=
\begin{pmatrix}
j \\
1 \\
\end{pmatrix}
$ + $
\begin{pmatrix}
j \\
2 \\
\end{pmatrix}
$ +…+$
\begin{pmatrix}
j \\
j-2 \\
\end{pmatrix}
$+ $
\begin{pmatrix}
j \\
j-1 \\
\end{pmatrix}
$ +$
\begin{pmatrix}
j \\
j \\
\end{pmatrix}
$. We realize that the terms are the coefficients of $(1+1)^j$ (binomial expansion) minus the the first coefficient
$
\begin{pmatrix}
j \\
0 \\
\end{pmatrix}
$. So $ n=(1+1)^j-1=
\begin{pmatrix}
j \\
1 \\
\end{pmatrix}
$ + $
\begin{pmatrix}
j \\
2 \\
\end{pmatrix}
$ +…+$
\begin{pmatrix}
j \\
j-2 \\
\end{pmatrix}
$+ $
\begin{pmatrix}
j \\
j-1 \\
\end{pmatrix}
$ +$
\begin{pmatrix}
j \\
j \\
\end{pmatrix}
$. This now implies that $n=2^j-1$. We can easily find what j is by $log(n)=log(2^j-1)$. This implies $j=log(n+1)/log(2)$. So given any integer n, if $j=log(n+1)/log(2)$ generates an integer, then this is the least number of weights required for our task.
Now, how to find what those integers are: We know that for an integer(pound) n we need j weights. In order for j specific integers to work for n no two different possible combinations should yield the same number. Otherwise we do not cover the whole set of integers from 1 to n since j numbers can only generate n different combinations. And also the total sum of the weights should equal n since j integers might generate n integers while they are not all within [1,n]. The total sum is the maximum so the other combinations are between 1 and n. Now we know a formula for $n=2^j-1$. $n=2^j-1$=$2^{j-1}+2^{j-2}+…+2^0$. We see that the terms add up to n and there are j of them. So each term could potentially be a weight. How do we know that no two possible combination generates the same number? let A={$2^0$, $2^1$, …, $2^{j-1}$}, Another requirement is that no combination of the elements of A should yield a member of A. using the formula $2^j-1$=$2^{j-1}+2^{j-2}+…+2^0$, we see that a member of the set, A, cannot be generated by the sum of all the previous members (we think of A as ordered). And since the sum of any number of positive integers cannot generate a number less than the highest number in that sum we see that all the requirements are meant. I could be more rigorous here, but am tired. In any event, the same approach will work for the second part of the question. Remember the geometric progression.