Author |
Topic: spices seller with balance scale (Read 1885 times) |
|
riddler358
Junior Member
Posts: 84
|
|
spices seller with balance scale
« on: Feb 25th, 2014, 8:19am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: spices seller with balance scale
« Reply #2 on: Feb 25th, 2014, 9:44am » |
Quote Modify
|
yes it is
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: spices seller with balance scale
« Reply #3 on: Feb 25th, 2014, 10:13am » |
Quote Modify
|
I suppose the seller could even go with pentagrams
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: spices seller with balance scale
« Reply #4 on: Feb 25th, 2014, 10:47am » |
Quote Modify
|
Is the number of weighings per sale limited to one?
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: spices seller with balance scale
« Reply #5 on: Feb 25th, 2014, 12:37pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: spices seller with balance scale
« Reply #6 on: Feb 25th, 2014, 12:45pm » |
Quote Modify
|
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.
|
« Last Edit: Feb 25th, 2014, 1:12pm by rloginunix » |
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: spices seller with balance scale
« Reply #7 on: Feb 25th, 2014, 1:29pm » |
Quote Modify
|
so we would have to add a restriction that his customers wouldnt like to wait therefore he wouldnt use spices as masses
|
« Last Edit: Feb 25th, 2014, 1:30pm by riddler358 » |
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: spices seller with balance scale
« Reply #8 on: Feb 26th, 2014, 9:18am » |
Quote Modify
|
on Feb 25th, 2014, 10:13am, towr wrote:I suppose the seller could even go with pentagrams |
| 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?
|
« Last Edit: Feb 26th, 2014, 11:20am by rloginunix » |
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: spices seller with balance scale
« Reply #9 on: Feb 26th, 2014, 9:28am » |
Quote Modify
|
on Feb 26th, 2014, 9:18am, rloginunix wrote:Hint: I miscalculated
|
« Last Edit: Feb 26th, 2014, 9:29am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: spices seller with balance scale
« Reply #10 on: Feb 26th, 2014, 9:39am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rloginunix
Uberpuzzler
Posts: 1029
|
|
Re: spices seller with balance scale
« Reply #11 on: Feb 26th, 2014, 12:01pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: spices seller with balance scale
« Reply #12 on: Feb 26th, 2014, 3:37pm » |
Quote Modify
|
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
|
« Last Edit: Feb 26th, 2014, 3:37pm by riddler358 » |
IP Logged |
|
|
|
towr
wu::riddles Moderator Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: spices seller with balance scale
« Reply #13 on: Feb 26th, 2014, 10:23pm » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
riddler358
Junior Member
Posts: 84
|
|
Re: spices seller with balance scale
« Reply #14 on: Feb 27th, 2014, 2:14pm » |
Quote Modify
|
ahhh he has most primitive scale
|
|
IP Logged |
|
|
|
|