Geometry

The golden ratio stops the fifth soldier

Soldiers fill a half-plane and advance by peg-solitaire jumps across a line. Two can send one of them a row forward, four two rows, eight three, twenty four rows — and no army at all, of any finite size, reaches the fifth. John Conway's proof weighs every square by a power of 1/φ, and the golden ratio's own equation x² + x = 1 is exactly what makes a forward jump cost nothing and the whole infinite army weigh exactly as much as the square it cannot reach.

Worth reading first: The rectangle that eats itself · The sum that fits in one square.

The rectangle that eats itself found the golden ratio φ=(1+5)/2\varphi = (1 + \sqrt5)/2 as the shape of a rectangle which, with a square removed, leaves a smaller copy of itself. In numbers that is the equation φ2=φ+1\varphi^2 = \varphi + 1, and dividing it by φ2\varphi^2 gives the same fact about the reciprocal x=1/φ=0.618…x = 1/\varphi = 0.618\ldots: x2+x=1x^2 + x = 1. Two successive powers of xx add up to the power before them. Every appearance of the golden ratio in this collection has been, in one way or another, that equation at work — in the inflation of tiles that never repeat, and in the numbers that come after the golden ratio, where it is the worst-approximable number of all.

This one is the strangest. It is a puzzle about soldiers on a chessboard that extends for ever, and the question is how far forward they can advance. John Conway posed and solved it in 1961, and the answer — they can reach the fourth row in front of their line and never the fifth, however many of them there are — is proved by giving every square a weight equal to a power of xx. The equation x2+x=1x^2 + x = 1 makes a step towards the goal cost exactly nothing, and the sum of a geometric series makes the whole infinite army weigh exactly 1. The fifth row is out of reach because the golden ratio balances the books to the last decimal place.

Soldiers that advance by jumping

The weight of the army, with the target on row 5. Pagoda weights x^d for target row 5; half-plane total 1.000000; first 5 rows 0.909830.
Fig. 1 Every square on or below the line weighted by x to the power of its distance in moves from the target on row 5, with x=1/φx = 1/\varphi. Added over the whole infinite half-plane the weights come to φ0=1\varphi^0 = 1, exactly the weight of the target.

The board is the infinite grid of squares, cut by a horizontal line. Any number of soldiers may be placed on squares on or below the line, at most one to a square, and they move as pegs do in peg solitaire: a soldier jumps over a soldier next to it, horizontally or vertically, into an empty square immediately beyond, and the soldier jumped over is removed. Every jump therefore costs one soldier. The question is which squares above the line a soldier can be brought to, and with how few soldiers.

The first row above the line is easy. Two soldiers in a column, the upper one touching the line, and the lower jumps over the upper into row 1. For row 2, four soldiers suffice and are needed, and for row 3, eight. Row 4 needs twenty. The pattern of doubling breaks there and the reason is not visible from the small rows. Then comes the surprise: no finite army, however large and however arranged, can put a soldier on row 5. Not a hundred soldiers, not a million.

The figure above holds everything the proof needs. Fix a target square on row 5. Give each square the weight xdx^d, where dd is the number of single steps — horizontal plus vertical — from that square to the target, and x=1/φx = 1/\varphi. The target itself weighs x0=1x^0 = 1. The squares just below the line in the target’s column are five steps away and weigh x5=0.090x^5 = 0.090; every step further away multiplies the weight by 0.6180.618. The weight of an army is the sum of the weights of the squares its soldiers stand on. The figure shades the squares by weight and writes the powers on the nearest ones.

A forward jump costs nothing

A jump never adds weight. Three jumps at distance 3: towards keeps the weight, across and away lose it.
Fig. 2 Three jumps at distance three to five from the target. A jump towards the target replaces x5+x4x^5 + x^4 by x3x^3, which is no change at all; a jump across the target’s column or away from it always loses weight.

What does a jump do to the army’s weight? Two soldiers disappear from their squares and one appears on a new square, and there are three cases, which the figure works through.

A jump towards the target: the jumper is d+2d + 2 steps from the target, the soldier it jumps over is d+1d + 1, and it lands dd steps away. The army loses xd+2+xd+1x^{d+2} + x^{d+1} and gains xdx^d. Since xd+2+xd+1=xd(x2+x)=xdx^{d+2} + x^{d+1} = x^d(x^2 + x) = x^d, the change is exactly zero. This is the one place the golden ratio enters, and it enters with no slack at all: any number smaller than 1/φ1/\varphi would make forward jumps lose weight, and any larger number would make them gain it.

A jump across the target’s column — horizontally, from one side to the other — starts d+1d+1 away, passes over a square dd away, and lands d+1d+1 away again. The army loses xd+1+xdx^{d+1} + x^d and gains xd+1x^{d+1}, a net loss of xdx^d. A jump away from the target, or any other jump, loses even more. So the weight of an army never increases, whatever jumps are made. It is a monovariant, in the vocabulary of puzzles: a quantity that only ever moves one way, and so divides the positions into those that can follow from a starting position and those that cannot, as the zero of a sandpile used a conserved count to decide which configurations can follow from which.

If a soldier ever reaches the target, the army’s weight at that moment is at least 1, since the target alone weighs 1. Because weight never increases, the army must have weighed at least 1 at the start.

The whole half-plane weighs exactly one

Now add up the weights of every square on or below the line. In the row immediately below the line, the square under the target is five steps away, its neighbours six, and so on outwards; the row weighs x5(1+2x+2x2+⋯ )=x5(1+2x1−x)x^5(1 + 2x + 2x^2 + \cdots) = x^5\left(1 + \tfrac{2x}{1-x}\right). Using 1−x=x21 - x = x^2 — the golden equation again — this is x5(1+2/x)=x5(1+2φ)x^5(1 + 2/x) = x^5(1 + 2\varphi), and 1+2φ=φ31 + 2\varphi = \varphi^3, so the row weighs x5φ3x^5\varphi^3. Each further row down weighs xx times the one above it, so the rows form a geometric series with ratio xx, and its sum multiplies by 1/(1−x)=1/x2=φ21/(1 - x) = 1/x^2 = \varphi^2.

The total is x5φ3φ2=x5φ5=1x^5\varphi^3\varphi^2 = x^5\varphi^5 = 1. The entire infinite half-plane, every square filled with a soldier, weighs exactly 1 — the weight of the one target square. The hero figure’s note gives the general case: with the target on row nn the half-plane weighs φ5−n\varphi^{5-n}, which is more than 1 for rows 1 to 4 and exactly 1 for row 5.

That closes the argument. A finite army fills only finitely many squares of the half-plane, and the squares it leaves empty have positive weight, so a finite army weighs strictly less than the whole half-plane: strictly less than 1. It would need to weigh at least 1 to reach the target. So it cannot. The equation x2+x=1x^2 + x = 1 was used twice, once to make forward jumps free and once to make the series sum to exactly the target’s weight, and it is the coincidence of the two that leaves no room at all. The same series, summed by the picture in the sum that fits in one square, is what makes the infinite army finite in weight.

Why it has to be this number

The weighting was not chosen for elegance. Suppose each square is weighted ydy^d for some number yy between 0 and 1, and ask what yy must be for the argument to work. A forward jump changes the weight by yd−yd+1−yd+2=yd(1−y−y2)y^d - y^{d+1} - y^{d+2} = y^d(1 - y - y^2). If 1−y−y21 - y - y^2 were positive, forward jumps would add weight and the monovariant would be lost; so yy can be at most the positive root of y2+y=1y^2 + y = 1, which is 1/φ1/\varphi. On the other hand, the half-plane’s total weight for a target on row 5 is y5(1+2y/(1−y))/(1−y)y^5(1 + 2y/(1-y))/(1 - y), which grows with yy; the smaller yy is, the lighter the half-plane and the stronger the conclusion. The best choice is therefore the largest permitted value, y=1/φy = 1/\varphi, and at that value the total is exactly 1. Any other value either breaks the monovariant or proves less. The golden ratio is not a weighting that happens to work; it is the only one that is sharp.

The same equation has turned up in this collection as a statement about reuse. In the search that reuses a point, golden-section search narrows an interval so that one of its two test points survives into the next round, and the condition for survival is exactly x2+x=1x^2 + x = 1: the piece that is cut away and the piece that is kept stand in the ratio the soldiers’ weights do. In three gaps and no more, points spaced round a circle by a fraction 1/φ1/\varphi of a turn always leave gaps of at most three sizes, the largest being the sum of the other two, and that additivity is the same equation again. Each is the fact that two consecutive powers of 1/φ1/\varphi add to the one before, read in a different setting — the Fibonacci recurrence in reverse, since Fn=Fn+1−Fn−1F_{n} = F_{n+1} - F_{n-1} and the powers of xx obey it exactly.

And the impossibility belongs to a family of arguments that the diagonal no unit measures began: a quantity that cannot change, or can change only one way, is set against a quantity the goal would need. The irrationality of φ\varphi was proved by a process that would have to shrink a whole number for ever; a second empty square proved a sliding puzzle unsolvable by a parity no move can alter. The soldiers’ weight is the continuous version of the same trick, and it is unusual among such arguments in that its invariant is irrational. A parity or a whole-number count could not do it, because the boundary between rows 4 and 5 is drawn by a sum that comes out to exactly 1 only because φ\varphi is the number it is.

Armies for the first four rows

The armies that reach rows 1 to 4. row 1: 2 soldiers, 1 jumps; row 2: 4 soldiers, 3 jumps; row 3: 8 soldiers, 7 jumps; row 4: 20 soldiers, 19 jumps
Fig. 3 For each target row, an army that reaches it — 2, 4, 8 and 20 soldiers — found by searching backwards from the target and replayed forwards jump by jump. The armies for rows 1 to 3 are the smallest the search finds.

The weight argument says nothing about rows 1 to 4, where the half-plane weighs more than 1 and there is room. For those rows armies have to be found, and the figure shows one for each. They were found by running the game backwards. Start with a single soldier on the target and repeatedly un-jump: replace a soldier by two soldiers on the two squares behind it in some direction, provided both are empty. Every forward game read backwards is a sequence of un-jumps, and a sequence that ends with every soldier on or below the line is an army that reaches the target. A search of increasing depth finds the smallest such army for rows 1, 2 and 3 in a fraction of a second: 2, 4 and 8 soldiers.

Row 4 is much harder. The smallest army has twenty soldiers, a result going back to Conway, and the backwards search needs several minutes and some fourteen million intermediate positions to find one, confined to a window nine squares wide and four deep. The figure’s fourth panel is that army. Each forward jump in it is checked as legal when it is replayed — a soldier jumping over an adjacent soldier into an empty square — and the last soldier left stands on the target.

The jump from 8 to 20 is where the doubling pattern breaks, and it breaks because the weights are getting tight. With the target on row 4 the half-plane weighs φ=1.618\varphi = 1.618, so there is spare weight, but much less than for lower rows, where the half-plane weighs φ2\varphi^2, φ3\varphi^3, φ4\varphi^4. An army for row 4 must be drawn from the heaviest squares, close to the target’s column, and those squares are crowded.

Twenty soldiers that waste nothing

The 20 soldiers that reach row 4, advancing. row 4: 20 soldiers, 19 jumps, 19 towards; weights start 1.000000000000 end 1.000000000000
Fig. 4 The 20-soldier army for row 4 at six moments of its 19 jumps, replayed and checked jump by jump. Every jump is towards the target, so the army never loses any weight.

Replaying the row-4 army jump by jump shows something the weight argument suggests but does not force. Measured with the target on row 4, the twenty soldiers weigh, to the precision of the arithmetic, exactly 1 — and every one of the nineteen jumps is a jump towards the target, so the weight never moves. The same is true of the eight-soldier army for row 3: it weighs exactly 1 for its own target, and all seven of its jumps are forward jumps. These smallest armies are perfectly economical. They start with precisely the weight they need and spend none of it.

The figure shows the army at six moments. The very first jump puts a soldier on row 1, straight up the target’s column, and for the next fifteen jumps the front barely moves: the army spends them rebuilding the column behind its leader, feeding soldiers in from the sides by horizontal jumps towards the centre — each a forward jump, because it shortens the distance to the target — and from below by vertical ones. A second soldier reaches row 2 at the seventh jump and the third row is reached only at the sixteenth. After seventeen jumps three soldiers are left, all in the target’s column, and the last two jumps carry one of them to row 4. Almost all the work is preparation; the advance itself comes at the end.

An army weighing exactly 1 that reaches its target cannot afford a single wasteful jump. It is a pleasing fact, though not a deep one: the search was free to find wasteful armies too, and found these. What it shows about the proof for row 5 is that the bound is not loose in spirit. Even for the rows that can be reached, the smallest armies sit exactly at the boundary the weights draw.

A thousand soldiers fall short

No finite army weighs enough for row 5. row 5 top-N: 1:0.090170, 2:0.145898, 5:0.291796, 10:0.450850, 20:0.631190, 50:0.854835, 100:0.953482, 200:0.991401, 500:0.999749, 1000:0.999996; bounds 1:2/2, 2:4/4, 3:8/8, 4:19/20
Fig. 5 The heaviest possible army of a given size for row 5 weighs less than 1 however many soldiers it has, approaching 1 only as the army fills the whole half-plane. For rows 1 to 4 the same count gives the fewest soldiers the weights allow, beside the number actually needed.

How close can a finite army come to weight 1 for row 5? The heaviest army of NN soldiers puts them on the NN squares nearest the target: one square at distance 5, three at distance 6, five at distance 7, and so on, since the squares at distance 5+k5 + k on or below the line number 2k+12k + 1. The figure plots the result. Ten soldiers weigh 0.451, a hundred weigh 0.953, a thousand weigh 0.999996. The curve climbs towards 1 and never reaches it, because what is left out — the squares beyond the thousandth — still has positive weight, however small.

The same count for rows 1 to 4 gives a lower bound on the size of an army: the fewest squares whose weights could add up to 1. For rows 1, 2 and 3 the bound is 2, 4 and 8, exactly the numbers needed. For row 4 it is 19, one short of the 20 actually needed. So the weights prove that row 4 needs at least nineteen soldiers and cannot prove that it needs twenty. The twentieth is forced by geometry the weights do not see — the nineteen heaviest squares are in the wrong shape to be played out — and establishing that requires a finer argument or a search.

What the weights cannot show

The figures compute everything they draw. The weights and sums are evaluated, the half-plane’s total is checked against φ5−n\varphi^{5-n}, every jump of every army is replayed and checked for legality, and every weight change is measured. But the central statement — that no finite army reaches row 5 — is not a computation at all. It is a proof about every army there could be, and no search could make it; the figures illustrate the two facts it rests on and the near-misses on either side.

The weights also say less than they seem to. A weight argument proves impossibility; it cannot prove possibility, since an army of sufficient weight may still be unable to advance, as the nineteen squares for row 4 show. And the argument is specific to the rules. If soldiers may also jump diagonally, a different weighting is needed and the boundary moves; in more dimensions it moves again — Henrik Eriksson and Bernt Lindström showed in 1995 that in dd dimensions the soldiers can reach row 3d−23d - 2 and no further, which is row 4 in the plane. The golden ratio is the weighting for the plane with orthogonal jumps, and its uniqueness belongs to that setting.

Still open: how few soldiers in higher dimensions

The plane is settled: rows 1 to 4 need 2, 4, 8 and 20 soldiers and row 5 cannot be reached. In three dimensions, where soldiers fill a half-space and the target can be up to seven layers above it, the smallest armies for the highest reachable layers are not known; the numbers grow quickly and the searches that settle the plane do not reach them. The weight arguments give lower bounds there too, and like the bound of 19 for row 4 they are not expected to be exact.

There is also the question of what “reach” should mean for infinite armies. The half-plane weighs exactly 1 for row 5, so the weight argument rules out finite armies with nothing to spare but says nothing about an army of infinitely many soldiers making infinitely many jumps. Whether row 5 can be reached in some limiting sense depends on how such an infinite sequence of moves is allowed to converge, and different formalisations give different answers; it is a question about the rules more than about the board.

Exactly one, and no further

Weight each square by xdx^d, where dd is its distance from the target and x=1/φx = 1/\varphi, so that x2+x=1x^2 + x = 1. A jump towards the target replaces xd+2+xd+1x^{d+2} + x^{d+1} by xdx^d and costs nothing; every other jump costs something; and the whole half-plane below the line weighs φ5−n\varphi^{5-n} for a target on row nn — exactly 1 for row 5. A finite army weighs less than the whole half-plane, so it weighs less than 1 and cannot reach row 5, though a thousand soldiers come within four millionths. Rows 1 to 4 can be reached with 2, 4, 8 and 20 soldiers, found here by searching backwards, and the smallest armies for rows 3 and 4 weigh exactly 1 and make only forward jumps: they spend nothing, because they have nothing to spare.

Shares its objects with

Essays that name at least two of the same things, and that neither author linked.

Named objects

A dashed tag is an object no other essay names yet.

Exhaustive searchFibonacci numbersGeometric seriesGolden ratioInvariant