Torre uno mismo-evitar camina sobre pequeños tableros rectangulares (pregunta de concurso)

Question

No estoy seguro de cómo obtener una forma cerrada fórmula para $R(3,n)$ como la recursividad consiste en una suma. Tal vez el mejor que se puede lograr es una recursividad que no se trata de una sumatoria de tener una parte superior del índice que se incrementa con el tamaño de la cuadrícula. El WolframAlpha artículo considera una similar, pero no idéntica de la diagonal de a pie en una cuadrícula rectangular.

Este es el problema número cinco de los de 2008 Canadá Olimpiada Nacional:

Un auto-evitar que la torre del pie en un tablero de ajedrez (una cuadrícula rectangular de la unidad de plazas) es una ruta trazada por una secuencia de movimientos paralela a un borde de la placa de una unidad cuadrada a otra, de tal manera que cada uno comienza donde el movimiento anterior terminó y que no se mueva nunca cruza un cuadrado en el que previamente se ha cruzado, es decir, la torre de la ruta de acceso no es auto-intersección.

Deje $R(m, n)$ el número de auto-evitar la torre camina sobre una $m×n$ ($m$ filas, $n$ columnas) tablero de ajedrez que comienza en la esquina inferior izquierda y termina en la esquina superior izquierda. Por ejemplo, $R(m, 1) = 1$ para todos los números naturales $m$; $R(2, 2) = 2$; $R(3, 2) = 4$; $R(3, 3) = 11$. Encontrar una fórmula para $R(3, n)$ para cada número natural $n$.

---

Hasta el momento, he deducido que:

1. Una vez que la torre se mueve a la parte superior de la fila, que se necesita para mover a la izquierda en el siguiente movimiento, y al menos en el extremo derecho de la plaza abierta en "abrir" bloque de decir $p$ plazas $(p\ge2)$, en la segunda fila. Esto es equivalente a la torre de hacer un movimiento forzado a exactamente $(3,p)$, a continuación, decidir dónde se mueven en un $2\times{p}$ rectángulo, por lo que es el girado equivalente al problema original para $R(p,2)$. (Puede haber varias distintos bloques abiertos en la segunda fila).
2. Una vez que la torre completa un movimiento a la izquierda en la segunda fila, lo que se necesita para pasar a la fila 3, a continuación, proceder como se indica en la regla 1.

Sub-problema 1: la búsqueda de $R(p,2)$

El camino está totalmente determinado por la $(p-1)$ opciones de que las filas (excepto la última, potencialmente incluyendo la primera) en la que se mueven de un lado a otro. Así

$R(p,2) = 2^{p-1} \tag{1}$

Esto también es aplicable si el grajo comienza una plaza a la derecha (y el paseo es entre las esquinas diagonalmente opuestas).

La enumeración de los posibles paseos

Introducir las siguientes notación:

• $W(3,q)$ : un completo paseo por la $R(3,q)$ problema, $q < n$
• $W(p,2)$ : un completo paseo por la $R(p,2)$ problema, $p < n$
• $U^i,D^i,L^i,R^i$ : mover de $i$ plazas en el arriba,abajo,izquierda,derecha dirección a ser seguido por un movimiento en otra dirección ($i$ puede ser omitido si igual a $1$)
• $R^{i+}, \dots$ : mover de $i$ cuadrados a la derecha,$\dots$ que puede ser seguido por un cambio en $any$ dirección (incluyendo una continuación en la misma dirección)

He identificado los siguientes distintos paseos:

1. $U^2$ (trivial)
2. $UR^xU$ , seguido por el obligado se mueve, $1 \le x \le n-1$
3. $UR^xDR^{1+} \rightarrow W(3,n-x-1) \rightarrow\text{ forced},\:1 \le x \le n-2$
4. $R^xU^2L^{1+} \rightarrow W(x,2),\:1 \le x \le n-1$
5. $R^xUL^{1+} \rightarrow W(x,2),\:1 \le x \le n-1$
6. $R^xUR^yU \rightarrow L^{y+1} \rightarrow W(x,2),\:x,y \ge 1,\:x+y \le n-1$
7. $R^xUR^yDR^{1+} \rightarrow W(3,n-x-y-1) \rightarrow L^{y+2} \rightarrow W(x,2),\:x,y \ge 1,\:x+y \le n-2$

De estos el camino de la cuenta involucra:

• solo suma para los casos de 2 a 5
• doble sumatoria de casos 6,7
• la recursividad en los casos 3,7

Para la contribución de caso 7, me sale:

$R_7(3,n) = \cases{\displaystyle\sum\limits_{x=1}^{n-3}\sum\limits_{y=1}^{n-x-2}{R(3,n-x-y-1)\cdot2^{x-1}}, n>3 \\ 0, \text{ otherwise}}$

Esto parece un poco demasiado complicado; hay una prolija forma de clasificar los paseos?

Answer 1

Deje $A(n),B(n),C(n),D(n)$ el conjunto de $3\times n$ paseos que en la última columna, al parecer estas imágenes, respectivamente:

Vamos $a(n)=|A(n)|$, $b(n)=|B(n)|$, $c(n)=|C(n)|$, $d(n)=|D(n)|$. Claramente, $a(n)=R(3,n-1)$, por simetría $b(n)=c(n)$, y como ninguna otra configuración es válida, $R(3,n)=a(n)+b(n)+c(n)+d(n)=R(3,n-1)+2b(n)+d(n)$.

Podemos extender cualquiera de las $B(n-1)$-a pie o $D(n-1)$-a pie a un $B(n)$-a pie, y se puede extender un $B(n-1)$, $C(n-1)$, o $D(n-1)$-a pie a un $D(n)$-a pie, cada uno en una forma única, y viceversa, si se "corta-corte" de la última columna como en la siguiente imagen:

En otras palabras, tenemos un bijection $B(n-1)\cup D(n-1)\leftrightarrow B(n)$ y un bijection $B(n-1)\cup C(n-1)\cup D(n-1)\leftrightarrow D(n)$. Esto nos da la recursiones $$ b(n)=b(n-1)+d(n-1),\qquad d(n)=d(n-1)+2b(n-1)$$ de dónde $$ 2b(n-1)=d(n)-d(n-1)=(b(n+1)-b(n))-(b(n)-b(n-1))$$ y así $$ b(n+1)=2b(n)+b(n-1).$$ Llegamos a la conclusión de que $b(n)$ es una combinación lineal de $\lambda_1^n$ $\lambda_2^n$ donde $\lambda_{1,2}$ son las soluciones de $X^2=2X+1$, es decir, $\lambda_{1,2}=1\pm\sqrt 2$. A continuación, $d(n)$ es también una combinación lineal, y hasta una constante, entonces es $R(3,n)$. Llegamos a la conclusión de $$R(3,n)=\alpha(1+\sqrt 2)^n+\beta(1-\sqrt 2)^n+\gamma $$ donde $\alpha,\beta,\gamma$ puede ser obtenido a partir de $$\begin{align}1=R(3,1)&=\alpha(1+\hphantom{1}\sqrt 2)+\beta(1-\hphantom{1}\sqrt 2)+\gamma\\ 4 = R(3,2)&=\alpha(3+2\sqrt 2)+\beta(3-2\sqrt 2)+\gamma\\ 11=R(3,3)&=\alpha(7+5\sqrt 2)+\beta(7-5\sqrt 2)+\gamma\end{align}$$ Uno encuentra straighforwardly (o, al menos, verifica) que $\alpha = \frac{2+\sqrt 2}4$, $\beta =\frac{2-\sqrt 2}4 $, $\gamma = -1$. En resumen, $$ R(3,n)= \frac{2+\sqrt 2}4(1+\sqrt 2)^n +\frac{2-\sqrt 2}4(1-\sqrt 2)^n-1.$$

Answer 2

Aquí hay una posible solución, con un enfoque diferente para contar los paseos a la suya.

Deje $\rho(3,k)$ el conjunto de la auto-evitar la torre paseos con exactamente la primera $k$ columnas. A continuación, $$R(3,n) = \sum_{i = 1}^n |\rho(3,i)|$$ Ahora tratamos de dividir $\rho(3,k)$ en subconjuntos disjuntos. (Esto es más fácil que en el problema original, ya que sabemos que el $k$-ésima columna obtiene ocupado por lo que hay menos casos). Definir:
$$\rho_1(3,k) := \{\mbox{rutas en las cuales cuadrado } (1,k) \mbox{ no se utiliza}\} \\ \rho_2(3,k) := \{\mbox{rutas utilizando la escuadra } (1,k) \mbox{ y } (3,n)\} \\ \rho_3(3,k) := \{\mbox{rutas en las cuales cuadrado } (3,k) \mbox{ no se utiliza}\}$$ Se nota que ya tenemos que entrar y salir de la $k$-ésima columna debemos utilizar al menos dos plazas en la columna y en el caso de $\rho_2$ debemos utilizar todos los tres. Esto nos da que el anterior establece forman una partición de $\rho(3,k)$. Por simetría $|\rho_1(3,k)| = |\rho_3(3,k)|$.
Ahora tenemos que pensar acerca de la construcción de $\rho(3,k+1)$$\rho(3,k)$. Podemos hacer esto mediante la adopción de la entrada de la plaza (o para las rutas en $\rho_2(3,k)$ el cuadrado de $(2,k)$) a partir de una ruta dada en $\rho(3,k)$ $k$- th y cambiar esta ruta de acceso para moverse a través de la $(k+1)$-ésima columna, volver a entrar en el $k$-ésima columna en la plaza de la que la ruta original que salió de la $k$-ésima columna. Esto nos da que (la supresión de la 3s): $$|\rho_1(k+1)| = |\rho_1(k)| + |\rho_2(k)| \\ |\rho_2(k+1)| = |\rho_1(k)| + |\rho_2(k)| + |\rho_3(k)| \\ |\rho_3(k+1)| = |\rho_2(k)| + |\rho_3(k)|$$ but using the symmetry we noted earlier this reduces to: $$|\rho_1(k+1)| = |\rho_1(k)| + |\rho_2(k)| \\ |\rho_2(k+1)| = 2|\rho_1(k)| + |\rho_2(k)|$$ Lo que nos da (para $k > 1$): $$ |\rho_1(k+1)| = |\rho_1(k)| + 2|\rho_1(k-1)| + |\rho_2(k-1)| = 2|\rho_1(k)| + |\rho_1(k-1)|$$ and similarly $$|\rho_2(k+1)| = 2|\rho_2(k)| + |\rho_2(k-1)|$$ Estos son lineales ecuaciones de diferencia por lo que sólo necesitamos algunos casos iniciales para determinar las constantes y tenemos fórmulas para$|\rho_1|$$|\rho_2|$. Pero es fácil ver $|\rho_1(1)| = 0$$|\rho_2(1)| = 1$. Esto nos da las siguientes soluciones: $$|\rho_1(k)| = \frac{1}{2 \sqrt{2}}(1+\sqrt{2})^{k-1} - \frac{1}{2 \sqrt{2}}(1-\sqrt{2})^{k-1} \\ |\rho_2(k)| = \frac{1}{2}(1+\sqrt{2})^{k-1} + \frac{1}{2}(1 - \sqrt{2})^{k-1}$$ Finalmente,$$R(3,n) = \sum_{i = 1}^n |\rho(3,i)| = \sum_{i=1}^n |\rho_2(3,i)| + 2 \sum_{i=1}^n |\rho_1(3,i)|$$, Pero estas son las series geométricas y así podemos los suma para obtener: $$R(3,n) = \bigg(\frac{1}{2} + \frac{1}{\sqrt{2}}\bigg) \bigg ( \frac{(1 + \sqrt{2})^n - 1}{\sqrt{2}} \bigg ) - \bigg ( \frac{1}{2} - \frac{1}{\sqrt{2}} \bigg ) \bigg ( \frac{(1 - \sqrt{2})^n - 1}{\sqrt{2}} \bigg ) $$ $$ = \bigg ( \frac{1}{2 \sqrt{2}}\bigg )((1 + \sqrt{2})^{n+1} - (1- \sqrt{2})^{n+1}) - 1$$