Quant, Math & Computer Science Puzzles for Interview Preparation & Brain Teasing
A collection of ~225 Puzzles with Solutions (classified by difficulty and topic)

Sep 19, 2014

Balancing Act Puzzle

Source: Australian Mathematical Society Gazette Puzzle Corner 35

Problem:
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, but not all, of the weights from each side and still keep the two sides balanced?



6 comments:

  1. Let a_1 < a_2 < ... < a_m and b_1 < b_2 < ... < b_n be weight on left and right pan respectively such that

    \sum(i = 1 to m) a_i = \sum(j in 1 to n) b_j = W

    Now for the left pan, consider "Proper" (meaning its value is not equal to W) partial sums of the form \sum(i = p to q) a_i such that 1 <= p < q <= m (There are mC2 - 1 many) along with individual a_i (m many) values.

    This produces mC2 - 1 + m distinct values for left pan all of which ranges from 1 to (m^2 + n^2)/2 > mn > W , (applying PHP) we can infer that there exist two values which are equal and both of them cant come from same pan.

    ReplyDelete
  2. Sorry. I missed some parts in the last paragraph.

    This produces mC2 - 1 + m distinct values for left pan and similarly nC2 - 1 + n distinct values for right pan.

    So in total, mC2 + nC2 + m + n - 2 values all of which ranges from 1 to W.
    Note that (mC2 + nC2 + m + n - 2) > (m^2 + n^2)/2 > mn > W.
    (applying PHP) we can infer that there exist two values which are equal and both of them cant come from same pan.

    ReplyDelete
    Replies
    1. How do you know that mC2 - 1 + m values produced from left pan are distinct? In general they aren't distinct!

      Delete
  3. Let a1 < a2 < ... < am and b1 < b2 < ... < bn be the weights on the 2 sides respectively. \sum ai = w = \sum bi.

    First, let's show an easy lemma : m,n >= 2.
    To prove contradiction, let (w.l.g.) m=1. Then, w >= n(n+1)/2 >= n = mn > w => contradiction.

    Now, for the left pan, consider partial sums as follows:
    a1, a2
    a1+a2, a1+a3, a2+a3
    a1+a2+a3, a1+a2+a4, a1+a3+a4, a2+a3+a4
    .
    .
    .
    w-am,......,w-a2,w-a1

    (to be concise, the pth partial sum in the qth line is [\sum(i = 1 to q+1) a_i] - a_{q+2-p})
    It's easy to see that the partial sums in each line, are strictly increasing, and also that the smallest partial sum in a line is strictly greater than the largest partial sum in the previous line. Thus, all the partial sums (none equal to w) are distinct and there are (2+3+4+...+m) = m(m+1)/2 - 1 of them altogether. Similarly, we consider n(n+1)/2 - 1 distinct partial sums from the right pan.
    total number of partial sums = m(m+1)/2 - 1 + n(n+1)/2 - 1 >= (m^2 + n^2)/2 by the lemma. Further, (m^2 + n^2)/2 >= mn > w using RMS-GM inequality. Thus since the partial sums are more than w in number, each being smaller than w, 2 of them must be equal (which can't be in the same pan as shown earlier). Thus we can take out the weights corresponding to these partial sums. :)

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. @omkar: I didn't approve of this line "the smallest partial sum in a line is strictly greater than the largest partial sum in the previous line".
    E.g. - Say weights on LHS are {1,2,3,4,100} then 1+2+3 !> 4+100

    ReplyDelete