### 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

1. Aah a classic gem- one of my most favourite invariant problems ever.

When 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.

2. good that you could solve it.. I could not do it in 2 days :(

3. @Nikhil: The hint gave in the problem :)

4. The soln:
Suppose 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

5. Awesome solution.. Naren/Amol(MS) gave the same solution..

6. Well i was thinking..
Can u get there in infinite no of steps?

7. http://www.chiark.greenend.org.uk/~sgtatham/solarmy/

8. @Siddhant.

I 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?

9. 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

10. yep. Got it. I was not able to visualise it. Thanks.