tag:blogger.com,1999:blog-4115025577315673827.post3025620702886431637..comments2019-08-23T16:42:38.981+05:30Comments on CSE Blog - quant, math, computer science puzzles: Clear Out PuzzleUnknownnoreply@blogger.comBlogger7125tag:blogger.com,1999:blog-4115025577315673827.post-45147965582906364582013-03-07T04:20:55.979+05:302013-03-07T04:20:55.979+05:30Solution provided by Sudeep Kamath (PhD Student, U...Solution provided by Sudeep Kamath (PhD Student, UC at Berkeley, EE IITB Alumnus 2008), Takaki and Rahul in comments! All solutions are essentially the same. Interesting discussion and links by Sudeep. Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-74104591796362961192013-03-07T04:18:42.634+05:302013-03-07T04:18:42.634+05:30Thanks Sudeep for the solution.
Coming up with a...Thanks Sudeep for the solution. <br /><br />Coming up with an infinite move solution is an interesting problem indeed. The Tatham and Taylor solution for Conway's Soldiers is non-intuitive and brilliant. Thanks for the links.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-50186504850331359282013-03-07T04:09:25.329+05:302013-03-07T04:09:25.329+05:30correct solution Rahul. Thank You.correct solution Rahul. Thank You.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-43739657241166600502013-03-07T04:08:43.977+05:302013-03-07T04:08:43.977+05:30correct solution takaki. thank you.correct solution takaki. thank you.Pratik Poddarhttps://www.blogger.com/profile/11577606981573330954noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-62879226351112650072013-03-05T00:17:24.430+05:302013-03-05T00:17:24.430+05:30Assign a value to each cell of the board:
Value o...Assign a value to each cell of the board:<br /><br />Value of cell (i,j) = 2^(-d) where d is the Manhattan distance of the cell from the (0,0) cell, the bottom-left cell. <br /><br />At any point in time, define the value of the board as the sum of the values of cells containing a counter, e.g., in the beginning, the value of the board = 1 (for the bottom-left cell) and 2*0.5 (for the other two cells) = 2.<br /><br />Now, note that any move keeps the value of the board same -- a counter is replaced by two counters of half the value. <br /><br />Let us calculate the value of the board where all but the initial three cells are occupied. <br /><br />Contribution of first column = 1/4 + 1/8 + .... = 1/2<br />Contribution of second column = 1/4 + 1/8 + .... = 1/2<br />Contribution of third column = 1/4 + 1/8 + .... = 1/2<br />Contribution of fourth column = 1/8 + 1/16 + .... = 1/4 <br />Contribution of fifth column = 1/8 and so on...<br /><br />Value of the board = 1/2 + 1/2 + 1/2 + 1/4 + 1/8 + ... = 2<br /><br />Hence the value of the board in any state in which the initial three cells are unoccupied will be less than 2. Since moves preserve the value of the board, any such state is not reachable.Rahulhttps://www.blogger.com/profile/08776745258307564576noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-47050401791664655502013-03-04T18:25:22.288+05:302013-03-04T18:25:22.288+05:30Define the weight of the square with coordinate (x...Define the weight of the square with coordinate (x, y) as 2^(-x-y). The total weight of squares with counters on them is invariant under the move. The starting total weight is 1 + 1/2 + 1/2 = 2. The total weight of all the squares except the bottom left three is also 2. A finite sequence of moves produces a configuration with a finite number of counters and any such configuration which doesn't cover the initial three squares must have weight less than 2. Therefore such a sequence of moves doesn't exist.takakihttps://www.blogger.com/profile/01295985839611242377noreply@blogger.comtag:blogger.com,1999:blog-4115025577315673827.post-92049054171948270592013-03-04T03:58:35.015+05:302013-03-04T03:58:35.015+05:30I have a hidden agenda to answer this question. Le...I have a hidden agenda to answer this question. Let the rows and columns be numbered as 0,1,2,3,... The state of the board can be represented as a bivariate polynomial in variables x and y as follows. For every counter present at (k,m), the polynomial has a term x^k * y^m with co-efficient 1. The starting state of the board is represented by 1+x+y. Any legal move changes the state by replacing a monomial x^k * y^m with the sum of two monomials x^k * y^m (x+y). Now, note that for x = y = 1/2, the initial state polynomial sums to 2 and the sum for the complete board is 4. Then, if the three bottom left squares are empty, then the entire rest of the board must be filled by counters which cannot be done in any finite number of moves.<br /><br />My hidden motive was of course, the problem of Conway's Soldiers, http://en.wikipedia.org/wiki/Conway%27s_Soldiers which is proved by a similar invariant. What I want to popularize is the solution by Tatham and Taylor that reaches the fifth row in an infinite number of moves. There are lot of subtleties in what an infinite-move solution even means and this nice page with animations explains it very well (with whooshes and megawhooshes!): http://www.chiark.greenend.org.uk/~sgtatham/solarmy/<br /><br />Perhaps it is possible to formalize an infinite-move solution to this Clear Out Puzzle as well.Sudeephttps://www.blogger.com/profile/13841069661156497844noreply@blogger.com