Clear Out Puzzle
Source: David Richards' Puzzle Collection
Problem:
A semi-infinite chess board (vary from zero to infinity in both dimensions) with counters in the three bottom left squares, as shown below.
How to move: If the squares above and to the right are free, a counter can be removed and replaced by two counters, one in the square above and one in the square to the right - as shown below
Prove that it is not possible to leave the three bottom left squares empty.
Update (March 07 2013)
Solution posted 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.
Problem:
A semi-infinite chess board (vary from zero to infinity in both dimensions) with counters in the three bottom left squares, as shown below.
How to move: If the squares above and to the right are free, a counter can be removed and replaced by two counters, one in the square above and one in the square to the right - as shown below
Prove that it is not possible to leave the three bottom left squares empty.
Update (March 07 2013)
Solution posted 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.
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.
ReplyDeleteMy 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/
Perhaps it is possible to formalize an infinite-move solution to this Clear Out Puzzle as well.
Thanks Sudeep for the solution.
DeleteComing 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.
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.
ReplyDeletecorrect solution takaki. thank you.
DeleteAssign a value to each cell of the board:
ReplyDeleteValue of cell (i,j) = 2^(-d) where d is the Manhattan distance of the cell from the (0,0) cell, the bottom-left cell.
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.
Now, note that any move keeps the value of the board same -- a counter is replaced by two counters of half the value.
Let us calculate the value of the board where all but the initial three cells are occupied.
Contribution of first column = 1/4 + 1/8 + .... = 1/2
Contribution of second column = 1/4 + 1/8 + .... = 1/2
Contribution of third column = 1/4 + 1/8 + .... = 1/2
Contribution of fourth column = 1/8 + 1/16 + .... = 1/4
Contribution of fifth column = 1/8 and so on...
Value of the board = 1/2 + 1/2 + 1/2 + 1/4 + 1/8 + ... = 2
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.
correct solution Rahul. Thank You.
DeleteSolution 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.
ReplyDelete