Search code examples
puzzle

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

Solution

  • 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.