tag:blogger.com,1999:blog-4115025577315673827.post5449386124766496343..comments2020-03-23T00:01:28.359+05:30Comments on CSE Blog - quant, math, computer science puzzles: Pebble Placement Puzzle 2Pratik Poddarhttp://www.blogger.com/profile/11577606981573330954noreply@blogger.comBlogger4125tag:blogger.com,1999:blog-4115025577315673827.post-78239474487741792282015-06-11T19:08:29.540+05:302015-06-11T19:08:29.540+05:30Hey Tushar, I think proving that you cannot add pe...Hey Tushar, I think proving that you cannot add pebbles to one particular configuration, only ensures that the configuration is optimal, but it need not be optimum.Anonymoushttps://www.blogger.com/profile/18313929688691542872noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-41731728127846964262015-06-03T23:46:23.216+05:302015-06-03T23:46:23.216+05:30Ans: 2n - 1
Proof:
Put all the pebbles in the fi...Ans: 2n - 1<br /><br />Proof:<br /><br />Put all the pebbles in the first row and first column i.e. 2n - 1 pebbles (as the corner square is common). With this configuration, placing a pebble anywhere on the board results in a parallelogram. Therefore, we cannot place any other pebble anywhere on the board, giving the maximum pebbles as 2n - 1.Tushar Guptahttps://www.blogger.com/profile/05487504925714283385noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-50768848018137143612015-03-01T11:32:34.183+05:302015-03-01T11:32:34.183+05:30Ans: 2n – 1.
Proof:
Let the ith row have Ni pebble...Ans: 2n – 1.<br />Proof:<br />Let the ith row have Ni pebbles. Let the column in which jth of these lies be denoted by Cij (1 <= j <= Ni). Now if there exist 2 rows, each of which have 2 pebbles, equal number of columns apart, we’d get a non-degenerate parallelogram.<br />Let’s denote the total number of pebbles by N = ∑i Ni<br />Consider the differences Dij = Cij - Ci1 … (2 <= j <= Ni). Thus, across all the rows, we have ∑i (Ni – 1) = N-n such differences. Now, the distinct values which a difference can have, are 1,2,..,n-1 i.e. n-1 of them. Thus, if N >= 2n, we’d have 2 (among >=n) differences which are equal (by pigeon hole :P). Note that these 2 differences are not in the same row, as per their construction. Hence, we’d have a non-degenerate parallelogram. Now, we show with an example, that N=2n-1 is possible -> just completely fill the 1st row and the 1st column.<br />Anonymoushttps://www.blogger.com/profile/18313929688691542872noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-18822344383242335322015-02-02T01:06:47.241+05:302015-02-02T01:06:47.241+05:30What does it mean to have a non-degenerate paralle...What does it mean to have a non-degenerate parallelogram?stratton1101https://www.blogger.com/profile/16318592246622725096noreply@blogger.com