Puzzle: find the minimum number of weights

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开发者_C百科 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

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?

Consider the problem at a basic level:

If you wanted to find the minimum weights for 20kg,

Initially: 20 = 1+1+1+1+1+1....(20 times). Using binary you could break it down to half by using only the odd weights.

  => 1, 2, 4, 6, 8, 10...20 (for all odd weights even no.s can be "added" by 1)
      ... 2+1, 4+1, 6+1...18+1.

Now, if "subtraction" also is considered, i.e. both the pans are being used, then we can take multiples of 3.

1     3        6        9       12        15        18        21        24        27

   2     4  5     7  8    10  11    13 14     16 17     19 20     22 23     25 26

       _________________  _________________  __________________  ___________________

We see all weights can be produced thus by adding and subtracting 1 to the multiple of 3's

IMP: 1 was the basic unit above

Next we can make 3 the basic unit of addition and subtraction, as it can deduce all other numbers. Hence,consider the sets, 3-6-9, 9-12-15, 16-17-18 etc can be taken and the middle terms can be eliminated as.

Thus we have,

1     3                9                    15                   21                 27

   2     4  5  6  7  8    10  11  12  13 14     16 17  18  19 20     22 23 24 25 26

                          _________________    __________________  __________________

Now 9 is our basic unit, as we can access any number from 1 through 9,directly. If we add or subtract , we get a gap of 18. Thus, we have the middle terms eliminated:

1     3                9                                                           27

   2     4  5  6  7  8   10  11  12  13 14  15  16 17  18  19 20  21 22 23 24 25 26

                          _________________________________________________________

Now, every number from 1 through 27 can be deduced. Hence 27 becomes our basic unit and the next gap that can be accessible will involve addition and subtraction of 27, giving 54.

Thus we can conclude that powers of 3 are being repeated as the difference between powers of 3 is always 3(n).

Hence proved.

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.

Assume you have a set of weights using which you can weigh any number up to n. Now you want to expand your set of weights to weight more numbers which means you want to weigh n+1, n+2 and so on. Adding weights n+1, n+2,....,2n would be redundant. The next weight in the series should be the ((sum of all the previous weights) * 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.