apothecary's scales

[lionelhill]

There are some simple logic problems (many of them old chestnuts) that programmers tend to approach differently to those without any such training. This is one of them. I'm personally interested not so much in the solution, but in the thought-process by which you would get there!

An apothecary has an old-fashioned set of apothecary's scales, a simple two-pan balance. He wants a set of weights to go with it: the minimal set of weights necessary to check masses between 1g and (at least) 40g with a precision of 1g. What weights must you supply?

 

[kwbMitel]

Yes, integer weights would make the extended solution more palatable. When you were mentioning the 3 states earlier I thought you had stumbled upon it but you were discussing the weights, not the scale. It's also why the 3^4 number intrigued me so much as 0 to 80 is 81 distinct weights

**********************************************
What's most important is that you realise ... There is no spoon.

 

[Olaf Doschke]

OK, I didn't read much of the answers, just saw SamBones smiley after his first thought. That of course alswo was mine. But what differs in the Scales is, that you can add a weight to the mass side or to the weights side, so any weight can be used both additive and subtractive and not at all. Bit in a number can only have additive or no effect on the total.

So my next thoughts are:

[hide]1. You can at most weigh a mass equal to the sum of all weights you have.
2. The next higher mass being Sum(weights)+1 can be measured with the other extreme situation: You add all your weights to that unmeasurable mass, and have 2*Sum(weights)+1 and need that weight as the next higher weight missing to measre that mass

Situation #2 is

These two rules don't say anything about how you can measure any weight in between these extremes, but I'll come back to this later.

I'll start with 1g mass and say I need a 1g weight to measure that. That's the situation #1.
2g alredy is a wight I can't measure then, but I don't need a 2g weight, as I can put my 1g weight to the mass side and then it's 3g, so I need a 3g weight as next higher weight, for the other pan.

So I have the sequence a(i+1) = 2* sum( a; n=1 to i)+1 which starting at a(1)=1 leads to 1,3,9,27, powers of 3.

By some "mystery" the sum of these 4 already are 40.

Now I need to prove I can construct any number of 1 to 40 with adding or subtracting these numbers. Trying that out I see some patterns:
1 = 1
2 = 3 - 1
3 = 3
4 = 3 + 1
5 = 9 - 3 - 1
6 = 9 - 3
7 = 9 - 3 + 1
8 = 9 - 1
9 = 9
10 = 9 + 1
11 = 9 + 3 - 1
12 = 9 + 3
13 = 9 + 3 + 1
14 = 27 - 9 - 3 - 1
15 = 27 - 9 - 3
...

The weights alterate between being used positively, being used negatively and not being used.

You could denote that with digits -1,0 and 1 in a place-value system. If you shift to the digits 0,1,2 instead, the normal trinary system could be used. It's place-values are 3^n with n from 0 to 3 you get the 1,3,9,27 again. The trinary number 2222 would then represent using all weights positive. As trinary number that is 80, but indeed due to the digits shifted by 1 2222 represents 1111, which is 40. So trinary number 0000 to 2222 make 81 combinations. You can use these 4 weights for -40g to 40g, which means you can use them for 0 to 40g, due to the symmetry of the scales.
[/hide]

Bye, Olaf.