¿Probar el límite superior del número de movimientos?

Question

En un $(2n-1)\times(2n-1)$ cuadrícula cuadrada cada pequeño cuadrado está marcado con una flecha hacia arriba o hacia la derecha o hacia abajo o hacia la izquierda. Un ejemplo sería $$\begin{array}{|c|c|c|}\hline\\\leftarrow & \rightarrow & \leftarrow\\ \hline \\ \uparrow & \downarrow & \uparrow \\ \hline \\ \leftarrow & \uparrow & \rightarrow \\ \hline \end{array}$$ Un bicho parte de una casilla arbitraria. Se mueve siguiendo la flecha de la casilla actual, después de salir, la flecha de esa casilla se gira por $\frac{\pi}{2}$ radianes en sentido contrario a las agujas del reloj. El proceso continúa hasta que el bicho se escapa de la rejilla cuadrada.

Demuestre que para cualquier disposición de flechas en $(2n-1)\times(2n-1)$ cuadrícula el bicho estará fuera de la plaza en no más de $2^{3n-1}.(n-1)! -3$ se mueve.

PD: Si tienes alguna idea, por favor, edita el título a algo más informativo.

Fuente: Planteamiento del problema

Answer 1

Procedemos por inducción. Cuando $n=1$ el bicho se escapa claramente en $2^{3(1)-1}(1-1)!-3=1$ mover.

Supongamos que la afirmación es válida para $n=k$ y considerar un $(2k+1) \times (2k+1)$ cuadriculado.

Considere un $(2k-1) \times (2k-1)$ rejilla en el centro de la $(2k+1) \times (2k+1)$ rejilla cuadrada. Supongamos que después de $m$ mueve el bicho sigue en la rejilla cuadrada. Por la hipótesis de inducción, el bicho tarda como máximo $2^{3k-1}(k-1)!-3$ se mueve para escapar del centro al anillo exterior. En el anillo exterior, el bicho puede visitar las 4 casillas de las esquinas como máximo dos veces, y el $4(2k-1)$ cuadrados a los lados como máximo tres veces. Además, el bicho pasará del anillo exterior al centro como máximo una vez por cada uno de los $4(2k-1)$ cuadrados a los lados. Así, \begin {align} m & \leq (2^{3k-1}(k-1)!-3)(4(2k-1)+1)+3(4(2k-1))+2(4) \\ &=2^{3(k+1)-1}k!-3-3(2^{3k-1})(k-1)!+8 \\ & \leq 2^{3(k+1)-1}k!-3-3(2^{3(1)-1})((1)-1)!+8 \\ & <2^{3(k+1)-1}k!-3 \end {align}

De este modo, se hace por inducción.