This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.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?

logic/weighing/optimal.weights.s

a) EQUATION

-----------

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

values, so:

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

Proof:

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

So, Y(n) is equal to the upper bound we found before, so this algorithm is

optimal, and the weights you must choose are powers of 3.

Spyros Potamianos

potamian@hpl.hp.com

Continue to: