lotus

previous page: 359 logic/weighing/gummy.bears.p
  
page up: Puzzles FAQ
  
next page: 361 logic/weighing/weighings.p

360 logic/weighing/optimal.weights.p




Description

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.

360 logic/weighing/optimal.weights.p


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:













TOP
previous page: 359 logic/weighing/gummy.bears.p
  
page up: Puzzles FAQ
  
next page: 361 logic/weighing/weighings.p