How Many Weights Are Needed to Balance Any Integer Weight on a Two-Pan Scale?

[Tony11235]

Say we have a scale for weighing objects, contains two pans that are balanced.

Given a collection of objects of known weight we weigh an object by putting it in one pan and putting known weights in the other pan until the scale balances. It may happen to be that there is no way to do this if we may place the given weights only in one pan.

If we can place the weights in both pans what is the minimum number of weights necessary to weigh an object whose weight is an unknown integer n? Then find a good lower bound.

This is for my algorithms analysis class. It is probably easy, but I'm having trouble getting started. Has anybody had this type of problem before? I thought I once heard that if n is odd, then it's 3, but I wouldn't know why.

 

[lippyka]

The problem can be solved by finding a way to represent any given number n as the sum of two numbers that can be achieved with a minimum number of weights. This can be done by using "greedy" algorithms, which try to get the best result using the least amount of resources.A good lower bound for this problem would be 3 weights. This is because if n is odd, then at least 3 weights are needed to represent it (one in each pan, plus one in the middle to balance it). Even if n is even, 3 weights may be enough, depending on the available weights (for example, if we have weights of 1, 2, and 4, then n=6 can be represented with only 3 weights: 4 in one pan and 2 and 1 in the other).