You have a set of balance scales and some weights. You need to be able to measure every whole number weight from 1 to 40 kilograms of (say) flour. What is the smallest number of weights you need and what are their values?

The first trick is of course that you can put weights on either side, so you have to notice that you don’t necessarily need to be able to sum to every value, you can subtract as well. If we put the flour on the right hand side, then anything we put on the left adds to the balance, and anything we put on the right subtracts from the balance. For example, if we had two weights, 1kg and 3kg we could make.

- 1kg
- 3kg
- 1kg + 3kg = 4kg
- 1kg – 3kg = –2kg
- 3kg – 1kg = 2kg

Obviously the negative weight isn’t going to be useful to us, as we will never be called upon to weigh –2kg of flour.

So, each weight can be in one of three places:

- The same side as the flour
- Not the same side as the flour
- Not on the scale at all

We’ll call the side the flour is on the “minus-side” (since, from the point of view of the plus side, it effectively lowers the weight of the plus side) and the other side the “plus-side”.

We’ll start with two weights,

$Y$and

$Z$, here are all possible configurations:

- $0$
- $+Y\u20130$
- $+Z\u20130$
- $0\u2013Y$
- $0\u2013Z$
- $Y\u2013Z$
- $Z\u2013Y$
- $+Y+Z\u20130$
- $0\u2013Y\u2013Z$

There are nine configurations, which shouldn’t surprise us. Two weights each in any of three places, is

$3\times 3=9$

Let’s also recall that we can’t measure 0kg and we can’t measure negative weights of flour (since they cannot exist), therefore our equation for real combinations measurable with

$m$weights is

$N(m)=\frac{({3}^{m}\u20131)}{2}$

We can therefore be certain then that two weights isn’t sufficient to measure 40 different weights of flour. Similarly, three weights would be

$3\times 3\times 3=27$

$N(3)=\frac{(27\u20131)}{2}=13$

Thirteen weights would be insufficient to distinguish between 40 different inputs.

$3\times 3\times 3\times 3=81$

$N(4)=\frac{(81\u20131)}{2}=40$

Perfect! What we want is possible. Let’s list all the configurations of four weights (zero and negatives included). In the following table, “0” means not on the scales, “-” means on the same side as the flour and “+” means not on the same side as the flour (the eagle eyed amongst you will notice that this is simply a base–3 count):

```
W X Y Z W X Y Z W X Y Z
------------- ------------- -------------
+ + + + - + + + 0 + + +
+ + + - - + + - 0 + + -
+ + + 0 - + + 0 0 + + 0
+ + - + - + - + 0 + - +
+ + - - - + - - 0 + - -
+ + - 0 - + - 0 0 + - 0
+ + 0 + - + 0 + 0 + 0 +
+ + 0 - - + 0 - 0 + 0 -
+ + 0 0 - + 0 0 0 + 0 0
+ - + + - - + + 0 - + +
+ - + - - - + - 0 - + -
+ - + 0 - - + 0 0 - + 0
+ - - + - - - + 0 - - +
+ - - - - - - - 0 - - -
+ - - 0 - - - 0 0 - - 0
+ - 0 + - - 0 + 0 - 0 +
+ - 0 - - - 0 - 0 - 0 -
+ - 0 0 - - 0 0 0 - 0 0
+ 0 + + - 0 + + 0 0 + +
+ 0 + - - 0 + - 0 0 + -
+ 0 + 0 - 0 + 0 0 0 + 0
+ 0 - + - 0 - + 0 0 - +
+ 0 - - - 0 - - 0 0 - -
+ 0 - 0 - 0 - 0 0 0 - 0
+ 0 0 + - 0 0 + 0 0 0 +
+ 0 0 - - 0 0 - 0 0 0 -
+ 0 0 0 - 0 0 0 0 0 0 0
```

Let us (for our own convenience) assume that

$W$is the heaviest, running to

$Z$, the lightest. Such that

$W\ge X\ge Y\ge Z$

We know that the most we can put on one side is all the weights. Therefore all of our weights must add up to some maximum,

$N$.

$W+X+Y+Z=N$

The second heaviest weight we are asked to weigh is

$N\u20131$, and the least we can take off is the smallest weight,

$Z$, therefore

$W+X+Y=N\u20131$

Therefore

$Z=1$(subtract these two equations). Which then enables us to measure

$N\u20132$by putting

$Z$on the minus-side.

Now we must measure

$N\u20133$. The least we can do is replace

$Z$on the plus-side and remove

$Y$.

$W+X+Z=N\u20133$

Therefore

$Y=3$. Which then enables us to measure

$(N\u20134)$,

$(N\u20135)$,

$(N\u20136)$,

$(N\u20137)$, and

$(N\u20138)$. Recapping:

$W+X+Y+Z=N$

$W+X+Y+0=N\u20131$

$W+X+Y\u2013Z=N\u20132$

$W+X+0+Z=N\u20133$

$W+X+0+0=N\u20134$

$W+X+0\u2013Z=N\u20135$

$W+X\u2013Y+Z=N\u20136$

$W+X\u2013Y+0=N\u20137$

$W+X\u2013Y\u2013Z=N\u20138$

You should be able to see the pattern from the table evolving now. Each weight is either positive, off, or negative. Which means we get double duty from each one. Taking

$Z$off lowers the total by 1kg; adding

$Z$to the negative side lowers the total by another 1kg. So, with

$Z$we can subtract 0, 1 or 2 from a given point (where

$Z$is “on”).

$Y$lets us subtract 0, 3 or 6 from a given point (where

$Y$is “on”). Combined

$Z$and

$Y$lets us subtract 0, 1, 2, 3, 4, 5, 6, 7, or 8 from a given point (where

$Y$and

$Z$are “on”).

It’s now pretty simple to carry on. The next smallest change we can make is to remove the second heaviest weight; we want that to give us

$(N\u20139)$:

$W+0+Y+Z=N\u20139$

Therefore

$X=9$.

$Y$and

$Z$are both “on” so we know that we can subtract another 8 kg from

$(N\u20139)$in sequence, taking us to:

$W+0+Y+0=N\u201310$

$W+0+Y\u2013Z=N\u201311$

$W+0+0+Z=N\u201312$

$W+0+0+0=N\u201313$

$W+0+0\u2013Z=N\u201314$

$W+0\u2013Y+Z=N\u201315$

$W+0\u2013Y+0=N\u201316$

$W+0\u2013Y\u2013Z=N\u201317$

Now we have to put X on the minus side, from there we know that

$Y$and

$Z$back on will give us the ability to do another 8 kg:

$W\u2013X+Y+Z=N\u201318$

$\dots $

$W\u2013X\u2013Y\u2013Z=N\u201326$

That only leaves us with the option of putting

$X$,

$Y$and

$Z$back on, and taking

$W$off, which we want to give us the next value,

$N\u201327$$0+X+Y+Z=N\u201327$

Subtracting this from the initial equation,

$(W+X+Y+Z=N)$:

$W=N\u2013(N\u201327)$

$=27$

So,

$W=27$. Further,

$W$,

$X$,

$Y$and

$Z$are now known, so we can calculate that

$N=40$.

We already know that we can position

$X$,

$Y$and

$Z$to subtract up to 26, which is just what we need to get us to 1kg.

$N=40$

$W=27$

$X=9$

$Y=3$

$Z=1$

QED.

Now let’s go even more general. For

$n$weights, what is the maximum weight of flour we can weigh? What weights do we need?

We’ll plough through this a little faster, first let’s add an additional weight:

$V+W+X+Y+Z=N$

We already know what

$W$,

$X$,

$Y$and

$Z$are, their derivation is utterly unchanged by the presence of

$V$. We run out when we come to:

$V\u2013W\u2013X\u2013Y\u2013Z=N\u201380$

I know that it’s

$N\u201380$as follows:

$V+W+X+Y+Z=N$

(eq1)

$W+X+Y+Z=40$(eq2)

$V\u2013W\u2013X\u2013Y\u2013Z=N\u201380$(eq1)-

$2\times $(eq2)

As before, we put all

$W$,

$X$,

$Y$and

$Z$back on the plus side, and take

$V$off, and that must be equal to our next integer weight:

$0+W+X+Y+Z=N\u201381$

As before, we subtract this from our initial equation,

$V+W+X+Y+Z=N$:

$V+W\u2013W+X\u2013X+Y\u2013Y+Z\u2013Z=N\u2013(N\u201381)$

$V=81$

We shouldn’t be surprised; as we said, each weight can be used twice, once when we take it off the plus side, and once when we add it to the minus side. Therefore, the nth weight is the sum of all the previous weights multiplied by two, plus one to get us to the next unknown.

Now we’ll label the

$n$th weight

$W(n)$, with

$n=0$being the first weight, and

$W(0)$equal to one.

$W(n)$can be expressed as a function of the sum of all the previous weights:

$W(n)=\left(\sum _{i=0}^{n\u20131}W(i)\right)\times 2+1$

So:

$W(0)=1$

$W(1)=W(0)\times 2+1=3$

$W(2)=(W(0)+W(1))\times 2+1=9$

$W(3)=(W(0)+W(1)+W(2))\times 2+1=27$

$W(4)=(W(0)+W(1)+W(2)+W(3))\times 2+1=81$

We should note that the maximum we can weigh with

$n$weights is the sum of those

$n$weights, or

$N(n)=\sum _{i=0}^{n}W(i)$

Therefore,

$W(n)=N(n\u20131)\times 2+1$

We should also note that we can get rid of the summation, and simply define

$N(n)$in terms of

$N(n\u20131)$:

$N(n)=N(n\u20131)+W(n)$

Substituting for

$W(n)$:

$N(n)=N(n\u20131)+(N(n\u20131)\times 2+1)$

$=3N(n\u20131)+1$

$N(0)$

we have to define as 1 to match our

$W(0)$defined as 1.

$N(n)=1,4,13,40,121,364,\dots $

$W(n)=1,3,9,27,81,243,729,\dots $

We’re still defining each term in terms of the previous term, which we needn’t do. We’ve already got an equation for

$N(n)$:

$N(n)=\frac{({3}^{n+1}\u20131)}{2}$

This is the very first equation I gave, but adjusted for a start-from-zero

$n$, instead of start-from-one,

$m$. Substituting this into our equation for

$W$:

$W(n)=(\frac{{3}^{n\u20131+1}\u20131}{2})\times 2+1$

$={3}^{n}$

This shouldn’t be a surprise to us really. The weights are a base–3 counting system, for any base, the nth digit’s multiplier is given by

${B}^{n}$. If we’d been really clever, we would have recognised this right from the start and just gone straight to the answer. Oh well.