Existence of some lattice path connecting all given lattice paths

Question

My daily work concerns analysis on metric spaces and some time ago it turned out that the problem I am dealing with boils down to a certain combinatorial problem. I've checked a lot of examples and it seems to be true but I don't know much about combinatorics and combinatorial tricks, so I hope the community is able to advise me on how I could attack this problem. I suppose it might be a variation of some well-known problem but I have no experience in this area.

Let $N \in \mathbb{N}$ and $L = \left\{(i, j) \in \mathbb{Z}^2 \,\colon \, i = 0, \ldots, N, \; j = -1, 0 ,1\right\}$. The set $L$ is the lattice on which we will build lattice paths.

Let $\mathcal{P}$ be the set of all lattice paths on $L$ starting from $(0, -1)$ and ending in $(N, 1)$ with steps in $S = \left\{(1,1), (1,-1), (1, 0)\right\}$ i.e. only "east-like" directions $\nearrow$ $\searrow$ $\rightarrow$ are available. Of course given points $(0, -1)$, $(N, 1)$ represent left-down and right-up corner of $L$, respectively.

Let $n \in \mathbb{N}$ and $p_1, \ldots, p_n \in \mathcal{P}$. Here $n$ is independent from $N$ fixed above. Let us denote these sequences as $p_i = \left(p_i^k\right)_{k=0}^N$ for $1 \le i \le n$ where $p_i^k \in L$. Of course $p_i^k = (k, q_i^k)$ for some $q_i^k \in \left\{-1, 0, 1\right\}$.

Let us give one simple requirement for the paths $p_1, \ldots, p_n$. Namely, two adjacent paths in this sequence (i.e. $p_i$ and $p_{i+1}$) are close to each other in the sense that $$\forall i \; ||p_i - p_{i+1}||_\infty \le 1$$ or equivalently $$\forall i \;\forall k \; |q_i^k - q_{i+1}^k| \le 1.$$

Then the thesis is as follows.

There exists a sequence $Q = \left(\left(r_i, s_i\right)\right)_{i=1}^M$ with $r_i \in \left\{0, \ldots, N\right\}$, $s_i \in \left\{1, \ldots,n\right\}$ and $(r_i, 0) \in p_{s_i}$ such that

1. $|r_{i+1} - r_i| \le 1$,
2. $|s_{i+1} - s_i| \le 1$,
3. $\bigcup_{i=1}^M \left\{s_i\right\} = \left\{1, \ldots,n \right\}$.

It means that moving on the line $y=0$ only through adjacent (distance $\le$ 1) points of lattice $L$ (item $1$) and adjacent paths in sequence $(p_1, \ldots, p_n)$ (item $2$) we can find a "path" which visits all the paths $p_i$ (item $3$).

I wrote a program in Python which finds sample sequence $Q$ from randomly generated paths $p_i$ but at the moment I don't see how to prove that the sequence $Q$ always exists. I encourage you to take a look at the program on GitHub to do some tests.

In the program, string $(m_1, m_2) \colon \, [s_1, \ldots, s_k]$ means $(m_1, m_2) \in p_{s_i}$ for all $i = 1, \ldots, k$. You can freely modify parameters $N$ and $n$ (lines $3, 4$ in the code).

https://github.com/mdybowski/Lattice_path/blob/main/Lattice_path.py

Answer 1

Let us draw a checkered table with $N$ columns and $n$ rows, such that the cell $(i,j)$ (that is, the one in the $i$th row and the $j$th column) contains the number $q_i^j$. Paint all cells with zeroes in black, all others are white. The conditions on paths claim that any two cells having a common edge contain numbers differing by at most $1$.

The desired sequence corresponds to a path along black cells, starting at the $1$st (i.e. the top) row and ending in the $n$th (the bottom) row, and passing each time from a cell to a cell adjacent to it either horizontally, or vertically, or diagonally (call this an admissible step).

Assume that such path does not exist. Augment the table with the $0$th row which is completely black. Consider the set $F$ of all black cells reachable from the $0$th row by admissible steps. This set contains no cells in the $n$th row.

If we remove the cells of $F$ (along with the boundaries!) from the table, it falls down into several components, but the bottom row is in one component $G$. The bounrary of $G$ consists of some parts of the borders of the table, and a path $m$ (along the cell borders) from the left to the right borders. All cells in $Q$ having at least one point on $m$ are white. Those cells intersecting $m$ contain a path along white cells going from the left border to the right one, and passing only horizontally or vertically on each step.

We now claim that such path cannot exist. Indeed, any white cell contains either $1$ or $-1$. Any two white cells adjacent horizontally or vertically share the same number, as their numbers differ by at most $1$. So all cells in this path share the same number. But all (white) cells in the left column contain $-1$s, while all (white) cells in the right column contain $1$s. A contradiction.

Remark. The same argument works if you have similar paths on $\{0,1,\dots,N\}\times\{-a,-a+1,\dots,b\}$ with $a,b>0$. Even in this setting you can find a desired path. It separates white cells with negative values from those with positive values.