Dejemos que $G$ sea una cuadrícula rectangular de cuadrados unitarios con $3$ filas ( $3$ filas de cuadrados) y $8$ columnas. ¿Cuántos paseos auto-evitativos hay desde el cuadrado inferior izquierdo de hasta el cuadrado superior izquierdo de $G$ ?
Un paseo auto-evitativo en una cuadrícula rectangular de casillas unitarias es una secuencia de movimientos entre casillas adyacentes horizontal o verticalmente que no visita la misma casilla más de una vez.
¿Alguna pista para hacerlo?
Puedes resolverlo por recursión. Hay un camino directo hacia arriba. Al pasar de una columna a la siguiente, deja que $A(n)$ sea el número de formas de salir de la columna $n$ en las plazas vecinas y $B(n)$ el número de formas de salir de la columna $n$ utilizando las casillas superiores e inferiores. Tenemos $A(1)=2, B(1)=1.$ Si entras en casillas vecinas, puedes salir en casillas vecinas de una manera o en casillas superiores e inferiores de una manera. Si entras por arriba y por abajo, hay una forma de salir por arriba y por abajo y dos formas de salir por las vecinas, así que $A(n+1)=A(n)+2B(n), B(n+1)=A(n)+B(n)$ Si el borde derecho de la ruta está en la columna $n$ hay $A(n-1)+B(n-1)$ caminos. Nuestra respuesta final es $1+\sum_{i=1}^7\left(A(i)+B(i)\right)=984$ si mi hoja de cálculo es correcta.
$A(n)$ es OEIS A052542 compensado por $1$ o el doble de las cifras Pell y $B(n)$ es A001333 . $2B(n)/A(n)$ son convergentes a $\sqrt 2$
Hay $984$ caminos. Supongamos que estamos viendo una sección transversal vertical (rebanada) de la trayectoria en su transición de una columna de cuadrados a la siguiente; llamémosla estado . Hay cuatro estados posibles: $$\begin{array}{c}\leftarrow\\ \cdot \\ \rightarrow\end{array},\quad \begin{array}{c}\leftarrow\\ \rightarrow \\ \cdot\end{array},\quad \begin{array}{c}\cdot\\ \leftarrow \\ \rightarrow\end{array},\quad\textrm{and}\quad \begin{array}{c}\cdot\\ \cdot \\ \cdot\end{array} $$ donde las líneas indican que el camino se cruza en ese nivel, y el punto indica que el camino no se cruza en ese nivel. Anota el matriz de transición entre los estados, es decir, el número de formas de pasar de un estado determinado en una columna a un estado determinado en la siguiente. Con los estados ordenados como arriba, la matriz de transición es $$A=\pmatrix{ 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 }.$$
Podemos pensar en la trayectoria dada como una extensión de una trayectoria que entra por la izquierda en la parte inferior, y sale por la izquierda en la parte superior, por lo que el estado más a la izquierda es el primero, correspondiente al vector fila $(1,0,0,0)$ . Tenemos que tener en cuenta todos los caminos que se pueden obtener a través de $7$ transiciones. Las cuatro entradas del vector $(1,0,0,0) A^7 = (239,169,169,407)$ Así se cuentan todos los caminos, desglosados por su aspecto en la columna de la derecha. Al sumarlos se obtiene $984$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
