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?
Solution:
Highlight the part between the * symbols for the answer.
* Yes - in fact something stronger holds: some single weight sits on BOTH pans, so removing that one weight from each side keeps the balance.
Proof (Govind's): let the left pan hold m weights a_1 < ... < a_m and the right pan n weights b_1 < ... < b_n, with both sums equal to W < mn. Suppose no weight value appears on both pans - then all m + n weights are distinct positive integers, so their total is at least 1 + 2 + ... + (m+n) = (m+n)(m+n+1)/2. But (m+n)(m+n+1)/2 = (m+n)^2/2 + (m+n)/2 >= 2mn + (m+n)/2 > 2mn >= 2W, contradicting that the total is exactly 2W <= 2mn. (Note (m+n)^2 >= 4mn is the AM-GM rearrangement.) Hence some a_i = b_j; removing that pair leaves both sides lighter by the same amount - still balanced, and neither side is emptied (the hypothesis W < mn forces m, n >= 2).
Solution by Govind from the comments. *
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?
Solution:
Highlight the part between the * symbols for the answer.
* Yes - in fact something stronger holds: some single weight sits on BOTH pans, so removing that one weight from each side keeps the balance.
Proof (Govind's): let the left pan hold m weights a_1 < ... < a_m and the right pan n weights b_1 < ... < b_n, with both sums equal to W < mn. Suppose no weight value appears on both pans - then all m + n weights are distinct positive integers, so their total is at least 1 + 2 + ... + (m+n) = (m+n)(m+n+1)/2. But (m+n)(m+n+1)/2 = (m+n)^2/2 + (m+n)/2 >= 2mn + (m+n)/2 > 2mn >= 2W, contradicting that the total is exactly 2W <= 2mn. (Note (m+n)^2 >= 4mn is the AM-GM rearrangement.) Hence some a_i = b_j; removing that pair leaves both sides lighter by the same amount - still balanced, and neither side is emptied (the hypothesis W < mn forces m, n >= 2).
Solution by Govind from the comments. *
Let a_1 < a_2 < ... < a_m and b_1 < b_2 < ... < b_n be weight on left and right pan respectively such that
ReplyDelete\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.
Sorry. I missed some parts in the last paragraph.
ReplyDeleteThis 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.
How do you know that mC2 - 1 + m values produced from left pan are distinct? In general they aren't distinct!
DeleteLet a1 < a2 < ... < am and b1 < b2 < ... < bn be the weights on the 2 sides respectively. \sum ai = w = \sum bi.
ReplyDeleteFirst, 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. :)
This comment has been removed by the author.
ReplyDelete@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".
ReplyDeleteE.g. - Say weights on LHS are {1,2,3,4,100} then 1+2+3 !> 4+100
In fact we can make a stronger statement. There is atleast one weight common to both the sides. Let one side have n weights a1 < a2 < a3 < ... < an and the other side have m weights b1 < b2 < b3 < ... < bm. Now if we have ai = bj for any 1 <= i <= n and any 1 <= j <= m then we are done. If it is not then we arrive at a contradiction as shown further. If all ai s and bj s are distinct. Then we can say a1 + a2 + ... an + b1 + b2 + ... bm >= 1+2+....(n+m ) = ( n+m )^2/2 + (n+m)/2 > 2nm. Now this contradicts the fact that (a1 +a2+ ... an ) + ( b1 + b2 + ... bm) = W +W = 2W <= 2nm. Hence the proof
ReplyDeleteIn fact we can make a stronger statement. There is atleast one weight common to both the sides. Let one side have n weights a1 < a2 < a3 < ... < an and the other side have m weights b1 < b2 < b3 < ... < bm. Now if we have ai = bj for any 1 <= i <= n and any 1 <= j <= m then we are done. If it is not then we arrive at a contradiction as shown further. If all ai s and bj s are distinct. Then we can say a1 + a2 + ... an + b1 + b2 + ... bm >= 1+2+....(n+m ) = ( n+m )^2/2 + (n+m)/2 > 2nm. Now this contradicts the fact that (a1 +a2+ ... an ) + ( b1 + b2 + ... bm) = W +W = 2W <= 2nm. Hence the proof
ReplyDeleteWe can claim a stronger statement that there will be atleast a weight with a common mass between the the 2 pans. We can arrive at this conclusion by contradiction. Assume that the union of all the m weights ( a1 < a2 < ... am )on the left side and n weights ( b1 < b2 <.. bn ) on the right side are distinct. In that case, we have m+n distinct weights. so, their combined sum would be (a1+a2+...am) + ( b1+b2+...bn) >= 1+2+...m+n = (m+n)^2/2 + (m+n)/2 >= 2mn + (m+n)/2 > 2mn
ReplyDeleteNow, we also know that (a1+a2+...am) =( b1+b2+...bn) = W <= mn.
So, (a1+a2+...am) + ( b1+b2+...bn) <= 2mn, which is a contradiction. and hence there must be atleast one ai = bj.