# Proving upper limit on number of moves?

In a $(2n-1)\times(2n-1)$ square grid every small square is marked with Up or Right or Down or Left arrow. An example would be $$\begin{array}{|c|c|c|}\hline\\\leftarrow & \rightarrow & \leftarrow\\ \hline \\ \uparrow & \downarrow & \uparrow \\ \hline \\ \leftarrow & \uparrow & \rightarrow \\ \hline \end{array}$$ A bug starts from an arbitrary square. It moves by following the arrow of current square, after it leaves, the arrow in that square is turned by $\frac{\pi}{2}$ radian anticlockwise. The process continues until the bug escapes the square grid.

Show that for any arrangement of arrows in $(2n-1)\times(2n-1)$ grid the bug will be out of the square in not more than $2^{3n-1}.(n-1)! -3$ moves.

Source: Problem Statement

-

We proceed by induction. When $n=1$ the bug clearly escapes in $2^{3(1)-1}(1-1)!-3=1$ move.
Suppose the statement holds for $n=k$, and consider a $(2k+1) \times (2k+1)$ square grid.
Consider a $(2k-1) \times (2k-1)$ grid in the middle of the $(2k+1) \times (2k+1)$ square grid. Suppose that after $m$ moves the bug is still in the square grid. By the induction hypothesis it takes the bug at most $2^{3k-1}(k-1)!-3$ moves to escape from the middle to the outer ring. At the outer ring, the bug can visit the 4 corner squares at most twice, and the $4(2k-1)$ squares at the sides at most thrice. Furthermore, the bug will go from the outer ring back into the middle at most once for each of the $4(2k-1)$ squares at the sides. Thus \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}