Level five of Conway’s Soldiers.

Before we start the boring post, there are already videos on the Conway’s Soldiers, so check them out if you don’t want to read this!

There is an infinite field, with infinite soldiers (as many as you need), but finite moves. Their job is to infiltrate over the line. It’s like checkers, except horizontally and vertically instead of diagonally. Only one jump may happen at a time. The jumped pieces are removed. The board:

With infinite soldiers and an infinite field, it seems like the soldiers can reach infinity. But no!

There is proof that level five is impossible. This was proved by the creator himself, John Horton Conway. The proof is on Wikipedia, but I’ll try to explain it myself:

There exists a number similar to phi where:

φ^2 = 1 – φ (I tried to copy a lowercase phi, but it all changes to the uppercase, so instead of the phi symbolised above, it will be φ).

In the other side to the soldiers, if we mark the target square (one square in level 5) with φ^0 (aka 1), and the surrounding squares with φ^n (where n is the Manhattan distance to the target square). There is a “score” of the configuration of the soldiers by totalling the value of the soldiers’ squares. So if there were two soldiers positioned to reach the target square on the next move, the configuration “score” would be φ^1 + φ^2.

There are three possible moves:

• The jump towards the target square changes the score by 0.
• The jump that changes nothing changes the score by -φ^(n+1).
• The jump further away from the target changes the score by -2φ^(n+1).

Therefore, the score will never increment, because φ is positive.

The configuration score of a row of soldiers directly underneath the target square is φ + 2φ^2 + 2φ^3 + 2φ^4 + 2φ^5 + 2φ^6 + …, and the score for a row of soldiers n spaces below the target square is {φ^(n – 1)} * (φ + φ^2 + φ^3 + φ^4 + …).

Remember how φ^2 = 1 – φ? New fact, where:

So is the target square is in level one, the score with no moves is: S(1) = {φ + 2(φ^2 + φ^3 + φ^4 + …)} * (1 + φ + φ^2 + φ^3 + …) Side note: the number in the score “function” is usually subscripted (small and lower), but WordPress won’t allow it so :v

Using the sigma function from above, we get S(1) = (φ + 2) * (1 + φ + 1) = (φ + 2)^2 = 5 + 3φ.

Since the difference between two conjoined squares is φ, to get the value of S(n), it is φ * S(n-1).

• S(2) = 3 + 2φ
• S(3) = 2 + φ
• S(4) = 1 + φ
• S(5) = 1

When a soldier reaches the target square T, the ending score is E = φ^0 + ε, where φ^0 is the contribution of the soldier on the target square, and ε is the contribution of the soldiers behind the line (our region). ε is small but always positive.

The starting configuration score is S(5) = 1, and the ending configuration score is E = 1 + ε, and this leads to a contradiction, since S(5) < E because ε is always positive, and the score never increases, so S(5) ≥ E, but a number cannot be smaller than another number that is smaller than or equal to that number.

But

hold

UP!!!!!!!!!!!!!!!!!!!!!!

Simon Tatham and Gareth Taylor proved that the impossible level 5 in Conway’s Soldiers is actually possible! Now if your first thought is, “how can that be true when Conway proved that it is impossible?” And you’re right. It uses up every soldier on the infinite board. We just have to tweak the rules and manipulate time a little bit.

If this doesn’t make sense, go to the link at the bottom, with all the links I used.

I’m not taking any credit for this solution, the credit goes to Simon Tatham and Gareth Taylor.

Think of making a large amount of moves in parallel, so using a full row of soldiers to get every one of them into level one. Not helpful, but it springs a new concept:

Doing a similar concept, but along one row. If a finite number of soldiers were in one row without any gap in between, the first one (far right) can be jumped by the second, the third by the fourth, the fifth by the sixth, and so one. First tweak! If an infinite number of moves can be made in finite time, that is legal. So the first jump in the second concept can be done at time t=0, the second jump at t=1/2, the third at t=3/4, the fourth at t=7/8, and so on, and at t=1, all jumps have been made, with time to spare. We made infinite moves in one second!

Now, we can only move one soldier at a time, so the idea of making large amounts of moves at once is scrapped, but if we take the “infinite moves, finite time” approach, we could do it in 1 second. We don’t know if t’s units of measurement is seconds, minutes or days, let’s call it arbunit (Arbitary Time Unit).

Another useful move that can be used is a reversed infinite sequence, or an ecneuqes etinifni. A clear end, but an uncertain beginning, and this strategy is very useful. We can visualise one soldier after consecutive jumps as we did in the second approach to the infinite sequence jump, but reversed. The two people created an awesome sequence which Gareth Taylor called a “whoosh”, most likely because it does look like a whoosh. In one row, the second jumps the first, fourth jumps third, and so on, until there are two soldiers at the left “end”, then the second part of the whoosh begins, where the leftmost soldier jumps over every soldier in the line until it finishes the rightmost jump, and is left alone after the whoosh.

The finite time? The first half of the whoosh can be done in one second, then the second half in another second, in the “keep halving and add, get 1” way, but in the second half, multiplying by two until reaching one arbunit.

Now, to advance further, Gareth Taylor and Simon Tatham created a “megawhoosh”, where it could literally turn a “quarter-plane” of soldiers into one soldier using a series of whooshes. The problem was that the megawhoosh only took the soldier to level two, so the two people started with a soldier at level three and worked their way backwards, doing one reverse jump, then reverse-whooshing both soldiers. If visualising it is hard, the visualisation is in the website linked down below. Move the left soldier left by reverse-jumping, then reverse-whoosh again.

Repeat infinitely, with the “halve every time” time management tool to fill the staircase of soldiers.

After the infinite whooshing, take every other soldier and whoosh them to the left, and then reverse-jump the soldiers to fill the gaps, which only takes a finite amount of steps in each column.

When that is done, the “quarter-plane” will be filled, and that is the reverse-megawhoosh. Now, to use the megawhoosh, do the exact same thing explained above, but in reverse.

Now, for the grand solution that Simon Tatham and Gareth Taylor devised!

1. Draw a line in the middle, where the final soldier will end up on the fifth level.
2. Megawhoosh the left half (not including the middle line) up to level three.
3. In the column that the line was drawn on, whoosh the column to level two, then jump the level three soldier to get to level four.
4. Megawhoosh the right half to level three, like the left half, then jump the soldier directly above the result of the second megawhoosh to reach level five.

Credits:

• https://www.chiark.greenend.org.uk/~sgtatham/solarmy/ by Simon Tatham and Gareth Taylor for the solution of level five being possible
• https://en.wikipedia.org/wiki/Conway%27s_Soldiers for the proof that level five is impossible
• https://www.youtube.com/watch?v=Y7hm0Xeicus by Vsauce2, for the easy explanation of Conway’s Soldiers

This was pain to write, but definitely not as much as Simon Tatham and Gareth Taylor when they had to find the manipulated solution to Conway’s Soldiers.

QED.

P.S. I want to post the gif for the solution provided by the two people who found the solution, but for legal reasons, I won’t. Check out the website for the animation, or this link.

Also, none of this information originates from me.