2
$\begingroup$

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.

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.