Recientemente me necesitaba algo como lo siguiente:
Deje $(a_0, a_1, \dots, a_m)$ $(b_0, b_1, \dots, b_n)$ dos secuencias finitas de números enteros, no necesariamente de la misma longitud, con el mismo principio y el final (es decir, $a_0 = b_0$ e $a_m = b_n$) y ambos con la propiedad de que la diferencia entre dos los sucesivos elementos de la secuencia siempre es $1$ o $-1$, es decir $|a_k - a_{k+1}| = 1$ for $k=0,\dots,m-1$ y lo mismo para el otro de la secuencia. Además, permitir a cada secuencia sólo se tienen elementos entre el principio y el fin. Para ser más precisos, la demanda $$\min(a_0,a_m) < a_k < \max(a_0,a_m)$$ for $k=1,\dots,m-1$ y lo mismo para la otra secuencia.
Es siempre posible construir una secuencia finita $$ ((\alpha_0,\beta_0), (\alpha_1,\beta_1), \dots, (\alpha_r,\beta_r)) $$ de pares de índices tales que las siguientes condiciones:
- $0 \leq \alpha_k \leq m$ $k=0,\dots,r$
- $0 \leq \beta_k \leq n$ $k=0,\dots,r$
- $(\alpha_0,\beta_0) = (0,0)$
- $(\alpha_r,\beta_r) = (m,n)$
- $|\alpha_k - \alpha_{k+1}| = 1$ $k=0,\dots,r-1$
- $|\beta_k - \beta_{k+1}| = 1$ $k=0,\dots,r-1$
- $a_{\alpha_k} = b_{\beta_k}$ $k=0,\dots,r$
(Esto es más fácil de visualizar que para escribir. Véase, por ejemplo, aquí.)
Tuve la oportunidad de probar este y también de código de un algoritmo recursivo para esto.
Mi pregunta es: Esto sin duda debe ser algo que la gente ha hecho antes. Pero, ¿cómo se llama? Yo era incapaz de encontrar un nombre para esto. Yo no sé ni cómo etiquetar este correctamente a la pregunta...
