The golden ratio stops the fifth soldier
Worth reading first: The rectangle that eats itself · The sum that fits in one square.
The rectangle that eats itself found the golden ratio as the shape of a rectangle which, with a square removed, leaves a smaller copy of itself. In numbers that is the equation , and dividing it by gives the same fact about the reciprocal : . Two successive powers of 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 . The equation 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 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 , where is the number of single steps — horizontal plus vertical — from that square to the target, and . The target itself weighs . The squares just below the line in the target’s column are five steps away and weigh ; every step further away multiplies the weight by . 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
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 steps from the target, the soldier it jumps over is , and it lands steps away. The army loses and gains . Since , 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 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 away, passes over a square away, and lands away again. The army loses and gains , a net loss of . 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 . Using — the golden equation again — this is , and , so the row weighs . Each further row down weighs times the one above it, so the rows form a geometric series with ratio , and its sum multiplies by .
The total is . 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 the half-plane weighs , 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 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 for some number between 0 and 1, and ask what must be for the argument to work. A forward jump changes the weight by . If were positive, forward jumps would add weight and the monovariant would be lost; so can be at most the positive root of , which is . On the other hand, the half-plane’s total weight for a target on row 5 is , which grows with ; the smaller is, the lighter the half-plane and the stronger the conclusion. The best choice is therefore the largest permitted value, , 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 : 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 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 add to the one before, read in a different setting — the Fibonacci recurrence in reverse, since and the powers of 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 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 is the number it is.
Armies for the first four rows
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 , so there is spare weight, but much less than for lower rows, where the half-plane weighs , , . 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
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
How close can a finite army come to weight 1 for row 5? The heaviest army of soldiers puts them on the 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 on or below the line number . 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 , 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 dimensions the soldiers can reach row 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 , where is its distance from the target and , so that . A jump towards the target replaces by and costs nothing; every other jump costs something; and the whole half-plane below the line weighs for a target on row — 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.
- The largest amount two coins cannot pay — both name exhaustive search, fibonacci numbers, golden ratio
- The rectangles a square can be cut into — both name exhaustive search, golden ratio, invariant
- A chaotic map that always comes back — both name fibonacci numbers, golden ratio
- A game decided before it starts — both name exhaustive search, invariant
- A growth rate no step contains — both name fibonacci numbers, golden ratio
- A ring that no pairing can break — both name exhaustive search, invariant
Named objects
A dashed tag is an object no other essay names yet.
Exhaustive searchFibonacci numbersGeometric seriesGolden ratioInvariant