tag:blogger.com,1999:blog-4115025577315673827.post6313595379115933207..comments2020-06-29T15:37:49.459+05:30Comments on CSE Blog - quant, math, computer science puzzles: Balancing Act PuzzlePratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger9125tag:blogger.com,1999:blog-4115025577315673827.post-23479212550076158612020-01-18T13:01:11.931+05:302020-01-18T13:01:11.931+05:30We can claim a stronger statement that there will ...We 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<br />Now, we also know that (a1+a2+...am) =( b1+b2+...bn) = W <= mn.<br />So, (a1+a2+...am) + ( b1+b2+...bn) <= 2mn, which is a contradiction. and hence there must be atleast one ai = bj.Govindhttps://www.blogger.com/profile/04133040088309286785noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-90938900583269111662020-01-16T11:25:47.516+05:302020-01-16T11:25:47.516+05:30In fact we can make a stronger statement. There is...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 proofGovindhttps://www.blogger.com/profile/04133040088309286785noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-1304730191629525162020-01-16T11:25:35.263+05:302020-01-16T11:25:35.263+05:30In fact we can make a stronger statement. There is...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 proofGovindhttps://www.blogger.com/profile/04133040088309286785noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-60202520117914238332016-04-02T21:06:06.212+05:302016-04-02T21:06:06.212+05:30@omkar: I didn't approve of this line "th...@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".<br />E.g. - Say weights on LHS are {1,2,3,4,100} then 1+2+3 !> 4+100Anonymoushttps://www.blogger.com/profile/03768098989316578636noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-12077754010115150742015-06-08T04:14:25.703+05:302015-06-08T04:14:25.703+05:30This comment has been removed by the author.Abhishek Mitrukahttps://www.blogger.com/profile/12695026970292358635noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-71476298477883031842015-03-06T23:08:27.213+05:302015-03-06T23:08:27.213+05:30Let a1 < a2 < ... < am and b1 < b2 <...Let a1 < a2 < ... < am and b1 < b2 < ... < bn be the weights on the 2 sides respectively. \sum ai = w = \sum bi.<br /><br />First, let's show an easy lemma : m,n >= 2.<br />To prove contradiction, let (w.l.g.) m=1. Then, w >= n(n+1)/2 >= n = mn > w => contradiction.<br /><br />Now, for the left pan, consider partial sums as follows:<br />a1, a2<br />a1+a2, a1+a3, a2+a3<br />a1+a2+a3, a1+a2+a4, a1+a3+a4, a2+a3+a4<br />.<br />.<br />.<br />w-am,......,w-a2,w-a1<br /><br />(to be concise, the pth partial sum in the qth line is [\sum(i = 1 to q+1) a_i] - a_{q+2-p})<br />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.<br />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. :)Anonymoushttps://www.blogger.com/profile/18313929688691542872noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-31686628975120958082014-10-25T17:16:15.950+05:302014-10-25T17:16:15.950+05:30How do you know that mC2 - 1 + m values produced f...How do you know that mC2 - 1 + m values produced from left pan are distinct? In general they aren't distinct!Yo!https://www.blogger.com/profile/15793407524283617413noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-47205867653907386442014-10-01T12:39:57.322+05:302014-10-01T12:39:57.322+05:30Sorry. I missed some parts in the last paragraph.
...Sorry. I missed some parts in the last paragraph.<br /><br />This produces mC2 - 1 + m distinct values for left pan and similarly nC2 - 1 + n distinct values for right pan.<br /><br />So in total, mC2 + nC2 + m + n - 2 values all of which ranges from 1 to W. <br />Note that (mC2 + nC2 + m + n - 2) > (m^2 + n^2)/2 > mn > W.<br />(applying PHP) we can infer that there exist two values which are equal and both of them cant come from same pan.Anonymoushttps://www.blogger.com/profile/07462007299438769456noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-85912039512672190512014-09-20T17:49:33.522+05:302014-09-20T17:49:33.522+05:30Let a_1 < a_2 < ... < a_m and b_1 < b_...Let a_1 < a_2 < ... < a_m and b_1 < b_2 < ... < b_n be weight on left and right pan respectively such that<br /><br />\sum(i = 1 to m) a_i = \sum(j in 1 to n) b_j = W<br /><br />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. <br /><br />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.Anonymoushttps://www.blogger.com/profile/07462007299438769456noreply@blogger.com