The traveler ant is walking over several chess boards. He only walks vertically and horizontally through the squares of the boards and does not pass two or more times over the same square of a board. a) In a $4$x$4$ board, from which squares can he begin his travel so that he can pass through all the squares of the board? b) In a $5$x$5$ board, from which squares can he begin his travel so that he can pass through all the squares of the board? c) In a $n$x$n$ board, from which squares can he begin his travel so that he can pass through all the squares of the board?
Problem
Source: Paraguayan Mathematical Olympiad 2012
Tags: combinatorics proposed, combinatorics
frill
28.10.2012 22:54
For even $n$ the ant can start anywhere. This is because you can draw a closed loop that passes through all the squares: e.g. for $6$x$6$: the loop starts in the top left corner goes along the top row to the end, then goes down the rightmost column to the bottom, then goes one to the right, and up till the second row, then one to the right and down to the bottom row, then one to the right and up to the second row, then one to the right and down to the bottom row, then one to the right and all the way up to the top left hand corner where we started. This pattern works for any $n$x$n$ where $n$ is even.
frill
28.10.2012 23:01
For odd $n$: colour the $n$x$n$ board like a chess board with the top-left corner as black. If you start in any of the white squares then you can't got through all the squares. Whenever you move, you go from a black square to a white square or vice versa. $\therefore$ at any time you will have gone through atleast as many white squares as black squares if you start on a white square. But as there are more black squares than white this means at no time can you have passed through all the back squares.