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,
and
, here are all possible configurations:
There are nine configurations, which shouldn’t surprise us. Two weights each in any of three places, is
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
weights is
We can therefore be certain then that two weights isn’t sufficient to measure 40 different weights of flour. Similarly, three weights would be
Thirteen weights would be insufficient to distinguish between 40 different inputs.
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
is the heaviest, running to
, the lightest. Such that
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,
.
The second heaviest weight we are asked to weigh is
, and the least we can take off is the smallest weight,
, therefore
Therefore
(subtract these two equations). Which then enables us to measure
by putting
on the minus-side.
Now we must measure
. The least we can do is replace
on the plus-side and remove
.
Therefore
. Which then enables us to measure
,
,
,
, and
. Recapping:
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
off lowers the total by 1kg; adding
to the negative side lowers the total by another 1kg. So, with
we can subtract 0, 1 or 2 from a given point (where
is “onâ€).
lets us subtract 0, 3 or 6 from a given point (where
is “onâ€). Combined
and
lets us subtract 0, 1, 2, 3, 4, 5, 6, 7, or 8 from a given point (where
and
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
:
Therefore
.
and
are both “on†so we know that we can subtract another 8 kg from
in sequence, taking us to:
Now we have to put X on the minus side, from there we know that
and
back on will give us the ability to do another 8 kg:
That only leaves us with the option of putting
,
and
back on, and taking
off, which we want to give us the next value,
Subtracting this from the initial equation,
:
So,
. Further,
,
,
and
are now known, so we can calculate that
.
We already know that we can position
,
and
to subtract up to 26, which is just what we need to get us to 1kg.
QED.
Now let’s go even more general. For
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:
We already know what
,
,
and
are, their derivation is utterly unchanged by the presence of
. We run out when we come to:
I know that it’s
as follows:
(eq1)
(eq2)
(eq1)-
(eq2)
As before, we put all
,
,
and
back on the plus side, and take
off, and that must be equal to our next integer weight:
As before, we subtract this from our initial equation,
:
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
th weight
, with
being the first weight, and
equal to one.
can be expressed as a function of the sum of all the previous weights:
So:
We should note that the maximum we can weigh with
weights is the sum of those
weights, or
Therefore,
We should also note that we can get rid of the summation, and simply define
in terms of
:
Substituting for
:
we have to define as 1 to match our
defined as 1.
We’re still defining each term in terms of the previous term, which we needn’t do. We’ve already got an equation for
:
This is the very first equation I gave, but adjusted for a start-from-zero
, instead of start-from-one,
. Substituting this into our equation for
:
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
. If we’d been really clever, we would have recognised this right from the start and just gone straight to the answer. Oh well.