Conway's Soldiers (CheckerBoard Unreachable Line)
Source: Asked to me by Amol Sahasrabudhe (Morgan Stanley Quant Associate)
Problem:
An infinite checkerboard is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". A move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible.
Prove that there is no finite series of moves that will allow a soldier to advance more than four rows above the horizontal line.
I could get the correct direction in 5 min. Spent enough time on the problem but could not solve it. :( Give it a go! \m/
Update: Sep 07, 2010
Solution: Posted by Siddhant Agarwal (Senior Undergraduate, Elec IITB) in comments!!
Problem:
An infinite checkerboard is divided by a horizontal line that extends indefinitely. Above the line are empty cells and below the line are an arbitrary number of game pieces, or "soldiers". A move consists of one soldier jumping over an adjacent soldier into an empty cell, vertically or horizontally (but not diagonally), and removing the soldier which was jumped over. The goal of the puzzle is to place a soldier as far above the horizontal line as possible.
Prove that there is no finite series of moves that will allow a soldier to advance more than four rows above the horizontal line.
I could get the correct direction in 5 min. Spent enough time on the problem but could not solve it. :( Give it a go! \m/
Update: Sep 07, 2010
Solution: Posted by Siddhant Agarwal (Senior Undergraduate, Elec IITB) in comments!!
Aah a classic gem- one of my most favourite invariant problems ever.
ReplyDeleteWhen I came across it first, I too gave it a long try before finally seeing the solution.
Hint to people- Think of a weight function which would create an invariant.
good that you could solve it.. I could not do it in 2 days :(
ReplyDelete@Nikhil: The hint gave in the problem :)
ReplyDeleteThe soln:
ReplyDeleteSuppose u can reach y=5 for some x. WLG let x=0;
Define W(x,y)=[(1+sqrt(5))/2]^(-|x|+y)
We see that this is an invariant in the sense that any move can only decrease the total weight. (the number is the golden ratio coming from the fibonacci seq) Now we observe that
Total initial weight = W(0,5)
Hence in finite no of moves u cannot reach y=5
Awesome solution.. Naren/Amol(MS) gave the same solution..
ReplyDeleteWell i was thinking..
ReplyDeleteCan u get there in infinite no of steps?
Just read the article on wiki about this. It gave a link to a webpage which proves that you can reach y=5 in an infinite no of steps! Here is the link
ReplyDeletehttp://www.chiark.greenend.org.uk/~sgtatham/solarmy/
@Siddhant.
ReplyDeleteI am sorry but I am a bit confused. How is it possible that
A function f is decreasing. f(0) is alpha. f(finite) < alpha but f(infinite) = alpha?
Am I missing something?
Well f is not a strictly decreasing function. In fact f decreses if and only if, u make a move in the wrong direction. i.e. away from ur target (i.e sideways away from x=0, or going down). Here at each step f remains constant. Hence the final value of f = alpha
ReplyDeleteyep. Got it. I was not able to visualise it. Thanks.
ReplyDelete