## apothecary's scales

## apothecary's scales

(OP)

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?

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?

## RE: apothecary's scales

1g, 2g, 4g, 8g, 16g, 32g

## RE: apothecary's scales

## RE: apothecary's scales

So...

1g, 2g, 4g, 8g, 16g, 32g to 63g

## RE: apothecary's scales

Since 1g/2g/4g/8g get us from 1 to 15 grams, and we can put weights on either side, we just need one weight greater than 15g and within 15g of 40g. So this would do it.

1g, 2g, 4g, 8g, 30g

That's 5 weights, one less than my first answer.

## RE: apothecary's scales

## RE: apothecary's scales

It took me quite some time to get over the binary solution approach being used above. That's all I'll say

**********************************************

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

## RE: apothecary's scales

## RE: apothecary's scales

## Spoiler:

A = 1

B = 2(A) + 1 = 3

C = 2(A + B) + 1 = 9

D = 2(A + B + C) + 1 = 27

And that just happens to meet our target 40 (A+B+C+D = 40).

## RE: apothecary's scales

Sambones, can you discover a next level to the puzzle?

**********************************************

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

## RE: apothecary's scales

## Spoiler:

I also jumped to the binary solution before realising that this isn't binary and can be done by less. I also fiddled around before coming up with the 1,3,9... solution.

Then I realised that what's really happening is that each weight can exist in three states: left-pan, right-pan and not-used. That means it's not really a base-2 situation at all, it's base-3. 4 weights offers us 4^3 combinations, which is 81, but one of those is boring (no weights at all) and for all the others, we have two symmetrical situations. Therefore there should be 40 - at best - distinctive combinations of weights. We can't do better than 1-40g with 4 weights, but can we do it at all?

The next thing is this: each weight is basically being added or subtracted (or not used). It's different to a binary number where each weight is either not present or added. So we should pick each heavier weight so that the existing weights, when subtracted from the new weight, will just reach down as far as the first new mass we need to measure.

If you can currently cover the region 1,2,3,4 then the next you need to cover is 5, which means you need a mass of 4+5=9, so that we can now deal with the range of 9-(1,2,3,4), through 9, up to 9+(1,2,3,4) - so now we're good up to 13.

## RE: apothecary's scales

## Spoiler:

## CODE

## RE: apothecary's scales

## Hidden:

**********************************************

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

## RE: apothecary's scales

## Hidden:

## RE: apothecary's scales

## RE: apothecary's scales

## Hidden:

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

## RE: apothecary's scales

## Hidden:

1. Start with a two-pan balance that is badly out of balance. If (by sheer coincidence, of course) the left pan weighs 41g more than the right pan, then it will be possible to weigh any amount between 1g and 81g by putting the unknown weight in the right hand pan and using the 1g, 3g, 9g, and 27g weights to bring both pans into proper balance.

2. Make the assumption that all unknown weights are some integral number of grams. This assumption allows one to infer that an unknown weight must be n grams, as long as one can show that the unknown weight is > (n-1) grams and < (n+1) grams. With this assumption, use weights of 2g, 6g, 18g and 34g to measure exactly any unknown weight of 2n grams and infer the weight of any unknown weight of 2n+1 grams for all integral weights between 1g and 80g.

I like method 1 better than method 2. It doesn't require an assumption that is almost certainly false in the real world, and it is something that could realistically happen in a practical problem. Suppose you are trapped on a desert island with nothing but your two-pan balance and 1g, 3g, 9g, and 27g weights. In order to survive you for some reason desperately need to weigh some unknown amount that turns out to be more than 40g. Do you give up and die? Of course not. You would load your 40g of weights onto one pan and scoop an equivalent amount of sand onto the other pan. Now that you have a known quantity of sand in one of the pans, you would be in position to weigh any amount up to 80g.

## RE: apothecary's scales

## Hidden:

## RE: apothecary's scales

## Hidden:

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

## RE: apothecary's scales

In terms of thought-process, what you've done is cunningly realised that there are two states the balance can be in (balanced or not), so in addition to the 40 non-trivially different states the 4 weights can be in, we've got 2 different outcomes for each. I'm impressed.

As for starting with an unbalanced pan, that's "cheating" by hiding an extra weight in the balance! It's a nice idea though, and I'd do it on a desert island. Thanks for that thought too.

## RE: apothecary's scales

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

## RE: apothecary's scales

So my next thoughts are:

## Hidden:

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); 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.

Bye, Olaf.