Arrows on a Chessboard

Question

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 1

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.

Answer 2

I am quite convinced that the answer is yes, the cricket will necessarily fall off. Though I am somewhat less convinced in my ability to construct a rigorous proof, I think this might be a valid approach, though it probably could be written more rigorously.

First classify a loop as a set of connected squares, two squares being connected if one is the first square in the others corresponding direction OR in the opposite direction.

For example the three red arrows would be connected:

\begin{array}{|c|c|c|} \hline \rightarrow&\rightarrow& \color{red}\rightarrow\\\hline \nearrow& \color{red}\nearrow& \rightarrow\\\hline \color{red}\uparrow&\nearrow& \nearrow\\\hline \end{array}

It is relatively clear that if a cricket can stay on the board, the board must have a loop (though not if and only if). It is also clear that any loop must have at least one unused square in its interior, in other words the loop must be surrounding at least one square.

I believe we can also show that given any loop, there must be a smaller loop with all points in its interior or part of it (smaller meaning it has less squares in its interior). My reasoning for this is as follows:

Any square must either be in a loop, or follow a path to the edge of the grid.* Since a square in the interior of a loop cannot follow a path to the edge of the grid; it would first come to a square in the loop (it also could not 'cross diagonals', as this would violate the $45^\circ$ rule) it must exist as part of a smaller loop (which may or may not include part of the larger one).

Given that any valid loop must have at least one interior square, and that any valid loop must also have a valid smaller loop, it is clear that no valid loop can exist, as obviously continually decreasing the size of the loops would necessarily decrease the size of the interior.

*I defined loops the way I did specifically so this would hold.

Answer 3

If we didn't have to put an arrow in the middle of a 3x3 board, we could send the cricket round in circles as follows:

But of course the middle arrow then doesn't have a direction that is consistent with the rules. And any attempt to set up circulation on a larger grid will have the same problem, it seems. There will be a central point that does not have a valid arrow direction due to the conflicting values nearby.

Similarly (or even more so) with a grid that attempts to have inward movement; this cannot be carried on to a central point, so must reduce to a circulation, with the same results as above.

There is thus no possible configuration of arrows that allows the cricket to arrive at a previously visited square on the board, so yes, the cricket will necessarily fall off the board.

Answer 4

Lets annotate an arrow as $n\mod 8$ that points in the direction $45°n $.

We know that the value of all arrows must increase or decrease by at most 1 each horizontal or vertical step.

After removing undesired directions from the borders, the general aspect of the grid looks like:

After many attempts and some reasoning I couldn't find any logical way to make rows respectively incremental until they end up decremental in the last row.

Conclusion: there is no solution

proof:

If the cricket is not necessarily to put anywhere in the grid , a loop can be symbolically representd as:

$$ \begin{array}{|c|c|c||c|c|c|} \hline . &\rightarrow& .& .& .& .\\\hline \nearrow&x=\rightarrow& \searrow& .& .& .\\\hline \uparrow &x& x& \searrow& .& .\\\hline \nwarrow&x & x& x& \searrow& .\\\hline .&\nwarrow & x& x& x& \swarrow\\\hline .&.& \nwarrow& x = \leftarrow& \swarrow& .\\\hline .&.& .& \nwarrow& .& .\\\hline \end{array} \qquad$$

the dots are not a problem they can be multiple values of different choices , but $x$ must be defined to accomplish and finalise our grid , after some struggling with numbers i didnt find any such x values where :

$$ \begin{array}{|c|c|c||c|c|c|} \hline . &0& .& .& .& .\\\hline 7=-1&x=0& 1& .& .& .\\\hline 6=-2 &x& x& 1& .& .\\\hline 5=-3&x & x& x& 1& .\\\hline .&5 & x& x& x& 1\\\hline .&.& 5& x = 4& 3& .\\\hline .&.& .& 5& .& .\\\hline \end{array} \qquad$$

at the level of upper rows x must be gradually incremental , and the lower rows $x$ must be respectively decremental where the anomaly appears !!!

---

Claification:

if we consider a series of consecutive numbers 0 1 2 .... n , the minimal length of this series that ensures a sudden decrementation is 4 . as following :

a b c d a b c d .... = 0 1 2 3 0 1 2 3 ...

$$a$$

$$d\ \ ↓↑\ \ \ b$$

$$c$$

this series incements in a specific row : a a b c = 0 0 1 2 the following series decrements next arrow: a d c c = 0 3 2 2

this is rule fitting because a a , a d , b c , c c are different by one step at most , but .... there is no way to apply this on bigger series , like 0 1 2 3 4 , ... and more like length=8 directions series of the actual problem.

---

Another assumtion is when two diagonal adjacent squares are 180° different that keeps the cricket in two squares loop but , the problem in the vertically adjacent square = $x$ there s nt such $x$ where $(x+1) mod 8 = 3$ and $(x-1) mod 8= 7 = -1$