And today, just for comfort, instead of calling the soldiers soldiers, I will be calling them pegs.

Conway’s Soldiers is simple. There are an infinite number of pegs behind a line that divides the land between the pegs and the enemy. The pegs may jump another peg vertically or horizontally, but never diagonally.

A number, Φ, exists so that:

Select the target square, which, in our case is any square on level 5, and mark it with Φ^0, or just 1 for simplicity. All the other squares on the enemy territory will be marked with Φ^n, where n is the Manhattan distance to Φ^0. Also, for simplicity, Φ^0’s square will be called T, for target.

We can define a “score” for the configuration of the pegs. If two pegs are lined up to reach T after one jump, the score is Φ^1 + Φ^2. The score can change in three ways:

If a jump moves a peg towards T, the change in score is Φ^(n – 2) – Φ^(n – 1) – Φ^n. That is because The original pegs are at Φ^(n – 2) and Φ^(n – 1), and when the peg jumps, the jumped peg, Φ^(n – 1) is removed, hence subtracting the score, and Φ^(n – 2) moves to Φ^n, hence subtracting Φ^(n – 2) and adding Φ^n, which leads to 0.

If a jump doesn’t impact the value of the jumping peg, the score is changed by -Φ^(n – 1).

If a jump moves a peg away from T, the score is changed by -2Φ^(n + 1).

Therefore, the score can never increase.

Now, let’s think about it at a different approach. If there was a row of pegs right behind T, the score would be:

The score of a line of pegs n spaces away would be {Φ^(n – 1)} * (Φ + 2Φ^2 + 2Φ^3 + 2Φ^4 + …). Two things:

That means that if S(1) was the starting score for a board with T at level one, S(1) = 5 + 3Φ. Since the difference of two squares directly next to each other is logarithmically Φ, S(n + 1) = S(n) * Φ.

So:

S(2) = 3 + 2Φ

S(3) = 2 + Φ

S(4) = 1 + Φ

S(5) = 1

Now, let there be an end configuration score E, where E = 1 + ϵ, where 1 is the contribution of the peg on T, and ϵ the contribution of the peg behind the line. ϵ is positive, but can be as small as possible.

Now, for S(5), which is one, since ϵ > 0, E > S(5). But the score never increases, so therefore that must mean that S(5) ≥ E. We have reached a contradiction, since if a > b, then b ≥ a cannot be true.

Q.E.D.

Credits to Wikipedia for the information. For detail, go check out the page.

## One thought on “Behind the scenes of the proof that level 5 is impossible.”