==> 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