tag:blogger.com,1999:blog-4115025577315673827.post6313595379115933207..comments2019-07-15T17:16:38.146+05:30Comments on CSE Blog - quant, math, computer science puzzles: Balancing Act PuzzleUnknownnoreply@blogger.comBlogger6125tag: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+100Abhishek Guptahttps://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. :)Omkar Thakoorhttps://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.Satadip Sahahttps://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.Satadip Sahahttps://www.blogger.com/profile/07462007299438769456noreply@blogger.com