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?

 

[SamBones]

Being a programmer, I immediately jumped to this answer without even thinking about it...

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

 

[SamBones]

Hmmm, thinking a little bit more though, if the true goal is to minimize the number of weights, you could eliminate the 1g weight and just be able to put an even number of grams up. Then you infer the weight if it appears to be between two different even values. That is, if it balances heavier than 14g, and less than 16g, you say it's about 15g. That brings the number of weights to purchase down to 5.

 

[SamBones]

Hmmm, thinking more, since it's a balance and not a scale, the largest weight could be anything from 32g to 63g. Since wights can be put on the both sides of the balance, a weight of 40g can be determined by putting say a 50g weight on one side, and 10g worth on the side with the item being weighed (8g + 2g).

So...

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

 

[SamBones]

Heh, I guess I'm basically showing my thought process with these posts ().

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.

 

[karluk]

I'm fairly certain I already know the answer, so I won't be participating in this thread, which after all is about the thinking processes of people who DON'T know the solution. Full disclosure: The first time I heard about this problem was during a party in my college years, during which there was a certain amount of drinking going on. I very quickly came to the conclusion that I was in no state to give the problem serious thought, and asked to see the solution. I don't know if I would have been able to solve it on my own, if I had approached it in a more serious frame of mind.

 

[kwbMitel]

I Also know the solution and clearly remember how I worked it out

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.

 

[SamBones]

So I'm on the right track?

 

[SamBones]

Ok, I believe I got it down to four weights, but my method of figuring it out was pretty brute force (using Excel).

Spoiler

Each weight greater than the 1g is one more than twice the previous weights combined. Or...

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

 

[kwbMitel]

Brute force has always worked for me. I've adopted Monty Carlo method as that best describes my method

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

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

 

[lionelhill]

I suppose I ought to admit my thought-process too:

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.

Sam Bones, thanks for entering into the spirit of things so well, and describing your intermediate solution too!

 

[SamBones]

Well, here's pretty much how the thought process went in Excel...

Spoiler

Weight	Combinations	Comments
1	1		Must have a 1g weight to get the required resolution
2	3-1		To get 2, what minus 1 is 2?  3!
3	3	
4	3+1		All of my current weights are used and total 4
5	9-3-1		To get 5, what minus 4 is 5?  9!
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		All of my current weights are used and total 13
14	27-9-3-1	To get 14, what minus 13 is 14?  27!
15	27-9-3	
16	27-9-3+1	
etc	etc

At which point I realized that 27+9+3+1 is 40, so I didn't bother completing all of the combinations. I then looked for a formula to generalize it and came up with the ones I previously posted.

 

[kwbMitel]

@Lionelhill
[hide]I Don't know what you meant by a weight that could be measured without any weights at all but the 4^3 number intrigued me, can you elaborate?[/hide]

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

 

[karluk]

@kwbMitel
[hide]4^3 is an obvious typo. It should be 3^4=81. That's how many different ways four weights can be used - left pan, right pan or not at all. There are three states for each weight and four weights, hence 81 combinations. But one of the 81 is worthless - the one where none of the weights is used at all. Of the remaining 80 combinations, half are mirror images of the others and don't add any new weighing capabilities (alternatively they can be thought of ways to measure negative weights, such as the lift generated by a helium balloon). So there are only 40 different positive weights that the apothecary can measure, which not so coincidentally is just what Lionelhill was asking for.[/hide]

 

[lionelhill]

Thanks for spotting my typo and reading the thought instead of the words! I'm a biologist by training and therefore can't do maths.

 

[kwbMitel]

@Karluk and Lionelhill
[hide]There is another solution that allows you to determine 80 weights. It also only requires 4 weights. Same rules as original[/hide]

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

 

[karluk]

[hide]I can think of two plausible ways to double the number of possible weighings without increasing the number of weights required. Unfortunately I would judge that both methods violate the original conditions of the problem.

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.
[/hide]

 

[karluk]

[hide]Correction: Strategy 2 requires weights of 2g, 6g, 18g, and 54g.[/hide]

 

[kwbMitel]

@Karluk
[hide]My preference is your #2 as it does not introduce any new elements to the puzzle. All weights can be determined(if not measured exactly)[/hide]

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

 

[lionelhill]

Very original and a nice thought! Thanks kwbMitel. I regard it as a nice bonus that I'll maybe add if I think of a rewording of the original puzzle. I think if I'm strict about it, the original still stands, as it asked for a precision of 1g, and didn't offer a promise that every item weighed would have an integer mass.

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.