25
$\begingroup$

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.

$\endgroup$
  • 5
    $\begingroup$ Great puzzle! I'm pretty certain the answer is 'yes' and I have some instinctive flow-based rationale for it, but nothing resembling a solid proof (yet). The heuristic argument goes something like this: 'suppose there is a closed loop. This corresponds to a closed loop in a planar flow, which of necessity (by basic winding-number arguments) must have a 'vortex' (a point where the flow is ill-defined) within it. The discrete version of such a vortex cannot possibly satisfy the continuity condition'. But I don't have a good discrete version of the winding number argument. $\endgroup$ – Steven Stadnicki Mar 26 '15 at 0:24
  • 2
    $\begingroup$ Should the starting square (where you place the cricket) be specified, or does it have to always work for ALL squares? $\endgroup$ – qzx Mar 26 '15 at 11:11
  • 2
    $\begingroup$ It is plainly obvious that a 1x1 and 2x2 board throws the cricket off. A little work shows that 3x3, 4x4, and 5x5 throw the cricket off as well. I went up to 10x10 and couldn't find a way to keep the cricket on the board, and there is a pattern that suggests due to the 2D nature of the puzzle and the adjacent arrow restriction you cannot design a board of any size that would keep the cricket on. Don't know how I might prove it though. $\endgroup$ – Adam Davis Mar 26 '15 at 13:47
  • 3
    $\begingroup$ @IanMacDonald This is a strictly mathematical puzzle, not a physical one; the puzzle itself states that the cricket goes from square to square following the arrows. $\endgroup$ – Steven Stadnicki Mar 26 '15 at 15:15
  • 2
    $\begingroup$ Having followed the rules for my answer, I'll add a comment that stretches them: ~~~~ All the arrows point straight up. The cricket jumps in the direction of the arrow, and lands back in the same square. $\endgroup$ – Joffan Mar 26 '15 at 22:56
10
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ do you call this a proof ? where the hell is that loop in the grid where the ball doesnt fall from ? $\endgroup$ – Abr001am Mar 26 '15 at 21:38
  • $\begingroup$ As @Agawa001 is saying, this isn't a proof. Are you proving that the cricket can stay on the board indefinitely? If so, you have a major flaw in your "proof" in that you've assumed that a loop L can exist given the guidelines, which it may not. If you're trying to prove not, you need to actually state why not. $\endgroup$ – Duncan Mar 26 '15 at 22:44
  • $\begingroup$ This just proves that it is possible to create a loop like this, with a minimal enclosed area of 1 (you can't go smaller than that): $$ \begin{array}{|c|c|c|} \hline \rightarrow&\searrow& \downarrow\\\hline \nearrow& & \swarrow\\\hline \uparrow &\nwarrow& \leftarrow\\\hline \end{array} $$ but it does NOT answer the $45^\circ$ requirement for adjacent orthogonal squares. How do you put arrows in the interior of $L$ without contradicting the $45^\circ$ rule? $\endgroup$ – qzx Mar 26 '15 at 23:02
  • 3
    $\begingroup$ @Duncan This is a proof by contradiction (technically, by infinite descent). It essentially says 'suppose that there were such a loop for some grid configuration. Then surely there is a grid configuration with the smallest such loop. But here is a way of generating, from any grid configuration with a loop, a configuration with a smaller loop.' $\endgroup$ – Steven Stadnicki Mar 27 '15 at 1:08
  • 5
    $\begingroup$ That said, one flaw with this proof is that you actually do need to prove that such a loop can't exist with zero cells in its interior! This isn't immediately obvious. $\endgroup$ – Steven Stadnicki Mar 27 '15 at 1:10
9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your proof seems to be saying 'no' rather than 'yes'. However, I agree with it. $\endgroup$ – DaaaahWhoosh Mar 26 '15 at 17:42
  • $\begingroup$ try to concretise an example $\endgroup$ – Abr001am Mar 26 '15 at 17:46
  • $\begingroup$ @DaaaahWhoosh Well yes to the question "Will this cricket necessarily fall off the board?" I realize there is some amiguity. $\endgroup$ – KSab Mar 26 '15 at 17:46
  • $\begingroup$ Oh, right. There are two contradictory questions in the main question, I only saw the second one. $\endgroup$ – DaaaahWhoosh Mar 26 '15 at 18:10
  • $\begingroup$ I think the only point where the proof could use a few more words is the reason why every square $S$ is in a loop or falls of the board. I think that, given it doesn't fall off, the way you find a loop is by looking at the two paths originiating from $S$, one given by following the arrows, and the other by following their reverses, since these are both valid connections in your sense. Nice! +1 $\endgroup$ – Mike Earnest Mar 26 '15 at 21:17
3
$\begingroup$

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:

enter image description here

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.

$\endgroup$
  • $\begingroup$ @Agawa001 who is being sarcastic? Did you actually read my answer? $\endgroup$ – Joffan Mar 27 '15 at 0:10
  • $\begingroup$ excuse me i stoped reading a this level Joffan "If we didn't have to put an arrow in the middle of a 3x3 board" , but as the matter of fact , there s no solution with actual rules based , something went wrong with that question $\endgroup$ – Abr001am Mar 27 '15 at 10:54
0
$\begingroup$

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:

enter image description here

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$

$\endgroup$
  • $\begingroup$ people who are for an availability of a solution please let us see whats up your sleeves $\endgroup$ – Abr001am Mar 26 '15 at 19:52
  • 4
    $\begingroup$ "I couldn't find one" is not a proof of non-existence. $\endgroup$ – KSmarts Mar 26 '15 at 20:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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