Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

PS: If you have any ideas please edit the title to something more informative.

Source: Problem Statement

share|improve this question
add comment

1 Answer 1

up vote 2 down vote accepted

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}

We are thus done by induction.

share|improve this answer
    
clear and concise, thanks a lot for the answer. –  sabertooth Feb 20 '13 at 17:07
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.