We can label the squares of an 8 x 8 chess board from from 1 to 64 in 64! different ways.

For each arrangement we find D, the largest difference between the labels of two squares which are adjacent (orthogonally or diagonally).

What is the smallest possible D (and how would you prove it)?

(In reply to possible solution by SilverKnight)

Yes, 9 is minimal, and here is a simple proof:

1 and 64 both exist somewhere on the board. Draw the shortest path between them, stepping from square to square. There can be at most 7 steps, since you can step diagonally. Since you go up by 63 numbers from 1 to 64, you can't have ALL your steps be less than 9. So D cannot be less than 9.

Posted by Brian Wainscott on 2004-02-05 13:59:06