Trekking Into the Desert

(Posted by Polymath)  This page is part of the Advanced High School Math Project.

If you were going to lead an army into the desert, you'd have to be sure your supply lines were adequate.  Getting a soldier or two a mile into the desert isn't too tough, but at some point, if your goal is to get as deep into the desert as possible, you have to hand a soldier a canteen and let him walk as far as he can.  Traveling into the desert takes up resources, after all.

John H. Conway is well-known in the math world as a brilliant analyst of games.  He modeled the idea above into a simple puzzle that uses common game rules (this problem is sometimes called 'Conway's soldiers').  Consider a chess board or a go board (or any size grid) with a rectangular array of pieces on one side:

The pieces each represent a soldier, and they are trying to trek into the desert, which is the rest of the board.  They move (only horizontally or vertically) using the standard checker jump:  one piece jumps an adjacent piece, landing in a vacant square immediately beyond, and the piece that was jumped over is removed.  So after one move, the board might look like this (I left a ghost image of the piece that was removed):

So now this army of soldiers has made it one mile into the desert.  The question is, how far can the soldiers get with more moves?  As you get further and further, more soldiers disappear, so is there a limit?  Try it yourself with a board for a while if you want.  Traveling 2 miles is very easy, and 3 miles is also pretty easy.  4 miles is a little tough, but you'll get it eventually, I think.  5 miles?  Try for a while, but not too long.

Conway was able to turn this puzzle into a mathematical model and prove that it's impossible to make it 5 miles into the desert in a finite number of moves, no matter how many pieces you start with.  The proof below uses only math taught in a standard Algebra 2 course.   It is taken from this page, which also contains a Java applet that lets you try the game.  You can read the proof there, if you want, but I've made the diagrams clearer and included more steps of the algebra, so it might be easier to follow here.

I include the proof in these pages not because this is a significant mathematical result (it's interesting, but not especially significant), but because the way Conway models the game is one of the best examples I've ever seen of mathematically modeling a problem.  I, for instance, would never have come up with the model on my own, but it makes perfect sense once you see it.  People who do this kind of math for a living see mathematics behind all sorts of rule sets and patterns.  I include this proof because it's such a good example of that kind of thinking.

So the model is this:  assign each square of the board its own number (you'll see which numbers in a minute).  Add up all the numbers of the squares that contain a piece, ignoring all the empty squares, and call that sum the total value of that configuration of the board.

Assume for the moment that you have succeeded in moving a soldier 5 miles into the desert.  Assign that location a value of 1 (which, note, you could write as x to the zero power, and we'll define x in a minute).  From there, each time you move one square further away (horizontally or vertically), increase the exponent on x.

So the assignment of values (using x, which we still haven't defined, but will be a positive number) looks like this:

Not all the squares are filled in so the picture won't be too cluttered, but I'm sure you see the pattern.  The green values are in the locations of the original pieces.  Note, crucially, that if we really did succeed in moving a piece to the square with a 1, then the value of the board is at least 1 (it's more if there are still other pieces left on the board).

Now let's work on finding the right value of x to use.  Let's assume that every move we make to get that piece 5 miles out moves a piece closer to the goal location (the one with a 1).  A little experimentation will show that moving a piece further away will never be to your advantage in this game, so this assumption is reasonable.  The example below shows a before-and-after picture of such a move for a vertical move, but the math is the same for a horizontal move (a result of the brilliant model).

Again, the ghost image shows where piece was removed due to the upwards jump.  The key to defining x is that we want that jump to have no effect on the total value of the board.  Thus

Since we know that x is going to be non-zero, we can divide both sides by x^n, leaving the key equation

Solving that with the quadratic formula gives (as the only positive solution)

Stunningly, this is the reciprocal of the Golden Ratio, which doesn't seem to have any business at all showing up in this problem, yet...there it is.  This makes x approximately .618.  The exact value isn't actually very important, except to note that it is less than 1, and that it solves the equation above it.

From here, the proof turns into some algebra.  It looks complicated, but it's easier than it looks.

Since the total value of the board with a piece 5 miles out is at least 1 (we noted that above), and since every useful move doesn't change the value of the board (that's how we defined x), the board has to start with a value of at least 1.  In fact, let's simplify it a little:  let's just assume that we juuuuust barely made it to 5 miles with our very last piece, so that the final value of the board is exactly 1.  And since we don't know the size of our starting array of pieces, let's say that the array is infinite (that is, the pieces occupy every square on a half-plane).

Now, look closely again at the diagram that assigns the values to the squares, and imagine now that it holds an infinite array of pieces in their starting positions (the green positions).  The column just below the 1 contributes the following to the total value of the board

This is a geometric series with starting with x^5 as its first term (a) and x as the ratio between successive terms (r).  Since x<1, this series converges according to the formula a/(1-r).   But in a brilliant stroke of luck, 1-x (our denominator) happens to equal x^2;  this is because of the key equation above!  So we have

This, remember, is the contribution of the single column just below the 1.  The contributions of the two columns on either side of it produce very similar series, but they each start with x^6 instead, so they simplify to x^4 instead.  Similarly, the columns further out (again, two of each) simplify to x^5, then x^6, x^7, and so on.  This makes the total value of the starting board

We got that last simplification from yet one more infinite series starting with x^4.  And now for the amazing finale.  The final, unbelievable simplification.  In each step below, I'm either using basic algebra or I'm doing a simple substitution from the key equation above (1-x for x^2, to be precise)

Yes, folks, that's a 1.  All of those infinite series (a whole infinite series of infinite series, you'll note!) combine to make the total value of an infinite starting array of pieces equal to 1.  The exact value of the final board with a single piece on the 5-mile mark.  This means that any finite array of starting pieces has a value less than 1, and we already know that this total value can't increase (we defined x that way, remember?).  So...you'll never, ever, ever get a piece to that 5th row of squares no matter how many pieces you start with.

Is that amazing, or what?  Is that a great mathematical model, or what?

N. B.  In fact, it's too amazing to be a coincidence, I think.  A long time ago, I happened to find an expression similar to one occurring in this proof:  I'm pretty sure it was the one that looks like

x^3 + 2(x^4+...)

And I seem to remember that Poisson was associated with this expression (though I could be wrong).  Please leave a comment here with more information about this if you have it.