Source: Asked to me by Amol Sahasrabudhe (Morgan Stanley Quant Associate)
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!!