Problem: Consider a 6 by 6 grid where you start at the top left square of the grid. Is there a path from the top left corner of the grid to the bottom right square of the grid such that you visit each of the 35 squares except the starting square exactly once (You cannot revisit the starting square. Note that each move in a path is either one step in the vertical direction or one step in the horizontal direction. You can’t move diagonally)

Solution: The first step to solving this problem is to colour the squares of the 6 by 6 grid as in the picture shown below.

Now, notice a few things about this colouring. Firstly, a white square is only adjacent to black squares and a black square is only adjacent to white squares. So, with each move, the colour of the square I am on changes. Since there are 36 squares, exactly 35 moves have to be made in total, as the 35 squares apart from the starting square need to be visited exactly once.

Since the colour of the current square changes with every move, I will need to be on a square of a different colour after an odd number of moves. So, since I start on a white square and I make an odd number of moves, I must end on a black square. However, it is easy to see from the diagram above that the bottom right square is a white square. So, it is impossible to end on the bottom right square if I visit every square except the starting square exactly once. Hence, the answer to question posed at the beginning of this post is no!!

Don’t forget to check my blog next week for another fascinating problem!!

Image Source: http://www.murderousmaths.co.uk/books/MMoE/chess.htm