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