Question

Given an \(n\times n\) grid of squares, where \(n>1\), a tour is a path drawn within the grid such that:

  • along its way the path moves, horizontally or vertically, from the centre of one square to the centre of an adjacent square;
  • the path starts and finishes in the same square;
  • the path visits the centre of every other square just once.

For example, below is a tour drawn in a \(6\times6\) grid of squares which starts and finishes in the top-left square.

tour in a 6 by 6 grid

For parts (i)-(iv) it is assumed that \(n\) is even.

  1. With the aid of a diagram, show how a tour, which starts and finishes in the top-left square, can be drawn in any \(n\times n\) grid.

  2. Is a tour still possible if the start/finish point is changed to the centre of a different square? Justify your answer.

Suppose now that a robot is programmed to move along a tour of an \(n\times n\) grid. The robot understands two commands.

  • command \(R\) which turns the robot clockwise through a right angle;
  • command \(F\) which moves the robot forward to the centre of the next square.

The robot has a program, a list of commands, which it performs in the given order to complete a tour; say that, in total, command \(R\) appears \(r\) times in the program and command \(F\) appears \(f\) times.

  1. Initially the robot is in the top-left square pointing to the right. Assuming the first command is an \(F\), what is the value of \(f\)? Explain also why \(r+1\) is a multiple of \(4\).

  2. Must the results of part (iii) still hold if the robot starts and finishes at the centre of a different square? Explain your reasoning.

  3. Show that a tour of an \(n \times n\) grid is not possible when \(n\) is odd.