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

- $|r_{i+1} - r_i| \le 1$,
- $|s_{i+1} - s_i| \le 1$,
- $\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