4
$\begingroup$

Find four weights such that given four weights and weighing pan (balance scale) you can measure all weights between $1$ to $80$.

I found this one here.Any idea how to solve?

  • 0
    The problem requires some clarification. It's sometimes asked how 4 weights can be used to measure all weights between 1 to 40. The intended meaning there is that each of these must be achievable as the difference between the sums of weights on the two scales. With that meaning of "measure", it's impossible to do the same for 1 to 80. I think the question means: Find 4 weights such that if you know that what you're measuring is an integer between 1 and 80 you can always infer the given weight. Brute search reveals that in addition to the guessable answer there's a slightly different one, too.2011-02-08
  • 0
    That alternative answer is actually a consequence of the problem not being posed economically -- the guessable answer allows you to infer the weight if you know it's between 1 and *81*, whereas the modified answer only works up to 80.2011-02-08
  • 0
    ... is your "alternative answer" just "the regular answer with the heaviest weight reduced by 1"? If so, I spent far too long wondering about that...2011-02-08
  • 0
    @Rawling: It is, yes -- sorry about that! I did say it was "slightly different" :-)2011-02-08
  • 0
    Use the integer closest to $e=2.718...$ as a base, and hence as suggested use $3$.2011-02-08
  • 0
    @Eric Naslund: Not sure whether that was a humorous remark? :-) That's the optimal base for FFT -- are you saying a similar argument applies here? I think 3 is the exact optimal base for this case, determined by the fact that there are 3 different things we can do with a weight, corresponding to changing the balance by +1, 0 or -1 times its weight.2011-02-08

2 Answers 2

5

Try using base 3 to express weights in that range.

  • 0
    Hm, brute-forcing got me the answer quite quickly (once I figured out the trick) but this has me trying to figure out *why* the given values work.2011-02-08
  • 1
    The numbers between 1 to 80 take 4 digits to express in base 3, since $3^4$=81$.2011-02-08
  • 0
    Yeah, I figured that much out. Just trying to figure out (without giving it away) why those 4 particular numbers work.2011-02-08
  • 0
    @Rawling: Go back to the formulation of make it balance and 1 to 40 lb. Express the weight in base 3. You have three possibilities for each weight: two pans and off, so can show it works.2011-02-08
  • 0
    Yeah... I was trying to come up with an obvious rule to go from the trinary representation of the weight to the +1/0/-1 combination of weights. (i.e. "Input starts with a 1? Add a +1 to the output, remove the 1 from the input, increment each digit of the input mod 3" or somethng.) I haven't managed that, but have at least convinced myself why it works.2011-02-08
  • 0
    ... and bang, got the rule as well.2011-02-08
3

OK, I'll write an answer since I have a bit more to say than will fit into comments. I won't give away the answer though; if you want it given away, please indicate that.

Please see my comments above regarding the problem formulation.

So we have two different problems, one where "measure" means "balance" and we want to be able to balance the weights from 1 to 40, and one where "measure" means "infer", and we want to be able to infer the weights from 1 to 81. (80 in the original question, but 81 makes more sense). Let's first think why we can't do better than 1 to 40 when "measure" means "balance". We have 81 different combinations of weights available, as we can choose $+$, $-$ or $0$ for each weight, corresponding to putting it on the one scale, the other scale or neither scale. There is a symmetry in that reversing the signs of a combination reverses the sign of the weight we can balance, which gives us nothing new since it just means we have to put the weight to be balanced on the other scale. So we don't actually have 81 different values, but one zero value and $2\times 40$ paired positive/negative values, i.e. 40 useful values. That's why we can't do better than 1 to 40 if "measure" means "balance".

Now if "measure" means "infer", we don't have to be able to balance each weight. In fact, what we need is to be able to balance precisely every other weight, since two consecutive weights that we can't balance can't be distinguished. And 81 is the greatest number such that we can balance 40 numbers and not leave any consecutive weights unbalanced, namely by balancing all even numbers from 2 to 80. Thats' why we can't do better than 1 to 81 if "measure" means "infer".

That actually already tells you a lot about how to find the answer, and in particular how to map between answers for the "measure"="balance" 1 to 40 problem and answers for the "measure"="infer" 1 to 81 problem.

One more thing about brute force searching: It's not a priori clear that we can restrict the search to integers (there was no such requirement in the question), but the above considerations imply that we can, for if we need to hit 40 integers with 40 available combinations, that only works if all the weights are integers.

  • 1
    Perhaps the 80 in the question comes from the scenario where you know the weight is a (non-negative) integer, but don't know an upper bound. Thus you can tell a weight of 80 but not of 81 (as it could be 82, 83 etc.)2011-02-08
  • 0
    @Rawling: I see -- good idea.2011-02-08
  • 0
    Could you please explain the "infer" part ?! I am not sure I am able to understand it, you may like to use any example thanks.2011-02-08
  • 0
    Sure. Say you have only one weight. In the "balance" paradigm, you can only "measure" (i.e. balance) that one weight, say, 1. In the "infer" paradigm, you can choose the one weight you have to be of weight 2. Then if you want to distinguish weights from 1 to 3, you can balance them against the weight of 2 and identify them as 1, 2 or 3, according as they are lighter, the same or heavier as the weight of 2 - i.e. you can infer their weight using only one weight. (Also note Rawling's comment above on the difference between only knowing that the weights are integers and also knowing their range.)2011-02-08