This specific puzzle is rather well known, and I am sure that most people may recognize this. There are lots of puzzles regarding 'tours' of certain buildings; by tour, I mean going through each room only once and then returning to the starting room. There is a problem, however: not all buildings can be toured. For this puzzle, we will consider a nxn rectangular grid. Let us look at a 5x5 grid.
We shall prove that such rectangular grids can't be toured. I came across this problem in the Oxford Mathematics Aptitude Test from 2009, yet I am sure that it was posed many times before.
By absurd, we shall presume that the grid can be toured.
Let us color the rectangular grid in black and white like a chessboard:
A 'move' is defined as the movement from one room to a neighboring room. Let us observe that, if a tour starts in a room of a certain color, it takes an even number of moves to return to a room of the same color. A tour of a grid should consist as \(n^2\) moves, as that's the number of rooms you need to tour. In the case of an odd n, the number of rooms is odd, so the number of moves is odd. Thus, after \(n^2\) moves, you can't return to a room of the same color as that of the room you started from, resulting in a contradiction.
The problem given by Oxford was more complicated than this; this was the last part of the problem given at Oxford. In the first four parts, you had to deal with a rectangular \(n*n\) grid with an even n. This problem reminds me of a puzzle regarding covering a chessboard with dominoes because of the strategy used. But that's a puzzle for another time.
Cris.
No comments:
Post a Comment