1

This is an extension of How to weigh up to 100kg with 5 weights.

Each month, the sugar delivery man delivers a number of bags of sugar to your shop. The bags are pre-weighed in increments of 1kg and range from 1kg to 200kg. However, although his sugar is the cheapest around, the sugar delivery man is both lazy and careless so he often he forgets to label the individual bags or labels them incorrectly.

1) Using only 5 weights, how can you label each bag of sugar with its correct weight?

2) If he delivers the same total weight W and number of bags N each month and you can use the delivered bags for measurements as well as your weights, what is the minimum number of weights you will need to guarantee you can correctly label each bag?

Community
  • 1
Briguy37
  • 1,579

1 Answers1

1

Since there has been no response I'll attempt to answer my own question, although the second part is still incomplete at this point.

1) One possible combination of weights is 2, 6, 18, 54, and 162. From these weights you can correctly determine any weight as long as it is below 243 pounds...

2) Let's take the simple case of $N = 1$. On the right is the set of weights you will need:

$$W <= 3^0 : ()$$ $$W <= 3^1 : (2*3^0)$$ $$W <= 3^2 : (2*3^0, 2*3^1)$$ $$W <= 3^x : (2*3^0, 2*3^1, .., 2*3^{x-2}, 2*3^{x-1})$$


Now let's move to $N=2$. You don't need any weights until you reach the $W=5$ case, in which case we add our 2kg weight, which can easily handle that case.

$W=9$ is the first interesting case for 1 weight, with the possible combinations (8,1), (7,2), (6,3), & (5,4). (8,1) and (7,2) will become obvious when the lighter bag is weighed against our 2kg weight. However, putting our weight on lighter bag's side will allow us to tell the difference between (6,3) & (5,4). $W=10$ you can do in the same manner.

However, for $W=11$ you cannot tell the difference between (8,3) and (7,4), so that is where we need 2 weights: 2kg, 6kg. Again, the first interesting case is when the average weight surpasses the total weights we have, or 2*8 + 1 = 17kg. Also, we again reach the first unmeasurable case when there are 2 possible cases where both bags are above the total weights we have, and their weights differ by more than the total weights we have. This case turns out to be $W=29$, where the cases we can't differentiate between are (9,20) & (10,19).

Having understood the pattern, it clearly depends on the total weight $w$ of our $x$ weights. This turns out to be $$w = 3^x - 1$$

We can now say that for $N=2$, $x$ weights can measure up to $W=3w+4=3^{x+1}+1$


I have not yet considered the N > 2 case, so more may come if someone else doesn't beat me to it...

Briguy37
  • 1,579
  • Clearly we need some systematic framework to avoid descending into an unending discussion of special cases. The most likely approach is induction, based on showing the weight of one "new" bag can be determined or otherwise eliminated, reducing to a smaller N. – hardmath Nov 02 '13 at 12:46