I've taken an $n$ by $n$ chessboard and drawn an arrow on each square, pointing in one of the eight compass directions. I've done this in such a way that arrows in (orthogonally) adjacent squares differ by at most $45^\circ$. I place a cricket on one of the squares, and it proceeds to hop from square to square, following the arrows. If an arrow points of the board, the cricket falls off the board. Will this cricket necessarily fall off the board?
$$ \begin{array}{|c|c|c|} \hline \nwarrow&\leftarrow& \nwarrow\\\hline \uparrow&\nwarrow& \nwarrow\\\hline \nearrow &\uparrow& \nwarrow\\\hline \end{array} \qquad \begin{array}{|c|c|c|} \hline \downarrow&\downarrow& \color{red}\swarrow\\\hline \searrow&\searrow& \color{red}\rightarrow\\\hline \color{red}\downarrow&\color{red}\rightarrow& \nearrow\\\hline \end{array} $$ For example, the board on the left is a possible $3\times 3$ board I could have made. You can check the cricket is doomed to fall off no matter where it starts. However, the board on the right is illegal: the red arrows at the bottom left differ by $90^\circ$, and the other two red arrows differ by $135^\circ$. The question is, does there exist a legal board, and some square on that board, where the cricket does not fall off when it starts on that square?
This puzzle is from Peter Winkler's collection, Mathematical Mind Benders. It seems like there are several solutions, and I was wondering what ways people had to solve this.
Answer
I agree the cricket must fall off. This might be equivalent to KSab's answer, but it's a slightly different take (also, this might not be totally rigorous but I think it is pretty convincing).
By way of contradiction, suppose the cricket doesn't fall off and thus goes around in some sort of loop $L$. There must be some number of squares on the interior of $L$ (not counting $L$ itself). Choose a board that minimizes the area enclosed in $L$. Notice $L$ either goes clockwise or counter-clockwise: without loss of generality, assume clockwise.
Now create a new board with all the arrows turned $90^\circ$ clockwise. This is still a valid board since adjacent squares rotated the same direction by the same amount, and therefore still differ by at most $45^\circ$. However, now all the arrows of $L$ point directly towards the interior of $L$. Thus, if the cricket starts inside of $L$, it will always be forced back inside of $L$. Thus the cricket again never escapes, and the new loop that if follows must enclose a smaller area.
No comments:
Post a Comment