Puzzle: find the minimum number of weights

Question

I came across this question: say given two weights 1 and 3, u can weigh 1,2 (by 3-1),3,4 (by 3+1) (using both sides of balance). Now find the minimum number of weights so that you can measure 1 to 1000.

So the answer was 1,3,9,27...

I want to know how do you arrive at such a solution means powers of 3. What is the thought process?

Source: http://classic-puzzles.blogspot.com/search/label/Google%20Interview%20Puzzles

Solution: http://classic-puzzles.blogspot.com/2006/12/solution-to-shopkeeper-problem.html

Answer 1

Theorem: You'll need weights 3^0 through 3^N to cover values 1 through S(N) = sum(3^i) for i = 0 to N.

Proof:

1. You've given the base case where N = 1.
2. Now assume this holds for N < M. For the case N = M we'll have weights 3^0=1 through 3^M which we already know covers values up to S(M-1). Consider that by trading sides for each weight on the scale we can express all negative values down to -S(M-1) with these same weights as well. This it will be sufficient to prove that we can express values S(M-1) + 1 through S(M) as 3^M + X where -S(M-1) <= X <= S(M-1). But S(M) = S(M-1) + 3^M so this is clear provided that S(M-1) + 1 >= 3^M - S(M-1). That is, if 3^M <= 1 + 2 * S(M-1) = 1 + sum(2 * 3^i) for i = 0 to M-1. This seems clear to me at the moment, but I've had a few cocktails and a proof wasn't really what you were asking for anyway, so I'll leave this final step as an exercise to the reader.
3. By induction, QED.

Answer 2

The next element in the series is the ((sum of all the previous numbers) * 2) + 1)

I think you just start at the base case 1, and work your way up. In order to hit the number 2 your choices are {2, 3, 4...} . 4 - 1 can't reach, 2 is redundant. After one more number the pattern emerges.

Answer 3

Here is how I had solved the problem. Say you have weights a_1, a_2, ..., a_r.

Now you can weight a weight x is you have

a_i1 + a_i2 + ... + a_ik = x + a_j1 + a_j2 + ... + a_jl

i.e x = Sum e_i * a_i

where e_i is either -1, 0 or 1.

i.e. we need to write each number as a linear combination of the a_i with coefficients 1,0 or -1.

Now we know that we can write any number in base 3 as a combination of powers of 3 with the coefficients(digits) 0,1,2.

A similar fact is that we can also use digits 1, 0 and -1 when we write a number in base 3!

The fact that we need to get all possible numbers leads to the fact that you might possibly be able to use powers of 3.

The puzzle is so constructed that it actually works out well and you can prove it easily.

The same idea can be applied to the similar problem where you have a spring balance (i.e just one pan). Here the coefficients are 0 and 1, and powers of 2 immediately spring to mind.

And another problem:

Suppose I said you had two copies of each weight and a common balance and had to weigh all weights from 1 to 61. Which weights would you choose?