Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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. –  joriki Feb 8 '11 at 13:38
    
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. –  joriki Feb 8 '11 at 13:43
    
... 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... –  Rawling Feb 8 '11 at 14:38
    
@Rawling: It is, yes -- sorry about that! I did say it was "slightly different" :-) –  joriki Feb 8 '11 at 15:18
    
Use the integer closest to $e=2.718...$ as a base, and hence as suggested use $3$. –  Eric Naslund Feb 8 '11 at 17:43
show 1 more comment

2 Answers

Try using base 3 to express weights in that range.

share|improve this answer
    
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. –  Rawling Feb 8 '11 at 13:15
1  
The numbers between 1 to 80 take 4 digits to express in base 3, since $3^4$=81$. –  lhf Feb 8 '11 at 13:28
    
Yeah, I figured that much out. Just trying to figure out (without giving it away) why those 4 particular numbers work. –  Rawling Feb 8 '11 at 13:37
    
@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. –  Ross Millikan Feb 8 '11 at 13:52
    
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. –  Rawling Feb 8 '11 at 14:34
show 1 more comment

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.

share|improve this answer
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.) –  Rawling Feb 8 '11 at 14:17
    
@Rawling: I see -- good idea. –  joriki Feb 8 '11 at 14:20
    
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. –  Quixotic Feb 8 '11 at 18:45
    
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.) –  joriki Feb 8 '11 at 19:10
    
+1 for the clever hints to the solution. –  Américo Tavares Feb 8 '11 at 19:44
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.