Enigma 975: Ant goes for a walk
31 January 2020
Posted by on
From New Scientist #2130, 18th April 1998 [link]
Imagine an 8 × 8 chess board and imagine that in each square of the board there is written one of the following four instructions:
Go straight ahead;
An ant is placed at the centre of the bottom left corner square. She walks, parallel to the bottom edge of the board, until she reaches the centre of the next square. She reads the instruction in the square she is in and sets off walking in the direction specified by that instruction. She walks in a straight line until she reaches the centre of a square or until she walks off the board; in the latter case, her walk stops. She continues her walk in this way, from square to square, obeying the instruction each time. She walks until she reaches the top right corner square, or she walks off the board; when either happens, her walk stops. In the former case it is called a successful walk.
Answer each of the following questions, “Yes” or “No”.
1. Is it possible to find a successful walk in which the ant repeats some part of her walk?
2. Is it possible to find a walk in which the ant does not repeat the first part of her walk but does repeat some part of her walk?
3. Is it possible to find a successful walk in which the ant visits the top left-hand corner square of the board more than once?
4. Suppose now that the board is 4 × 4. Is is possible to write an instruction in each square, using each of the four different instructions four times, so that the ant’s walk visits every square of the board at least once?