The Pawn March Problem

Question

The Pawn March Problem is something I just came up with, and I thought it was interesting enough to share.

White has a line of $n$ pawns on an infinite chess board, all on rank 0 (negative positions are legal, and pawns may never make double moves). Black has a single rook on $ωω$. Assuming optimal play and that Black cannot move to a position where it is stalemate, what is the furthest rank to which White can get a pawn?

The first couple positions are rather easy. Let the first pawn start on $A0$, and each additional pawn start to the right $B0$, $C0$, $D0$,...

1. White's only move is to $A1$. Black moves to $Aω$. White moves to $A2$. Black takes $A2$, and we're done. $PM(1)=2$.

2. White's moves are symmetric, so wlog White moves $A1$. There are a couple of possibilities here, but Black's best move is to $Aω$. If White pushes the A-pawn, Black takes on $A2$ and eventually takes the B-pawn on $B2$. If White pushes the B-pawn, Black takes $A1$, White moves $B2$, Black moves $B1$, and the White pawn is eventually taken on $B3$. $PM(2)=3$.

3. It's trickier here. It's important to note that $1.A1$ is different than $1.C1$, because Black can move to $ω0$ but not $-ω0$. I might write a program later to attempt to solve it, but figured that the lovely folks here might be able to solve it or know of something like it that would give some insight.

Answer 1

A simple fact:

The reachable rank is unbounded.

Proof:

Let k be the rank we want to reach. A pawn triangle with tip at rank k takes k^2 moves to build. Actually, all we need is that it is a fixed finite number. White can sequence the moves m1,m2,... in such a way that the building triangle can only be attacked from the base. Choosing n large enough white can start building an arbitrary number of triangles repeating the same move m1 modulo an arbitrary spacing. As black needs 3 moves to disrupt any triangle (take a base pawn, back up, move laterally) they can damage only one third of those. Thus white can make the second move m2 at rouhghly 2/3 n1 sites. Of those black can disrupt one third. Therefore white can make the third move m3 at about 4/9 n1 sites and so on. As n and hence n1 can be chosen arbitrarily large the claim is proved.

An asymptotic bound:

The reachable rank is O(sqrt n log n)

Proof (sketch):

For large n black can bisect the white pawns for 4 moves per cut. Starting from behind: 1.target a not yet moved pawn near the file we want to cut at. 2. Whatever white does move to the square the pawn was or still is on. 3. catch the nearest pawn to the left or right. 4. back up. We can make roughly sqrt n cuts to get pieces of size roughly sqrt n. Focusing down one such piece of size x takes about 2x moves if we systematically target the least advanced pawn. If we do this one after the other always choosing the piece white has invested most moves in then white's best strategy is distributing the 2x moves black is busy with eradicating their current target evenly over the surviving pieces because the one living longest will be the one with the least moves. This piece will accumulate O(sqrt n x (1/sqrt n + 1/(sqrt n - 1) + ... + 1/2 + 1)) moves. So the given bound holds even if white were to get away with making all the moves of that piece with the same pawn.

It seems there is still room for improvement here, cf. last sentence of the spoilered bit. For example, black could make it a policy to immediately catch every runaway pawn (or group of runaways) once it is n^(1/4) ahead of its peers.

Because of that I suspect O(n^(1/4) log n) is also a valid bound, in fact, my gut feeling is O(log n) or perhaps slightly larger (something like O(log n log log n) or O((log n)^2)) because instead of making sqrt n pieces of size sqrt n it should be possible to either fix the size of pieces or make it grow much more slowly in n, though there are probably a few technicalities to be addressed. White will still have nothing better than distributing their moves evenly over the remaining pieces yielding a finite harmonic series as above (only a bit longer).

Answer 2

Here is an upper bound.

Black can easily prevent White to reach past rank n+2.

Here is how

I assume w is > n.

The rook only needs to move to rank 0, then capture whatever it can on that rank, then move to the next non-empty rank and repeat, in effect capturing all pawns from the back.
For the last pawn, the rook moves behind the pawn and capture it on the next move.

If a single pawn races forward it takes the rook 1 move to rank 0, n-1 moves to capture the stationary pawns and 2 moves to capture the last pawn.

If any other than the foremost pawn moves forward, it forces the rook to do a non-capturing move to change rank but at the same time White looses a move not advancing the foremost pawn. It only delays the last capture and doesn't help White to go further.

So White cannot do better than n+2.

This strategy is not optimal though.

First it takes more moves than the examples for n=1 and n=2.

Then, if one pawn races alone in front, it becomes vulnerable to a 3 or 4 move excursion by the rook to capture it, cancelling its progress.
On the other side, if other pawns move forward to protect it, then they need at least k(k+1)/2 moves to force k moves on the rook.
In both cases the pawns cannot progress anywhere near my upper bound.

A wild guess is that White cannot do better than O(sqrt(n)).