Friday, March 30, 2007

a puzzle about minimum number of weights required, and how i by chance found its solution

it was a very boring class going on, and so my friend sitting next to me on the desk gave me a puzzle. what minimum number of weights does one need to be able to make measurements upto 100 kg [assuming a least count of 1 kg], and tell those weights too. i have heard/read this problem before, but i had not read or thought about its solution.

my strategy, which i by chance got somehow, was this.

-to measure any weight, we need to build it up
-to build up a weight, there are 3 methods
  1. a direct weight of its measurement. example to measure 2 kg, we have a weight that weighs 2 kg
  2. additive weight- i.e. a weight produced by adding 2 or more available direct weights. example to measure 2 kg, i add 2 available 1 kg weights
  3. subtractive weight- i.e. a weight produced by subtracting 2 [or more- in some combinations] available direct weights. example to produce 2 kg, subtract 3 from 5.
having formed this strategy, the simple task was now to implement it on the whole length of integers from 1 to 100.

here's the digest

-for 1 kg- 1st option is mandatory, unless we want to deliberately use a less efficient combination. hence 1 kg weight is mandatory

-for 2 kg, although all 3 methods can be used, subtractive approach looks like the most efficient, since for subtraction we would necessarily have to have a highest possible weight [from which an already present direct weight- 1 kg in this case- would be subtracted]. not only would this highest weight itself serve us till its own magnitude, but by adding it to already available weight rather than subtracting that from it, we would be able to achieve higher weights. a simple way to calculate the magnitude of this subtractive weight is to add the sum total of already available weights to the value we want to form. example 1 kg is available as direct weight. we want to form 2 kg value. so add 1 [already available] to 2 [value we want to form] and thus we need 3 kg weight. with 1 and 3, not only can we form 2 by subtraction, but we can also form 4 by addition. had we chosen to have 2 kg direct weight so as to be able to form 3 kg by addition, we would not have been able to form 4 kg, and also there would have been a redundant combination- subtracting 1 from 2 to achieve 1- which we already have in form of 1 kg direct weight. with 1 and 3 there is no redundant combination. and hence it is most efficient. so far till 4 kg.

-for 5, again we need to add 1+3+5= 9. we can achieve 5,6,7,8,9,10,11.....13 with this

-14- add 1+3+9+14= 27. values up to 40 possible.

-41- we need 81 as per above algorithm.

-with 81 available, we can calculate any value till 121. so there are 21 redundant values here.

i will someday try to find out a way to calculate precisely till 100, and not till 121, since any unnecessarily heavy weight will cause unnecessary cost increase- since metal is obviously used in creating these weights. anyways, i am happy that a nice strategy by chance came to my mind the moment he put his puzzle.

No comments:

Post a Comment