7
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ goo.gl/VqbzP2 $\endgroup$ Nov 26, 2014 at 11:53
  • $\begingroup$ I think the reason $2$ and $3$ work so well relates to their proximity to $e$, but I'm not sure. EDIT: never mind $\endgroup$ Nov 26, 2014 at 12:08
  • $\begingroup$ @labbhattacharjee I don't think that just because we saw $63 = 2^n -1$, and $1+2+2^2 + .... +2^{n-1} = 2^n -1$, that we are using base 2 numbers. Otherwise, I do not understand what the book wants to say. $\endgroup$ Nov 26, 2014 at 12:29
  • $\begingroup$ @SwapnilRustagi Do you happen to remember which number theory book did you find this problem? also maybe what area of number theory is this question testing on? I found this question in an interview prep book, and I want to strengthen my understanding of number theory relating to this area $\endgroup$
    – Tianhe Xie
    Mar 4, 2021 at 20:44

2 Answers 2

7
$\begingroup$

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.

$\endgroup$
9
  • $\begingroup$ So what this means is that we can represent any integral weight in binary notation (base 2) and we only need to use a particular weight once or not at all. When we do the same with base 3 on one pan, to weigh 8 pounds, we would need 2 weights of 3 kg and 2 weights of 1 kg. And the number of weights will only increase if we go to a higher base. So base 2 is best for one pan. When we have two pans, weights on one of the pans can be thought of as negative, and so using base 3 becomes preferable over base 2. But what's the certainty that every integer can be written using 1bar, 1 and 0 in base 3? $\endgroup$ Nov 27, 2014 at 11:53
  • $\begingroup$ Every number can be written using 0, 1, 2 in base 3. Given a number written that way, you can add to it a number written using on 0 and 1, and get an answer written using only 0 and 1. So every number can be written as a difference of two 0, 1 numbers. That tells you what to put into the two scales. $\endgroup$ Nov 27, 2014 at 12:04
  • $\begingroup$ @Swapnil: I was deliberately avoiding getting very technical, but the argument is almost there in what I wrote. It's an easy proof by induction. If the powers of $3$ up through $3^k$ can represent $1$ through $\frac 12(3^{k+1}-1)$, to calculation in the answer shows that adding $3^{k+1}$ to…. the available powers let's us represent everything from $3^{k+1}$ down to $\frac 12(3^{k+1}+1)$ by subtraction $\endgroup$ Nov 27, 2014 at 12:57
  • $\begingroup$ Then by addition we get everything up to $3^{k+1}+\frac 12(3^{k+1}-1)=\frac 12(3^{k+2}-1)$. $\endgroup$ Nov 27, 2014 at 13:04
  • $\begingroup$ Probably my fault, but sorry I did not understand. $\endgroup$ Nov 27, 2014 at 13:11
0
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .