They'll Get There Eventually

Alright, the Sending Scouts Into The Desert problem has been up there with no solution for far too long, I suppose its time to post the solution. I'm going to proceed assuming that you have not already read the solution over at cut the knot and basically steal their derivation.

We will do the solution case by case first. For N=1, it clearly takes two pieces, one on the first line and one on the second line. For N=2 it takes 4 pieces, 3 on the first line and 1 on the second line. N=3 is a bit less trivial, but it won't take long to find that you need 8 pieces. So, so far the pattern goes 2,4,8, so it looks like N=4 should take 16. This is actually not the case, if you try it you won't be able to get to N=4 with less than 21 pieces (cut the knot says you only need 20, but I am reasonably certain that they have made some error, I cannot find anything better than 5 on the first line + 5 on the second line + 5 on the third line + 5 on the fourth line + 1 on the fifth line).

For N=5 the situation is even more interesting though, you cannot get to the fifth line with any finite number of pieces. To see this, let us consider a function that maps board configurations onto integers. We will later arrange the function so that legal moves do not increase the value of the function, so you cannot reach a higher-valued configuration from a lower-valued one, and use this to prove that we cannot reach the fifth line.

Let us assign a number to each square of the checkerboard, and the function will simply add up the numbers at the locations where we have pieces. We will arrange the numbers so that legal moves never increase the value of the function. Let us assume that somebody claims to have reached a particular square on the N=5 line of the board. We will assign that square a value 1. The four squares that neighbor it will be assigned a value x (we will fix x later). The next 8 neighboring squares will be assigned value x². The next 12 neighboring squares will have value x³ and so on out to infinity. More concisely put, we have the "master square" of value 1 and a square that is K spaces away (taxicab metric) from the master square has value x^K.

Let us consider a generic legal move, where piece A jumps piece B. There are three types of things that could have happened from this. First, A could have landed closer to the master square than it was before. In this case, A started on x^m, while B started on x^m-1, then A ended on x^m-2. To ensure that the function is nonincreasing, we need

x^m-2 ≤ x^m-1+x^m

The second type of move has piece A moving further away from the master square. In this case, A started on x^m and B on x^m+1, with A ending on x^m+2. For a nonincreasing function, we need to have

x^m+2 ≤ x^m+1+x^m

The third type of move has piece A staying the same distance from the master square. In this case, A started on x^m and B started on x^m-1, with A ending on x^m. So we need to satisfy

x^m ≤ x^m-1+x^m

This condition is satisfied easily if x is a nonnegative number.

Let us assume that the first condition is an equality (this means that moves toward the master square will conserve the value of the function, rather than decrease it). Dividing out x^m-2, this equation solves to 1-x-x²=0, meaning that

x=(√5 - 1)/2

There is another root, but it was discarded because x must not be negative. This x is actually the inverse of the golden mean. The last equation remaining is also satisfied by this choice of x, as you can confirm easily.

Now, supposing as before that the master square is on the fifth line, it is the place on the fifth line that somebody claims that they can reach using some path of legal moves. This configuration has value 1 (or more, if they had extra pieces lying around), so their initial configuration must also have value 1 or more. What is the maximum value you can get with a configuration of pieces in your base to start? You have at most 1 piece on x⁵, at most 3 pieces on x⁶, at most 5 pieces on x⁷, at most 7 pieces on x⁸, and at most 2n+1 pieces on xⁿ⁺⁵. Thus, the most value of pieces you can have is

Σ (2n+1) xⁿ⁺⁵

the sum running from 0 to infinity (actually this isn't really the most you can have, its actually more than you can have with any finite number of pieces, but its how much you could have with an infinite number of pieces).

We can simplify the sum to

2x⁶Σ nx^n-1 + x⁵Σ xⁿ
= 2x⁶ d/dx Σ xⁿ+x⁵Σ xⁿ

Of course, the sum &Sigma xⁿ is 1/(1-x) (since x is between -1 and 1) so we have

2x⁶/(1-x)²+x⁵/(1-x)

Now we use 1-x=x² (the quadratic that x solved) to simplify this to

2x²+x³
=x²(2+x)
=(1-x)(2+x)
=2-x-x²
=1

Therefore, no finite number of pieces can have total value 1, so no finite number of pieces can make a series of legal moves that ends with a piece five lines deep.

I suppose one can still imagine an infinite number of pieces doing it, but it will also take them an infinite number of moves, so its not clear that it really makes any sense to talk about such a thing.