Conway's soldiers cannot reach the fifth row
Statement
Soldiers occupy every lattice point with of the plane, one per point. A move: a soldier jumps over an adjacent soldier (horizontally or vertically) onto the empty point just behind, and the soldier jumped over is removed. Prove that no finite sequence of moves can bring a soldier to the point .
Hint
Give each lattice point the weight with (so ). Show that the total weight of the soldiers never increases and that the initial total weight is exactly .
Show solutionHide solution
Solution
Idea. Use a potential function with the golden ratio so that jumps toward the target keep the total unchanged and all other jumps decrease it.
Weights. Let , so . The weight of the point is with . The target has weight .
Initial weight. Using and , for ,
A move does not increase the weight. A move takes three consecutive points on a line and replaces soldiers on by one on . Along a line, the taxicab distance to is convex, so the triple has one of the forms:
- : change ;
- : change ;
- : change .
So the total weight never increases.
Conclusion. After any finite sequence of moves the weight is at most . Suppose a soldier reached . It contributes weight ; but infinitely many other soldiers remain, each with positive weight, so the total would exceed . Contradiction. ∎
Remark. The golden ratio is exactly the value making jumps toward the target neutral, which is why row can be reached but row cannot.
Lesson. Weight/potential functions: choose weights that make the dangerous move neutral and every other move a decrease.