Why must there be two points of a space filling curve $f: N \times N \rightarrow \{ 1,...,N^2 \}$ with distance $N+1$?

Question

Question

Why is the following statement true?

Given a $N \times N$ grid and any space-filling curve $f: N \times N \rightarrow \{ 1,...,N^2 \}$ that covers the entire grid, the cells on the grid which are assigned the numbers $1$ and $N^2$ (the "first" and "last" numbers) have $L_\infty$-distance of at most $N-1$, and therefore there must exist two cells which are direct neighbors on the grid but have a distance of at least $N+1$ on the curve.

Background

The previous statement is my slightly paraphrased version of a short assertion/statement made in a paper about space-filling curves I am studying. The first part to me is clear:

• The cells assigned numbers $1$ and $N^2$ are at a distance of at most $N-1$ on the grid.

(Using Chebyshev/chessboard distance this is the farthest away two cells can be on the grid). But I do not see how it implies the second statement:

• There always exist two directly neighboring cells whose numbers differ by at least $N+1$.

The statement is worded such that the conclusion is obvious, but I must admit it is not obvious to me. The statement in question is in the very last paragraph of page labeled 8 in the full PDF available here. I will also note that for the first part of the statement the author uses the language "there is a path of length at most $N-1$" which seems strange to me and I cannot think of another way to interpret it besides the one I have stated.

Answer 1

Look at any simple path from the cell numbered $1$ to the cell numbered $N^2$, of length $\leq N$ (i.e., including $\leq N$ distinct cells), where the length of the path comes from the grid distance between the two points.You have at most $N-1$ "jumps" between adjacent cells on that path: if each jump has curve distance less than $N+1$, then the total curve distance $d$ is less than $(N-1)(N+1) = N^2-1$, so that you cannot go from $1$ to $N^2 > 1+ d$ (the curve value of the first and last point of the path).

I.e., at a very high-level, it can be seen as an averaging argument: if you have no more than $N-1$ jumps of length less than $N+1$, you cannot overall go from $1$ to $N^2$.