# The track of the chess knight at $n\times n$ board

Let $6 \le n$ and also we have an $n\times n$ board. Prove that for every way of coloring the $n \times n$ board with $n$ colours there will be a track such that a chess knight from the bottom left corner can reach the top right corner without passing through all the colours which have been used to colour the board.

• What is the movement of a horse? Are you looking at a chess knight? – paw88789 Jan 11 '15 at 10:24

A chess knight can move from the lower left square to the upper right square on the 6x6 board in 4 moves (ie. touching 5 squares), on the 7x7 board in 4 moves also, and on the 8x8 board in 6 moves (ie. touching 7 squares). In all these cases, since the knight does not enter $n$ squares, it can avoid touching all the $n$ different colours.
A knight can move across a 4x4 board in 2 moves, so extending a board from $n\times n$ to $(n+3)\times(n+3)$ only extends the minimal corner-to-corner knight track by 2 moves (from the old corner to the new corner). Therefore for all larger boards, the minimal moves for a knight corner-to-corner is also less than $n-1$ and so not all n colours will be visited.