All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic > Weights and Scales
Balancing weights (Posted on 2014-11-06) Difficulty: 3 of 5
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

No Solution Yet Submitted by Ady TZIDON    
Rating: 3.0000 (1 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution solution | Comment 1 of 2
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
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (3)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information