Maths WorkshopMaths problems with full solutions
Exercise 2236Combinatorics › Counting principlesOlympiadAdded 5 Nov 2026

Conway's soldiers cannot reach the fifth row

#weight function#potential#golden ratio#infinite board

Statement

Soldiers occupy every lattice point (x,y)(x,y) with y≤0y\le0 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 (0,5)(0,5).

Hint

Give each lattice point (x,y)(x,y) the weight σ∣x∣+(5−y)\sigma^{|x|+(5-y)} with σ=5−12\sigma=\frac{\sqrt5-1}2 (so σ2+σ=1\sigma^2+\sigma=1). Show that the total weight of the soldiers never increases and that the initial total weight is exactly 11.

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 σ=5−12≈0.618\sigma=\frac{\sqrt5-1}2\approx0.618, so σ2=1−σ\sigma^2=1-\sigma. The weight of the point P=(x,y)P=(x,y) is σd(P)\sigma^{d(P)} with d(P)=∣x∣+∣5−y∣d(P)=|x|+|5-y|. The target T=(0,5)T=(0,5) has weight 11.

Initial weight. Using ∑k≥0σk=11−σ=1σ2\sum_{k\ge0}\sigma^k=\frac1{1-\sigma}=\frac1{\sigma^2} and ∑x∈Zσ∣x∣=1+2σ1−σ=1+2σ\sum_{x\in\mathbb Z}\sigma^{|x|}=1+\frac{2\sigma}{1-\sigma}=1+\frac2\sigma, for y≤0y\le0,
W0=σ5⋅1σ2(1+2σ)=σ3+2σ2=1.W_0=\sigma^5\cdot\frac1{\sigma^2}\left(1+\frac2\sigma\right)=\sigma^3+2\sigma^2=1.

A move does not increase the weight. A move takes three consecutive points P,Q,RP,Q,R on a line and replaces soldiers on P,QP,Q by one on RR. Along a line, the taxicab distance to TT is convex, so the triple (d(P),d(Q),d(R))(d(P),d(Q),d(R)) has one of the forms:
- (n+2,n+1,n)(n+2,n+1,n): change σn−σn+1−σn+2=σn(1−σ−σ2)=0\sigma^n-\sigma^{n+1}-\sigma^{n+2}=\sigma^n(1-\sigma-\sigma^2)=0;
- (n,n+1,n+2)(n,n+1,n+2): change <0<0;
- (n+1,n,n+1)(n+1,n,n+1): change <0<0.
So the total weight never increases.

Conclusion. After any finite sequence of moves the weight is at most W0=1W_0=1. Suppose a soldier reached TT. It contributes weight 11; but infinitely many other soldiers remain, each with positive weight, so the total would exceed 11. Contradiction. ∎

Remark. The golden ratio is exactly the value making jumps toward the target neutral, which is why row 44 can be reached but row 55 cannot.

Lesson. Weight/potential functions: choose weights that make the dangerous move neutral and every other move a decrease.