42nd Putnam 1981

------
 
 
Problem A2

We can label the squares of an 8 x 8 chess board from from 1 to 64 in 64! different ways. For each way we find D, the largest difference between the labels of two squares which are adjacent (orthogonally or diagonally). What is the smallest possible D?

 

Solution

Answer: 9.

Consider the straightforward ordering 1, 2, 3, 4, 5, 6, 7, 8 for the first row, 9, 10, ... , 16 for the second row, ... , 57, 58, ... , 64 for the last row. Adjacent squares in the same row have difference 1, adjacent squares in different rows have difference 7, 8 or 9. So for this ordering D = 9.

If we take any two squares on a chessboard there is a path from one to the other of length at most 7, where each step of the path is to an adjacent square [if the squares are at opposite corners of an m x n rectangle with m >= n, then take m - 1 steps, n - 1 of them diagonal and the rest along the longest side.] So there is a path of at most 7 steps from 1 to 64. At least one step of that path must have a difference of at least 9 (since 7 x 9 = 64 - 1). So we always have D ≥ 9. Hence the minimal D is 9.

 


 

4th Putnam 1941

© John Scholes
jscholes@kalva.demon.co.uk
8 Oct 1999