wu :: forums - Print Page


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

        riddles >> medium >> Measuring Weights
        
(Message started by: william wu on May 27^th, 2003, 6:33pm)

Title: Measuring Weights
Post by william wu on May 27^th, 2003, 6:33pm

A merchant's 40 pound measuring weight falls from a table and breaks into 4 pieces. When the pieces are weighed, it was found that each had an integral weight, and the 4 pieces could be used to weight every integral weight between 1 and 40 pounds. What were the weights?

Author: Claude Gaspard Bachet de Meziriac (1581-1638)

Title: Re: Measuring Weights
Post by Leonid Broukhis on May 27^th, 2003, 7:46pm

Duh: [hide]1, 3, 9, and 27[/hide] Why is it medium?

Title: Re: Measuring Weights
Post by BNC on May 28^th, 2003, 3:16am

And why twice?

PS: It's on the 3rd post here (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1043672792;start=3)

And another note: look at the "inverse" problem: use 4 integer weights to measure any integer weight up to N. What is N, what are the weights (1,3,9,27 => N=40 is sub-optimal).

Title: Re: Measuring Weights
Post by Leonid Broukhis on May 28^th, 2003, 8:06am

What's optimality in this case? They do, or they don't.

Title: Re: Measuring Weights
Post by wowbagger on May 28^th, 2003, 8:44am

I guess BNC meant to ask for the maximal N possible with 4 weights.

Title: Re: Measuring Weights
Post by towr on May 28^th, 2003, 9:28am

well, you can have the weight as a negative, positive or not, so 3^4 -1 = 80 is the theoretical maximum.
This limits the space enough to find the an answer brute-force.

Title: Re: Measuring Weights
Post by towr on May 28^th, 2003, 10:09am

hmm.. well, without a novel way of weighing I'm hardpressed to find any N over 40..

Title: Re: Measuring Weights
Post by tohuvabohu on May 28^th, 2003, 12:18pm

There is one way to figure out more than 40 integral weights:
[hide]infer what you can't match[/hide]

Title: Re: Measuring Weights
Post by towr on May 28^th, 2003, 12:47pm

but then [hide]how do you know it's an integral weight[/hide]

Title: Re: Measuring Weights
Post by Leonid Broukhis on May 28^th, 2003, 12:54pm

on 05/28/03 at 09:28:40, towr wrote:

well, you can have the weight as a negative, positive or not, so 3^4 -1 = 80 is the theoretical maximum.
This limits the space enough to find the an answer brute-force.

You need to divide by two, because it does not matter on which side of the scale you put the object being weighted.

Title: Re: Measuring Weights
Post by towr on May 28^th, 2003, 1:35pm

heh, yeah.. that's true of course..
So that's an elegant proof that 40 is the best, this way..

You can weigh integral weights from -40 to 40 (including lighter than air objects like helium-filled balloons). And you can determine between which integral weights any nonintegral weight on that range is.

Title: Re: Measuring Weights
Post by BNC on May 28^th, 2003, 4:36pm

on 05/28/03 at 12:47:10, towr wrote:

but then [hide]how do you know it's an integral weight[/hide]

I did "say" any integer weight, but I gues I should have stressed that you have an a-priori knowledge of the "integerability" of the weights.