INTELLIGENT WORK FORUMS
FOR COMPUTER PROFESSIONALS

Log In

Come Join Us!

Are you a
Computer / IT professional?
Join Tek-Tips Forums!
  • Talk With Other Members
  • Be Notified Of Responses
    To Your Posts
  • Keyword Search
  • One-Click Access To Your
    Favorite Forums
  • Automated Signatures
    On Your Posts
  • Best Of All, It's Free!

*Tek-Tips's functionality depends on members receiving e-mail. By joining you are opting in to receive e-mail.

Posting Guidelines

Promoting, selling, recruiting, coursework and thesis posting is forbidden.

Jobs

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?

RE: apothecary's scales

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

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

bigsmile


RE: apothecary's scales

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.


RE: apothecary's scales

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


RE: apothecary's scales

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

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

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.

RE: apothecary's scales

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.

RE: apothecary's scales

So I'm on the right track? bigsmile


RE: apothecary's scales

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

RE: apothecary's scales

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.

RE: apothecary's scales

(OP)
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!

RE: apothecary's scales

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

Spoiler:

CODE

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.

RE: apothecary's scales

@Lionelhill

Hidden:

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?

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

RE: apothecary's scales

@kwbMitel

Hidden:

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.

RE: apothecary's scales

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

RE: apothecary's scales

@Karluk and Lionelhill

Hidden:

There is another solution that allows you to determine 80 weights. It also only requires 4 weights. Same rules as original

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

RE: apothecary's scales

Hidden:

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.

RE: apothecary's scales

Hidden:

Correction: Strategy 2 requires weights of 2g, 6g, 18g, and 54g.

RE: apothecary's scales

@Karluk

Hidden:

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)

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

RE: apothecary's scales

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

RE: apothecary's scales

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.

RE: apothecary's scales

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:

Hidden:

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

Red Flag This Post

Please let us know here why this post is inappropriate. Reasons such as off-topic, duplicates, flames, illegal, vulgar, or students posting their homework.

Red Flag Submitted

Thank you for helping keep Tek-Tips Forums free from inappropriate posts.
The Tek-Tips staff will check this out and take appropriate action.

Reply To This Thread

Posting in the Tek-Tips forums is a member-only feature.

Click Here to join Tek-Tips and talk with other members!

Resources

Close Box

Join Tek-Tips® Today!

Join your peers on the Internet's largest technical computer professional community.
It's easy to join and it's free.

Here's Why Members Love Tek-Tips Forums:

Register now while it's still free!

Already a member? Close this window and log in.

Join Us             Close