wu :: forums - Print Page


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

        riddles >> easy >> spices seller with balance scale
        
(Message started by: riddler358 on Feb 25^th, 2014, 8:19am)

Title: spices seller with balance scale
Post by riddler358 on Feb 25^th, 2014, 8:19am

Seller of spices shop wants to sell his spices in decagrams. For measurement he wants to use balance scale. He wants to be able to sell any amount of decagrams up to 1 kilogram. What is the least number of masses he needs to run his shop in such manner?

Title: Re: spices seller with balance scale
Post by towr on Feb 25^th, 2014, 9:07am

[hide]5[/hide]

Title: Re: spices seller with balance scale
Post by riddler358 on Feb 25^th, 2014, 9:44am

yes it is :)

Title: Re: spices seller with balance scale
Post by towr on Feb 25^th, 2014, 10:13am

I suppose the seller could even go with pentagrams :P

Title: Re: spices seller with balance scale
Post by rloginunix on Feb 25^th, 2014, 10:47am

Is the number of weighings per sale limited to one?

Title: Re: spices seller with balance scale
Post by towr on Feb 25^th, 2014, 12:37pm

You have a scheme in mind other than putting weights on the scale and then scoping/pouring the spices till the scales balance?

I suppose one weight is enough if you're allowed to create piles of spices that can act as additional weights.

Title: Re: spices seller with balance scale
Post by rloginunix on Feb 25^th, 2014, 12:45pm

You are absolutely right, towr. That's what I was after. If more than one measurement per sale is allowed rations of spices themselves can become weights.

Title: Re: spices seller with balance scale
Post by riddler358 on Feb 25^th, 2014, 1:29pm

so we would have to add a restriction that his customers wouldnt like to wait therefore he wouldnt use spices as masses

Title: Re: spices seller with balance scale
Post by rloginunix on Feb 26^th, 2014, 9:18am

on 02/25/14 at 10:13:50, towr wrote:

I suppose the seller could even go with pentagrams :P

OK, let's see. If, for convenience, we scale the numbers down then 10 grams becomes 1 and 1000 grams becomes 100. The problem then is to find the smallest number of weights required to measure any whole amount of substance between 1 and 100 grams with a one-gram precision.

It's still not specified how the pan scales are to be used. Two cases are possible - both pans, only one pan.

In either case let's assume that a problem has been solved somehow and N weights does it. If we freeze any measurement in time we will see that some weights will be off the pans - assign 0 to those - while some will be on them. Assign 1 to the weights on the pan by themselves. Assign 2 to the weights on the same pan with the substance - if both pans are to be used. The smallest number of states that describes any such measurement then is 2 and 3 correspondingly.

It follows we should use binary and ternary numbers to record the required amount of substance because any such mapping is lossless - we can take any number in base 10 and rewrite it in base 2 or 3. From the rules of such translation it follows that N is the smallest number of terms of powers of 2 or 3 that sums to at least 100. In the "Counterfeit coin" thread we've done such calculation and know that in general for any number "a" the sum of consecutive powers of its N terms is (a^N - 1)/(a - 1). That's the maximum whole amount of substance we can measure with N weights.

If a == 3 then N = 5, if a == 2 then N = 7. So a = 3, N = 5 and both pans should be used is the answer: 1, 3, 9, 27, 81. (For 2/7 it's of course 1, 2, 4, 8, 16, 32, 64).

The "3/5" weighing scheme is based on the fact that the required amount of weight is the difference between the larger amount of weights on the pan by themselves and the smaller amount of weights on the same pan with the substance. Since we are only allowed to use the weights that are the exact powers of 3 then we should record this difference using only such numbers in base 10 (ten) or the numbers that have only zeros and ones in base 3. For example, 17 grams of substance = 27 - 10 = (27 + 1) - 9. So we put two weights of 1 and 27 on one pan, one weight of 9 on the other and add the substance till pans balance.

The only extra room I see so far is that with 5 weights we can measure extra 21 grams: (3^5 - 1)/2 = 121. With 5-gram steps renumbering yields the range of 1 to 200. Five ternary bits isn't enough to record the extra 79 grams.

Any hints?

Title: Re: spices seller with balance scale
Post by towr on Feb 26^th, 2014, 9:28am

on 02/26/14 at 09:18:12, rloginunix wrote:

Any hints?

Hint: [hide]I miscalculated[/hide] ;D

Title: Re: spices seller with balance scale
Post by rloginunix on Feb 26^th, 2014, 9:39am

While driving to work today I hope an interesting question popped into my head.

What if we put our spice seller on the road? He/she is not traveling through the seven bridges of Konigsberg but rather simply goes from place to place occasionally. To save the most money on gas the spice seller wants to put the lightest load of weights in the car. So:

what is the lightest by weight package of weights required to measure any whole amount of substance between 1 and 100 grams?

I don't know the answer, sorry. Just enough brain cycles to come up with a question and type it in.

Title: Re: spices seller with balance scale
Post by rloginunix on Feb 26^th, 2014, 12:01pm

One very simple and quick optimization is to cut the extra 21 grams out and make it same 5 weights: 1, 3, 9, 27, 60.

A primitive "proof" for a 1 to 10 grams range is as follows. Normally we would need 3 weights 1, 3 and 9. An optimized mix would be 1, 3 and 6. Numbers in square brackets designate the substance and here's how we would measure all the weights from 1 to 10:

1: 1 = [1]
2: 3 = 1 + [2]
3: 3 = [3]
4: 3 + 1 = [4]
5: 6 = 1 + [5]
6: 6 = [6]
7: 6 + 1 = [7]
8: 6 + 3 = 1 + [8]
9: 6 + 3 = [9]
10: 6 + 3 + 1 = [10]

I don't think this is the right answer though.

Title: Re: spices seller with balance scale
Post by riddler358 on Feb 26^th, 2014, 3:37pm

i had quick thought to add it to the question, but almost as quick was obvious reaction that if he is weighin in such manner he needs the upper bound total weight

Title: Re: spices seller with balance scale
Post by towr on Feb 26^th, 2014, 10:23pm

If he has a balance scale with adjustable arms, then he only needs to mark how to adjust the arms, and one or fewer weights could suffice.

Title: Re: spices seller with balance scale
Post by riddler358 on Feb 27^th, 2014, 2:14pm

ahhh he has most primitive scale :)