This article is from the Puzzles FAQ, by Chris Cole firstname.lastname@example.org and Matthew Daly email@example.com with numerous contributions by others.
What is the smallest set of weights that allow you to weigh on a
balance scale every integer number of kilograms up to some number N?
Obviously (I hate this word! :-) any weight Y that can be weighed
by X1, X2, ... Xn can be written as:
Y = A1*X1 + A2*X2 + .... + An*Xn
where Ai is equal to -1, or 0, or 1.
b) UPPER BOUND FOR Y(n)
Each Ai can have one of three values, so the total number of
combinations of values for A1,A2, ... An is 3^n. At least one of these
combinations gives Y=0 (A1=A2=...=An=0). Out of the remaining 3^n-1
combinations, some give a negative Y (for example A1=A2=...=An=-1).
and some a positive Y (and some might also give zero values, e.g. if
X1=X2, and A1=1, A2=-1).
Because of symmetry it's easy to see that the combinations that give Y>0
are at most half i.e. (3^n-1)/2. It is also possible that different
combinations might give the same value of Y, and it is also possible
that these values of Y are not successive.
However, to obtain an upper bound, lets assume the best case i.e.
all (3^n-1)/2 combinations give different, positive, and successive
Y(n) <= (3^n-1)/2
c) AN OPTIMAL ALGORITHM FOR CHOOSING Xn
I will present an algorithm for choosing the weights X1,X2,...Xn.
Then we will prove that it is optimal.
For n=1, we choose X1=1, and of course Y(1) = 1.
Let's assume that we have already chosen n weights X1, X2 ... Xn,
and that we can weigh all Y where 1<=Y<=Y(n).
We are allowed to get an extra new weight Xn+1.
If we choose:
Xn+1 = 2*Y(n)+1
then we get
Y(n+1) = Y(n) + Xn+1 = 3*Y(n)+1
for 1<= Y <= Y(n):
use the weights X1...Xn (ignoring the new one)
for Y(n)+1 <= Y < Xn+1 = 2*Y(n)+1
Put Xn+1 on one side of the scale, and on the other side put
the unknown weight, and a combination of X1...Xn so that
this combination weighs "Xn+1 - Y" (which is a number
in the range 0...Y(n), so *there exists* such a combination)
for 2*Y(n)+1 <= Y <= 3*Y(n)+1:
put the unknown weight on one side, and on the other side
put Xn+1, and combination of X1...Xn with a weight equal to
"Y - Xn+1" (which again is a number in the range 0...Y(n),
so there exists such a combination)
So, to summarize, if we use such an algorithm, we have: X1 = 1; Y(1) =1; Xn+1 = 2*Y(n)+1 Y(n+1) = Y(n) + Xn+1 = 3*Y(n) + 1 It's easy to prove (e.g. by induction) that: Y(n) = (3^n-1)/2 X(n) = 3^n