There are some weights on the two sides of a balance scale. The mass of each weight is an integer number of grams, but no two weights on the same side of the scale share the same mass. At the moment, the scale is perfectly balanced, with each side weighing a total of W grams.
Suppose W is less than the number of weights on the left multiplied by the number of weights on the right.

Is it always true that we can remove some of the weights from each side and still keep the two sides balanced?

Rem: Ignore the trivial solution of removing all weights from both sides.

Source : CSE blog

Suppose there are n weights on the left, x1 - xn, and m weights on the right, y1 - ym.  All of the xi are distinct and all of the yj are distinct.

There are two cases to consider:

if some xi = some yj then we can remove all of the other weights and be left with a balanced scale. So in this case it's possible.

Suppose instead that all of the x and y are distinct.

If we add the weights from both sides, the smallest possible value is when the x's and y's are the numbers from 1 to (n+m), and this sum is (n+m)(n+m+1)/2. The sum of the weights on both sides is also 2W -- twice the sum of weights on either side. So:

2W >= (n+m)(n+m+1)/2

But we also have that W <= nm from the problem. We can combine:

nm >= W >= (n+m)(n+m+1)/4

4nm >= (n+m)(n+m+1)
4nm >= n^2 + 2nm + m^2 + (n+m)
0 >= n^2 -2nm + m^ + (n+m) = (n-m)^2 + (n+m)

But the term on the right is always positive unless n = m = 0, which is the degenerate solution we were to ignore, so there is no way to have a set of weights with no duplication that meets the constraints of the problem.

Therefore, if there is a set of weights that meets the terms of the problem, it must be the case that there is a weight with the same value on both sides, and that removing all but these two weights will preserve the balance. 

Posted by Paul on 2014-11-06 11:50:03