[Prime]

Having disposed of one weighing job, same rock-weighing issued requirements for another challenging task. The task involves a balance-type scales.

1). Due to government regulations you can use only one measuring weight. It can be any weight you want. There are 7 rocks each weighing a whole number of pounds between 1 and 5 inclusively. The rocks are not necessarily distinct in weight from one another. Using just one weigh and balance scales, figure out the weight of each rock.

[bonanova]

Using just one weigh and balance scales, figure out the weight of each rock.

Does "weigh" refer to use of the scales? or does it mean "weight"?

If the latter, how many times may the scales be used?

[HoustonHokie]

Assuming you mean one weight and unlimited weighings:

it's impossible. Here are cases where you can't determine all the weights:

If your chosen weight is:

1 lb - you can't determine the weight of all the rocks if they are all equal weight and all heavier than 1 lb. (ex 5,5,5,5,5,5,5 vs 4,4,4,4,4,4,4)

2 lb - you can't determine the weight of 7 equal weight rocks that are 3 - 5 lbs. (ex 5,5,5,5,5,5,5 vs 4,4,4,4,4,4,4)

3 lb - you can't determine the weight of 7 equal weight rocks that are 4 - 5 lbs. (ex 5,5,5,5,5,5,5 vs 4,4,4,4,4,4,4)

4 lb - you can't determine the weight of 1 rock less than 4 lb if you have six 4-lb rocks. (ex 4,4,4,4,4,4,2 vs 4,4,4,4,4,4,1)

5 lb - you can't determine the weight of 1 rock less than 5 lb if you have six 5-lb rocks. (ex 5,5,5,5,5,5,2 vs 5,5,5,5,5,5,1)

The OP didn't rule out fractional weights, so those may be a possibility - I'll have to check and see. I also don't think it helps to choose a weight heavier than 5 lb.

That being said, the 4-lb weight is a pretty good choice. The only time it doesn't work is if you have six 4-lb rocks in the group and the seventh is less than 4 lb. The others seem to fail more often than that.

Edited October 13, 2008 by HoustonHokie

[bonanova]

Well it was a fun exercise, but ...

It cannot be done.

Group E = {1's}
Group F = {2's, 3's, 4's, 5's}

If there are at least three E's you can find everything. DONE
ELSE

Sort F, lightest to heaviest
If F is of four types, then F = {2,3,4,5} DONE
If F is of three types, R, S, T,
Compare [1 and r] with [s]. If lighter, F = {2,4,5} DONE
ELSE compare [1 and s] with [t]
If balance, F = {2,3,4} DONE
Else F = {2,3,5} DONE
If F is of two types S, T
Compare [1 and s] with [t]. If balance, F = {2,3}, {3,4} or {4,5} WHAT NEXT?
ELSE If there is at least one E
Compare [1 and e and s] with [t]
If balance, F = {2,4} or {3,5} compare [1 and e] with [s]
If balance, F = {2,4} ELSE F = {3,5} DONE
ELSE F = {2,5} DONE
IF E is empty STUMPED
If F is of one type
Fewer than three E's STUMPED

Compare all stones against known weight of 1.

Group D = {1's}
Group E = {2's}
Group F = {3's, 4's, 5's}

Sort F into R, S, T, with T heaviest.
If R S T are all not empty, {R,S,T} = {3,4,5} Done.

If T is empty:
Compare [2 and r] with [s]. If balance, {R,S} = {3,5} Done. Else {R,S} is {3,4} or {4,5}

If D is not empty, compare [d and 2] with [r]. If balance, {R,S} = {3,4}, else {4,5}. Done. OR If D is empty,
If E is not empty, compare [e and 2] with [s]. If balance, {R,S} = {4,5}, else {3,4}. Done. OR If D and E are empty,
If R has at least two stones, compare [r and r] with [s and 2]. If balance, {R,S} = {3,4} else {4,5}. Done. OR
If R has only one stone: F = {3,4,4,4,4,4,4} or {4,5,5,5,5,5,5}. STUMPED.

If S and T are empty: F = {3,3,3,3,3,3,3} or {4,4,4,4,4,4,4} or {5,5,5,5,5,5,5}. STUMPED.

Compare all stones against known wieght of 2.

Compare all seven to known weight of 3
Group D = {1's, 2's}
Group E = {3's}
Group F = {4's, 5's}

Compare D stones pairwise.
If D is of two types, they are {1's} and {2's}
If D is of one type
If there are at least 2 d's:
Compare [d and d] with [3]. If lighter, {D} = {1} else {D} = {2}
If there is only one d:
Compare F stones pairwise.
If F is of two types, they are {4's} and {5's}.
Compare [3 and d] with [4].
If balance, {D} = {1} Else {D} = {2}
If F is of one type
Compare [3 and d] with [f].
If lighter, {D,F} = {1,5}
If heavier, {D,F} = {2,4}
If balance, {D,F} = {1,4} or {2,5}
Then what?
If F is empty: STUMPED.
If D is empty STUMPED

KNOWN weight is 3:

Group D = {1's, 2's, 3's} - Sort D into R, S, T with T heaviest
Group E = {4's}
Group F = {5's}

If R S T are all not empty
D = {1,2,3} DONE

If [only] T is empty:
Compare [r and s] with [4]
If lighter, D = {1,2} DONE
If balance, D = {1,3} DONE
If heavier, D = {2,3} DONE
If S and T are empty
If there are at least two D's
Compare [d and d] with [4]
If lighter, D = {1} DONE
If balance, D = {2} DONE
If heavier, D = {3} DONE
If there is only one D
If F is not empty
Compare [4 and d] with [f]
If balance, D = {1} DONE
ELSE D = {2} or {3}
Depending on how many E and F
Some combinations could be found.
If F is empty we have {d,4,4,4,4,4,4} and 4
Cant distinguish d=2 from d=3 STUMPED

Compare all stones against known weight of 4.

then

Group D = {1's, 2's, 3's, 4's}
Group E = {5's}

Sort D, lightest to heaviest
If D is of four types, then D = {1,2,3,4} DONE
If D is of three types R, S, T. -- D = {1, 2, 3}, {1, 2, 4}, {1, 3, 4} or {2, 3, 4}
Compare [r and t] with [5]
If lighter, D = {1, 2, 3} DONE
If heavier, D = {2, 3, 4} DONE
If balance, compare [r and s] with [t]
If balance, D = {1, 3, 4} DONE
ELSE D = {1, 2, 4} DONE
If D is of two types S, T -- D = {1,2}, {2,3}, {3,4}
Compare [s and t] with [5]
If lighter, D = {1,2} or {1,3}
If balance, D = {2,3} or {1,4}
If heavier, D = {2,4} or {3,4}
If there are at least two S,
Compare [s and s] with [t] to resolve. DONE
If there is only one S
STUMPED.
If D is of only one type
If there are at least 2 D's compare [d and d] with [5]
If lighter, D = {1} or {2}
If there are at least 3 D's compare [d and d and d] with [5] to resolve DONE
If there are no more than 2 D's STUMPED
If heavier, D = {3} or {4}
STUMPED.

Compare all stones against known weight of 5.

[Prime]

Well it was a fun exercise, but ...

Condition-wise it is the same problem as your original "Weighty thoughts". You have to excuse my grammar. I meant there is a balance-type scale, where you can only weigh one side against another and see if one weighs more, or another, or they are equal. My variation of the problem explores some logical inferences that we passed in your original post.

I believe, I solved this problem. If I point out what's wrong with your proof above, it would be a dead giveaway. And I think you might enjoy finding the solution on your own.

[bonanova]

Condition-wise it is the same problem as your original "Weighty thoughts". You have to excuse my grammar. I meant there is a balance-type scale, where you can only weigh one side against another and see if one weighs more, or another, or they are equal. My variation of the problem explores some logical inferences that we passed in your original post.

I believe, I solved this problem. If I point out what's wrong with your proof above, it would be a dead giveaway. And I think you might enjoy finding the solution on your own.

Fair enough. I'll list a hard case for each known weight.

If you can solve one of them, just reply OK.

If I see an OK I'll revisit my analysis.

1. Known weight of 1: Distinguish seven 5's from seven 4's.
   
2. Known weight of 2: Distinguish seven 5's from seven 4's.
   
3. Known weight of 3: Distinguish seven 5's from seven 4's.
   
4. Known weight of 4: Distinguish six 4's and a 1 from six 4's and a 2 or 3.
   
5. Known weight of 5: Distinguish six 5's and a 1 from six 5's and a 2, 3 or 4.
   

[Prime]

Fair enough. I'll list a hard case for each known weight.

If you can solve one of them, just reply OK.

If I see an OK I'll revisit my analysis.

1. Known weight of 1: Distinguish seven 5's from seven 4's.
   
2. Known weight of 2: Distinguish seven 5's from seven 4's.
   
3. Known weight of 3: Distinguish seven 5's from seven 4's.
   
4. Known weight of 4: Distinguish six 4's and a 1 from six 4's and a 2 or 3.
   
5. Known weight of 5: Distinguish six 5's and a 1 from six 5's and a 2, 3 or 4.
   

OK I'll try to answer that making as little giveaway as I can manage:

There is nothing wrong with your analysis. And there is nothing wrong with your calculations.

What's wrong is the conclusion that the problem is unsolvable.

I must add that the problem is fair. There are no tricks and no additional assumptions to make, aside from what is clearly implied in the statement of the problem.

[Prime]

Does "weigh" refer to use of the scales? or does it mean "weight"?

If the latter, how many times may the scales be used?

I've made several typos and must clarify. I meant one "reference weight" of your choosing. You can make any number of rock weighings, until you find all individual rocks' weights.

Thanks for pointing that out.

Also, I meant rock-weighing firm in the first sentence. The word "firm" is missing (which is not rellevant to the solution, though.)

[bonanova]

OK I'll try to answer that making as little giveaway as I can manage:

There is nothing wrong with your analysis. And there is nothing wrong with your calculations.

What's wrong is the conclusion that the problem is unsolvable.

I must add that the problem is fair. There are no tricks and no additional assumptions to make, aside from what is clearly implied in the statement of the problem.

I'll accept all of that, of course, in which case you should be able to solve at least one of my hard cases.

Can you solve at least one of my hard cases?

Or was your OK a yes?

[Prime]

I'll accept all of that, of course, in which case you should be able to solve at least one of my hard cases.

Can you solve at least one of my hard cases?

Or was your OK a yes?

As far as I can see, your hard cases are unsolvable.

[bonanova]

As far as I can see, your hard cases are unsolvable.

Great hint. Thanks.

Now to get my thinking outside my self-imposed box.

This is a great puzzle ...

[bonanova]

1. 2.5
   
2. 3.5
   
3. 1.5
   

[Prime]

1. 1.5
   
2. 2.5
   
3. 3.5
   

Continue thinking outside self-imposed box. Be warned though, the proof of my solution is 2 pages long.

Not that the proof is all that difficult, but it is tedious.

[HoustonHokie]

1. 2.5
   
2. 3.5
   
3. 1.5
   

I was thinking outside (or maybe inside?) the box in that way as well, but I got stuck and now I'm trying

6, 7, 8

Maybe it has something to do with the fact that the range of possible weights for the whole set of stones is between 7 and 35.

[Prime]

I was thinking outside (or maybe inside?) the box in that way as well, but I got stuck and now I'm trying

6, 7, 8

Maybe it has something to do with the fact that the range of possible weights for the whole set of stones is between 7 and 35.

Since this puzzle is my own invention based on the previous "Weighty thoughts" topic, the solution I have, may not be so simple and elegant.

However, ...

Before I found what the reference weight should be, I found a certain criteria for it.

If you deduce the criteria, you'll find the reference weight, and then I'll forego the tedious proof that it works, as long as you understand how it does, I'll consider, you've found the solution.

[HoustonHokie]

Since this puzzle is my own invention based on the previous "Weighty thoughts" topic, the solution I have, may not be so simple and elegant.

However, ...

Before I found what the reference weight should be, I found a certain criteria for it.

If you deduce the criteria, you'll find the reference weight, and then I'll forego the tedious proof that it works, as long as you understand how it does, I'll consider, you've found the solution.

Well, here's what I was thinking...

I think a stone of weight 8 works. Here's why:

Basically, the principle is to take all the stones and place them on the scale with the [8]. If the stones are lighter than [8], you know the answer (1 1 1 1 1 1 1). If it's equal, you know the answer as well (1 1 1 1 1 1 2). If 7 stones weigh more than [8], try with any 6 of those 7 stones.

If 6 stones weigh less than [8], there are two possible solutions (1 1 1 1 1 1 or 1 1 1 1 1 2), which are easily distinguishable from one another by weighing the stones against each other. If they equal [8], then there are two solutions (1 1 1 1 2 2 or 1 1 1 1 1 3), which are distinguishable. If they're more than [8], try with 5 stones.

If 5 stones weight less than [8], there are four possible solutions (1 1 1 1 1 or 1 1 1 1 2 or 1 1 1 1 3 or 1 1 1 2 2), all of which can be distinguished. 5 stones equalling [8] can be made with (1 1 1 1 4 or 1 1 1 2 3 or 1 1 2 2 2) and you can tell those apart. If 5 stones weigh more than [8], try with 4 stones.

And so on. The pattern continues until you have 2 stones. If two stones equal 8, they are (4 4 or 5 3). If they are greater than 8, they can be (4 5) or (5 5). The nice thing is that when multiple combinations of stones make are less than or equal to [8], the weights of the individual stones can always be found by weighing them against one another.

Once you've identified any of your stones, it should be possible to identify the rest. Hopefully this will satisfy for your proof, because it would take a long time to write it all out.

edit: correct bust in 5 stone solution

Edited October 13, 2008 by HoustonHokie

[Prime]

Well, here's what I was thinking...

I think a stone of weight 8 works. Here's why:

Basically, the principle is to take all the stones and place them on the scale with the [8]. If the stones are lighter than [8], you know the answer (1 1 1 1 1 1 1). If it's equal, you know the answer as well (1 1 1 1 1 1 2). If 7 stones weigh more than [8], try with any 6 of those 7 stones.

If 6 stones weigh less than [8], there are two possible solutions (1 1 1 1 1 1 or 1 1 1 1 1 2), which are easily distinguishable from one another by weighing the stones against each other. If they equal [8], then there are two solutions (1 1 1 1 2 2 or 1 1 1 1 1 3), which are distinguishable. If they're more than [8], try with 5 stones.

If 5 stones weight less than [8], there are four possible solutions (1 1 1 1 1 or 1 1 1 1 2 or 1 1 1 1 3 or 1 1 1 2 2), all of which can be distinguished. 5 stones equalling [8] can be made with (1 1 1 1 4 or 1 1 1 2 3 or 1 1 2 2 2) and you can tell those apart. If 5 stones weigh more than [8], try with 4 stones.

And so on. The pattern continues until you have 2 stones. If two stones equal 8, they are (4 4 or 5 3). If they are greater than 8, they can be (4 5) or (5 5). The nice thing is that when multiple combinations of stones make are less than or equal to [8], the weights of the individual stones can always be found by weighing them against one another.

Once you've identified any of your stones, it should be possible to identify the rest. Hopefully this will satisfy for your proof, because it would take a long time to write it all out.

edit: correct bust in 5 stone solution

I went through a number of trials before finding how weight range/number of rocks/reference weight correspond.

Whenever you have a possible solution -- look for the proof that it does not work.

[Prime]

In case people are still working on this, I'll throw this suggestion into the pot.

First, try solving 4 rocks ranging from 1 to 4 lb with one reference weight.

When testing possible solution, look for proof that it does not work.

For example reference weight of 3 lb fails to solve 3 rocks of 3 lb each with 4th rock lighter than 3 lb.

[bonanova]

I'm tied up today but will have time to work on this tomorrow.

No further clues please.

[HoustonHokie]

In case people are still working on this, I'll throw this suggestion into the pot.

First, try solving 4 rocks ranging from 1 to 4 lb with one reference weight.

When testing possible solution, look for proof that it does not work.

For example reference weight of 3 lb fails to solve 3 rocks of 3 lb each with 4th rock lighter than 3 lb.

Here's a brute force method for solving your hint puzzle - a reference weight of 5 works. In the code box, the numbers in front of each solution represent how many 1 lb, 2 lb, 3lb, or 4 lb stones you have in the set.

4 0 0 0 4 rocks < 5 - know answer
3 1 0 0 4 rocks = 5 - know answer
3 0 1 0 3 rocks = 4th rock - know answer
3 0 0 1 3 rocks < 4th rock - know answer
2 2 0 0 3 rocks = 5, 2 heavier than other 1 - know answer
2 0 2 0 3 rocks = 5, 2 lighter than other 1 - know answer
2 0 0 2 2 rocks = 5; 2 lighter rocks less than 1 heavier rock - know answer
2 1 1 0 2 lightest rocks = middle rock; 1 lightest + middle = heaviest rock - know answer
2 1 0 1 2 lightest rocks = middle rock; 1 lightest + middle < heaviest rock - know answer
2 0 1 1 2 lightest rocks < middle rock - know answer
1 3 0 0 3 rocks = 5, 2 heavier than other 1 - know answer
1 0 3 0 1 heaviest rock + lighter rock < 5, 2 heavier rocks = 5 + lighter rock - know answer
1 0 0 3 2 rocks = 5; 2 heavier rocks > 5 + lighter rock - know answer
1 2 1 0 heaviest rock + 1 middle = 5 - know answer
1 2 0 1 heaviest rock + lightest rock = 5; 2 middle rocks < 5 - know answer
1 1 2 0 1 heaviest rock + middle = 5 - know answer
1 0 2 1 heaviest rock + lightest rock = 5; 2 middle rocks > 5 - know answer
1 1 0 2 heaviest rock + lightest rock = 5; lightest rock + middle rock < heaviest rock - know answer
1 0 1 2 heaviest rock + lightest rock = 5; lightest rock + middle rock = heaviest rock - know answer
1 1 1 1 4 different weights - know answer
0 3 1 0 2 rocks = 5; 3 lightest rocks > 5 - know answer
0 3 0 1 2 lightest rocks = heaviest rock; 1 lightest rock + heaviest rock > 5 - know answer
0 1 3 0 2 rocks = 5; 2 heavier rocks < 5 + lighter rock - know answer
0 0 3 1 2 lighter rocks > 5 - know answer
0 1 0 3 heaviest rock + lightest rock > 5; 2 heavier rocks > 5 + lighter rock - know answer
0 0 1 3 heaviest rock + lightest rock > 5; 2 heavier rocks = 5 + lighter rock - know answer
0 2 2 0 heaviest rock + lightest rock = 5; 2 lighter rocks > 1 heavier rock; 2 lighter rocks < 5 - know answer
0 2 0 2 heaviest rock + lightest rock > 5; 2 lighter rocks = 1 heavier rock - know answer
0 0 2 2 heaviest rock + lightest rock = 5; 2 lighter rocks > 1 heavier rock; 2 lighter rocks > 5 - know answer
0 2 1 1 lightest rock + middle rock = 5 - know answer
0 1 2 1 lightest rock + middle rock = 5 - know answer
0 1 1 2 lightest rock + middle rock = 5 - know answer

[b]1 2 3 4[/b] 

Here's why I chose 5 as my reference weight. It's the same reason I chose 8 as the reference weight in the original problem. The range of possible weights for 4 stones is 4 to 16. I chose a weight that was one greater than the low end of that range. That way, I could immediately tell what to do with combinations that are less than or equal to my reference weight, and combinations of 2 or 3 stones out of the group would tell me what to do with overall combinations that are greater than my reference weight. I actually think that I could do it with a weight of 6 or 7 as well because they are less than 2*(low end of the range) = 2*4 = 8, but I'm not really willing to work out the brute force answer again. Basically, I feel pretty certain that choosing a reference weight that is 1 greater than the low end of the combination weight range will always work, and I think that choosing any whole number weight that is in the range (low end) < ref weight < 2*(low end) will work as well. I can't find a situation where a weight in that range won't work, and that's what you were hinting at, I think.

[Prime]

Here's a brute force method for solving your hint puzzle - a reference weight of 5 works. In the code box, the numbers in front of each solution represent how many 1 lb, 2 lb, 3lb, or 4 lb stones you have in the set.

4 0 0 0 4 rocks < 5 - know answer
3 1 0 0 4 rocks = 5 - know answer
3 0 1 0 3 rocks = 4th rock - know answer
3 0 0 1 3 rocks < 4th rock - know answer
2 2 0 0 3 rocks = 5, 2 heavier than other 1 - know answer
2 0 2 0 3 rocks = 5, 2 lighter than other 1 - know answer
2 0 0 2 2 rocks = 5; 2 lighter rocks less than 1 heavier rock - know answer
2 1 1 0 2 lightest rocks = middle rock; 1 lightest + middle = heaviest rock - know answer
2 1 0 1 2 lightest rocks = middle rock; 1 lightest + middle < heaviest rock - know answer
2 0 1 1 2 lightest rocks < middle rock - know answer
1 3 0 0 3 rocks = 5, 2 heavier than other 1 - know answer
1 0 3 0 1 heaviest rock + lighter rock < 5, 2 heavier rocks = 5 + lighter rock - know answer
1 0 0 3 2 rocks = 5; 2 heavier rocks > 5 + lighter rock - know answer
1 2 1 0 heaviest rock + 1 middle = 5 - know answer
1 2 0 1 heaviest rock + lightest rock = 5; 2 middle rocks < 5 - know answer
1 1 2 0 1 heaviest rock + middle = 5 - know answer
1 0 2 1 heaviest rock + lightest rock = 5; 2 middle rocks > 5 - know answer
1 1 0 2 heaviest rock + lightest rock = 5; lightest rock + middle rock < heaviest rock - know answer
1 0 1 2 heaviest rock + lightest rock = 5; lightest rock + middle rock = heaviest rock - know answer
1 1 1 1 4 different weights - know answer
0 3 1 0 2 rocks = 5; 3 lightest rocks > 5 - know answer
0 3 0 1 2 lightest rocks = heaviest rock; 1 lightest rock + heaviest rock > 5 - know answer
0 1 3 0 2 rocks = 5; 2 heavier rocks < 5 + lighter rock - know answer
0 0 3 1 2 lighter rocks > 5 - know answer
0 1 0 3 heaviest rock + lightest rock > 5; 2 heavier rocks > 5 + lighter rock - know answer
0 0 1 3 heaviest rock + lightest rock > 5; 2 heavier rocks = 5 + lighter rock - know answer
0 2 2 0 heaviest rock + lightest rock = 5; 2 lighter rocks > 1 heavier rock; 2 lighter rocks < 5 - know answer
0 2 0 2 heaviest rock + lightest rock > 5; 2 lighter rocks = 1 heavier rock - know answer
0 0 2 2 heaviest rock + lightest rock = 5; 2 lighter rocks > 1 heavier rock; 2 lighter rocks > 5 - know answer
0 2 1 1 lightest rock + middle rock = 5 - know answer
0 1 2 1 lightest rock + middle rock = 5 - know answer
0 1 1 2 lightest rock + middle rock = 5 - know answer

[b]1 2 3 4[/b] 

Here's why I chose 5 as my reference weight. It's the same reason I chose 8 as the reference weight in the original problem. The range of possible weights for 4 stones is 4 to 16. I chose a weight that was one greater than the low end of that range. That way, I could immediately tell what to do with combinations that are less than or equal to my reference weight, and combinations of 2 or 3 stones out of the group would tell me what to do with overall combinations that are greater than my reference weight. I actually think that I could do it with a weight of 6 or 7 as well because they are less than 2*(low end of the range) = 2*4 = 8, but I'm not really willing to work out the brute force answer again. Basically, I feel pretty certain that choosing a reference weight that is 1 greater than the low end of the combination weight range will always work, and I think that choosing any whole number weight that is in the range (low end) < ref weight < 2*(low end) will work as well. I can't find a situation where a weight in that range won't work, and that's what you were hinting at, I think.

Unfortunately, the "brute force" enumeration missed some variations. In particular, the cases when you have all 4 rocks 4lb and all 4 rocks 3lb each. I don't see how your chosen reference weight can solve that.

Your reasoning for reference weight criteria is lingering dangerously close to the solution. You just need to give a bit more attention to the details.

[HoustonHokie]

Unfortunately, the "brute force" enumeration missed some variations. In particular, the cases when you have all 4 rocks 4lb and all 4 rocks 3lb each. I don't see how your chosen reference weight can solve that.

Your reasoning for reference weight criteria is lingering dangerously close to the solution. You just need to give a bit more attention to the details.

It's always the obvious that sneaks up and bites you in the butt . To fix my missing cases, you need a weight that will help you distinguish them, which can only be done with a

7-lb weight. So, in general, a weight of 2*(low end of range) - 1 should be the choice.

For four stones weighing 1 - 4, choose 2 * 4 - 1 = 7. For 7 stones weighing 1 - 5, choose 2 * 7 - 1 = 13.

Question: does the same thing apply if you have 7 stones weighing 2 - 6? Would 2 * 14 - 1 = 27 be the right choice?

[Prime]

It's always the obvious that sneaks up and bites you in the butt . To fix my missing cases, you need a weight that will help you distinguish them, which can only be done with a

7-lb weight. So, in general, a weight of 2*(low end of range) - 1 should be the choice.

For four stones weighing 1 - 4, choose 2 * 4 - 1 = 7. For 7 stones weighing 1 - 5, choose 2 * 7 - 1 = 13.

Question: does the same thing apply if you have 7 stones weighing 2 - 6? Would 2 * 14 - 1 = 27 be the right choice?

Great work! You have found correct reference weights for both 4 1 -- 4-lb rocks and 7 1 -- 5-lb rocks. I should add, it's the only reference weights that can work.

However, not quite the criteria for finding the reference weight. Note, I specified how many rocks were there. And I figured out the minimum necessary to make the problem solvable. So when you use that number in a formula for finding reference weight, you are relying on my giving you the optimal numbers. True criteria tells you both things: 1) How many rocks you need for a given weight range and 2) what should be the reference weight.

So, moving on, here is my solution with the proof for 7 rocks ranging from 1 to 5 pounds and just one reference weight. I'm giving the solution, but holding back on my criteria/formula for now.

Solution/Proof

Use balance scales to weigh the rocks one against another, and sort the rocks in order by weight. Take a 13 lb reference weight.

I. If all 7 rocks weigh the same:

1). For 5-lb rocks, 3 rocks is the minimum enough to outweigh the 13 lb reference.

2). For 4-lb rocks, 4 outweigh 13 lb.

3), 5 3-lb outweigh 13.

4). 7 2-lb outweigh 13.

5). And in case of all 1-lb rocks – all of them together weigh less than 13 lb.

II. When there are only two different rock weights:

1). 3 through 6 5-lb rocks: We can tell the heavier rocks are 5-lb each by weighing 3 of them against 13-lb. Then 5*3 - 13 = 2; 13 - 5*2 = 3. This way we can find or exclude the cases when the lighter rocks are 2 or 3-lb each. Beside that 2*5 + 4 > 13; whereas, 2*5 + 1 < 13. In this way we can tell whether the lighter rock(s) is 4 or 1-lb.

2). If there are 2 or less 5-lb rocks: 5 1-lb rocks will weigh the same as the 5-lb rock (that case is unique to 5 and 1). 4*2-lb + 5-lb = 13-lb (unique to 2 and 5). For 5 and 3-lb groups, the unique identifier is: 2*3-lb + 5-lb < 13-lb AND 3*3-lb + 5-lb>13-lb. For 5 and 4-lb: 4-lb*2 + 5-lb = 13-lb.

3). If the heavier rock is 4-lb and there are 4 or more of them: we can tell that the heavier rock is 4-lb since 4 of them weigh more than 13-lb reference. Thereafter, 4*4 - 13 = 3; 13 - 4*3 = 1. In this way we can identify 1 or 3-lb lighter rock, and the default 2-lb.

4). If there are 3 or less 4-lb rocks. Then if the lighter rocks are 1-lb, 4 of them weigh the same as one 4-lb, which is unique to 1 and 4. When the lighter rocks are 2-lb, two of them weigh the same as 4-lb. The same ratio exists between 2 and 1. However, in that case the total weigh of all 2 and 1-lb rocks would always be less than 13-lb, whereas total 4 with 2-lb combination would always weigh more. Finally, when the lighter rocks weigh 3-lb then 3*3 + 4 = 13 is a unique way to identify that case.

5) In case heavier rock(s) are 3-lb 1*3 = 3 OR 3*4 + 1 =13; then 2*3 = 3*2 OR 3*5 – 13 = 2 OR 2*5 + 3 = 13 can uniquely identify any combination of 3 and 1, or 3 and 2.

6) In the case of 2 and 1-lb rocks: 1*2 = 2 while the total is less than 13, and 2*6+1= 13 uniquely identify all the cases.

III. When there are 3 different rock weights it gets messier, but even more different ways of identification. Let’s list all 10 possible combinations with one of their characteristics:

1). 123 (1+2=3)

2). 124 (1+2<4)

3). 125 (1+2<5)

4). 134 (1+3=4)

5). 135 (1+3<5)

6). 145 (1+4=5)

7). 234 (2+3>4)

8). 235 (2+3=5)

9). 245 (2+4>5)

10). 345 (3+4>5)

Let’s consider the cases 1, 4, 6, and 8 where the lighter two stones are equal in weight to the heavier one.

The case (1) we can identify by 1*2 = 2, or if there are less than 2 1-lb rocks – 2*3 = 3*2 can be the identifier, or if there are also less than 3 2-lb rocks, then the combination 3*4 + 1 must be available, which uniquely identifies the case of (1).

The case (4) is identified by 1*3=3, or if there are less than 3 1-lb rocks, 3*3+4=13, or if there are also less than 3 3-lb rocks, then the case 4*3+1=13 is available.

In the case (6): 1*4=4; if less than 4 1-lb then 4*2+5=13; if less than 2 4-lb – 2*5+4>13 distinguishes it from other cases.

In the case (8): 2*5-lb + 3-lb = 13-lb, if less than 2 5-lb then 2*3=3*2, if less than 2 3-lb then 5*2-lb + 3-lb = 13-lb.

Now the cases 2, 3, and 5, where the lighter two rocks together weight less than the heavier one.

2*2=4; 2*2<5; and 3*2>5 can tell those cases apart. However if there is only one rock of the middle weight, then 1*4=4 tells case (2) from (3) and (5), and 1*2=2<3 distinguishes cases (3) and (5). If there are also less than 4 of the lightest stone then there must be at least 3 of the heaviest. In that case, 5*3>13 separates (3) and (5) from (2) and 13 - 5*2 = 3 may be used to distinguish between (3) and (5).

Finally for the cases 7, 9, and 10:

Comparing two lightest rocks against one heaviest: 2*2=4; 2*2<5; and 3*2>5. If there is only one of the lightest rocks, then two heaviest with one in the middle: 4*2+3<13; 5*2+4>13, thereafter case (9) from (10): 5*2+2<13, 5*2+3=13. If there is only one heaviest rock, then we can tell 4 in the middle from 3 by comparing 4 of them against 13-lb, then use 4*4 - 13 = 3 comparing that to the lightest rock to tell apart cases (9) and (10).

IV. When we have 4 different rock weights, all we have to do is to find which weight (1, 2, 3, 4, or 5) is missing.

Putting one of the lightest and one of the heaviest on one plate versus one of each second and third on another plate, will divide the possibilities as following:

If they weigh the same then it is 1234, or 1245, or 2345.

If the middle ones weigh more, it must be 1345, if it weighs less, it is 1235.

From the first three cases the 2345 one can be isolated by the 5-4<2 and the 1245 case can be separated by 4-2>1.

V. When there are 5 groups of rocks of different weight, we don’t need to do anything further, just assign their weights from 1 to 5.

If you take time to go through that solution to verify it, you could also get a notion on what was my criteria for finding reference weight and minimum number of rocks for a given weight range.

I belive the weight range 1 through 6 pounds is the maximum you can solve with just one reference weight. Past that you need more than one reference weight.

For an encore and to finish off this puzzle:

1).How many rocks (at the minimum) and what reference weight do you need to solve the range of 1 through 6 pounds with just one reference weight?

2).What is the largest weight range that could possibly be solved with 2 reference weights?

Is the original "Weghty thoughts" problem with 26 rocks in the 26-lb range solvable with 2 reference weights?

(No need to go through all permutations to prove solution. Just show genral reasoning and test for the cases when purported solution may fail.)

Edited October 15, 2008 by Prime

[Prime]

I shall post my solution to my puzzle, before I forget what it was.

So the trick is to choose reference weight higher than heaviest rocks in the range. There are two types of cases that reference weight must resolve.

1. It must work for the case when all rocks weigh the same.

For that it must take different number of rocks of different weights to exceed reference.

Example: For the weight range up to 5 lb we could take a reference weight R = 9 lb. We can tell 5 from 4, since 5*2 > 9 and 4*2 < 9; 4 from 3 and from 2, since 4*3 > 9, 3*3 = 9, and 2*3 < 9, and 2 from 1, since 2*5 > 9 and 1*5 < 9. For that there must be at least 5 rocks so that 2 lb * 5 >= R. However, reference 9 lb does not work for another situation, as explained below.

In general, if top weight in the range is W, then reference weight R criteria is:

W*n > R; (W-1)*n < R; (W-2)*(n+1) < R; and so on, if necessary, we could solve this and find that n > W^1/2 - 1, or something like that, but with small numbers it may be easier finding the right n by trial and error.

2. For another limiting case let’s consider all rocks but one are the heaviest rocks in the range.

Again, the reference weight will allow us to determine the weight of the heavy rocks. The main trick is to determine the weight of the light rock. Here the main criterion for the reference weight reveals itself. Consider two smallest (in absolute value) remainders R mod W. For example, 9 mod 5 = 4 or -1. Thus between the reference weight and sufficient number of 5 lb rocks we could tell 4 lb and 1 lb rocks. But we could not tell 2 lb from 3 lb -- they both fall between 1 and 4. A different remainder between reference and heavy rock can offer more reference points. Consider, 13 lb reference. The remainders with 5 are 2 and 3. So we could weigh 2 and 3 lb rocks against that. But now the remaining 1 and 4 lb weights fall into different categories. Namely, 1 < 3, 4 > 3. For the same reason we must avoid having reference to be a multiple of a sufficiently large rock weight. We would just lose additional reference points.

So this is why I think the range up to 6 lb is the highest, for which we could use just one reference weight. Consider reference weight which yields remainders |2| and |4| when divided by 6. Such as 22, for example, which allows to have additional reference points: 6*4 - 22 = 2; 22 - 6*3 = 4.

6------4------2------0

That is sufficient to tell apart all 5 weights under 6:

1<2; 2=2; 2<3<4; 4=4; 5>4.

The reason I chose 22, is because it is the first such reference that works for 5, 4, 3, and 2 as well:

5*5 - 22 = 3; 22 - 5*4 = 2 and 1<2; 2=2; 3=3; 4>3.

22 - 4*5 = 2 and 1<2; 2=2; 3>2.

22 - 3*7 = 1 and 1=1; 2>1.

Correspondingly, we need 22/2=11 rocks (so that we can tell all 1 lb from all 2 lb) to solve 6 with 1 reference weight. When weights are spread more evenly across the range, there are more relations to tell them apart.

If we took two reference weights, R1 and R2, then we have 4 references: R1, R2, R1+R2, and R2-R1. Then we could have a set of 4*2=8 remainders, which would enable us to tell apart 8*2+1=17 different weights. So theoretically, 2 reference weights may (or may not) solve the range of up to 18 lb. But not 26 lb range from the first "Weighty thoughts" puzzle. Although, 3 reference weights could go as far as solving 54 lb range.

Like in the original version of the weight problem dating back to 17th century, the powers of 3 proliferate. E.g., n reference weights seem to give (3ⁿ - 1)/2 combination reference weights. And the range which could possibly be solved with that 2*3ⁿ.

That's as far as I went with research of this problem. I did not find any actual solutions for 18 lb range with two reference weights. With 3 weights, or more we must switch from pounds to grams, or milligrams. It is possible even for some modest weight ranges, we would have to transport tiny rocks in railroad cars and then use those cars and locomotive as reference weights.