13
$\begingroup$

Suppose you can make a rectangular maze, where each cell (apart from the bottom-right) can contain an arrow in one of the four directions (up, down, left or right) of your choosing, except for those on an edge or corner, which must not point out of the maze.

A ball is then placed into the top-left square and begins to move. It will move in the direction of the arrow in the cell that it is currently in. Then, that arrow will rotate 90 degrees clockwise. If an arrow is pointing out of the maze, it will continue rotating clockwise until it points in a valid direction.

A valid maze is one in which the ball will never reach the bottom-right corner.

Prove or disprove the existence of such a maze. If it exists, find the smallest possible maze (in terms of number of squares).


Here is an example of a maze.

An example of a 2x2 maze. Top-left (A1) has arrow pointing right, top-right (A2) is pointing left, lower-left (B1) is pointing up.

  • The ball begins in A1. It moves right to A2, and the A1 arrow rotates to point down.
  • The ball moves left to A1, and the A2 arrow rotates to point down (as both up and right point out of the maze).
  • The ball moves down to B1, and the A1 arrow rotates to point right (as both left and up point out of the maze).
  • The ball moves up to A1, and the B1 arrow rotates to point right.
  • The ball moves right to A2, and the A1 arrow rotates to point down.
  • The ball moves down to B2, and the A2 arrow rotates to point left.
  • Now, the ball is in B2, the bottom-right corner of the maze, so that is the end. It is not a valid maze, but if it were, it would have a score of $4$.
$\endgroup$
22
$\begingroup$

Suppose such a maze exists. Then the balls visits at least one square infinitely many times. Let $S$ be one such square that is closest to the bottom-right. $S$ is not the bottom-right square, so there exists a square $T$ to the right of or below $S$ that is closer to the bottom-right than $S$ is. However, the ball must visit $T$ at least once every $4$ visits to $S$ due to arrow rotation. Therefore, the ball must also visit $T$ infinitely many times, contradicting the minimality of $S$. Then no such maze exists.

$\endgroup$
  • $\begingroup$ Very succinct; well done. I'll wait a bit before accepting. $\endgroup$ – ZanyG Mar 22 at 21:50
  • 1
    $\begingroup$ This(Q&A) probably belongs into mathematics.stackexchange.com ? $\endgroup$ – LMD Mar 23 at 12:15

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.