wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> medium >> Minimum number of weights 1kg - 80 kg
        
(Message started by: wonderful on Apr 11^th, 2008, 10:44pm)

Title: Minimum number of weights 1kg - 80 kg
Post by wonderful on Apr 11^th, 2008, 10:44pm

We have a two-arms balance. What is the number of weights we need to weight any M kg ? M is any natural number from 1 to 80.

E.g., you might need a 5 kg weight to weight M =5 kg, a 3 kg weight to weight a M =3kg. THe these two weights can weigh M = 8 kg.

Have A Great Day!

Title: Re: Minimum number of weights 1kg - 80 kg
Post by pscoe2 on Apr 12^th, 2008, 10:36am

i think it works like this....
for any M kg wt. u need 1,3,9,27,81.... wt to weigh a max of 1+3+9+27+... wt..
in this case it works out to be 5...
EX:
for 2=>3-1
for 4=>3+1
for 5=>9-3-1
for 6=>9-3....
i think u guys must hv figured out wht i m saying

Title: Re: Minimum number of weights 1kg - 80 kg
Post by Grimbal on Apr 12^th, 2008, 2:47pm

9-3+1, as the number 7 would be written in some special form of ternary.

Title: Re: Minimum number of weights 1kg - 80 kg
Post by wonderful on Apr 12^th, 2008, 3:03pm

Thanks Grimbal. After posting the question, how the above schem work for 7 kg, I notice that this should work as the way you mentioned.

The next question is can we prove that this is the optimal scheme i.e., any other scheme need at least 5 weights?

Have A Great Day!

Title: Re: Minimum number of weights 1kg - 80 kg
Post by Grimbal on Apr 12^th, 2008, 4:22pm

Well, with 4 weights you only have 3^4 = 81 ways to place them. One pattern is not to put any weight. The remaining 80 patterns can be paired symmetrically by switching the 2 panes. They measure the same weight with a negative sign. It follows that with 4 weights, you can distinguish only 40 different positive weights.

Title: Re: Minimum number of weights 1kg - 80 kg
Post by wonderful on Apr 12^th, 2008, 5:23pm

Thanks Grimbal! Regarding the solution: 1,3, 9, 27, 81 it can weights up to 127 kg. However, we need to weight up to 80 kg. Is there some waste here? Can anyone provide a more optimal solution?

Have A Great Day!

Title: Re: Minimum number of weights 1kg - 80 kg
Post by pex on Apr 13^th, 2008, 2:39am

on 04/12/08 at 17:23:10, wonderful wrote:

I think we can simply replace the 81 by 40.

Title: Re: Minimum number of weights 1kg - 80 kg
Post by towr on Apr 13^th, 2008, 6:59am

If we only need to distinguish integer weights from 1..80, then we only need weights 2,6,18,54
<2 => 1
=2 => 2
>2 & <6-2 => 3
=6-2 =>4
>6-2 & <6 => 5
etc

Title: Re: Minimum number of weights 1kg - 80 kg
Post by wonderful on Apr 13^th, 2008, 4:15pm

Welldone Towr!

Have A Great Day!

Title: Re: Minimum number of weights 1kg - 80 kg
Post by pscoe2 on Apr 14^th, 2008, 12:35am

@ towr
i m not clear what u want to say
i dont think with 2,6,18,54 u can make a wt of 1 kg....
am i missing smthing..

Title: Re: Minimum number of weights 1kg - 80 kg
Post by towr on Apr 14^th, 2008, 1:13am

on 04/14/08 at 00:35:32, pscoe2 wrote:

@ towr
i m not clear what u want to say
i dont think with 2,6,18,54 u can make a wt of 1 kg....
am i missing smthing..

If it's given that anything you weigh is a whole (positive) number of kilos, then if it's less than 2kg, it must be 1kg. But you're right in that you wouldn't be able to weigh, say, a kilogram of granulated sugar.
My scheme relies on an extra assumption. That's why I put an emphasis on 'distinguishing', rather than use a term like 'measuring'. (It's the difference between picking integers from a set of integers, or picking integers from a set of reals).