The squares of an n x n chessboard are numbered in an arbitrary manner from 1 to n^{2} (every square has a different number). Show that there are two squares with a common side whose numbers differ by at least n.

**Solution**

For k = 1, 2, 3, ... , n^{2} - n, we may partition {1, 2, 3, ... , n^{2}} into the three non-empty sets A_{k} = {1, 2, 3, ... , k}, B_{k} = {k+1, k+2, ... , k+n-1}, C_{k} = {k+n, k+n+1, ... , n^{2}}.

Call two squares adjacent if they share a side. Suppose an arrangement is possible with the numbers in adjacent squares always differing by less than n. Since B_{k} has less than n elements, we can choose a row and a column which do not contain an element of B_{k}. Their union is the cross X_{k}. If X_{k} contains an element of A_{k} and an element of C_{k}, then it must contain two elements in adjacent squares, one in A_{k} and one in C_{k}. Contradiction (because these elements must differ by at least n). So X_{k} is either a subset of A_{k} or a subset of C_{k}.

Since A_{1} only has one element, X_{1} must be a subset of C_{1}. Similarly, since C_{N} only has one element, X_{N} must be a subset of A_{N} (where N = n^{2} - n). Hence for some k, X_{k} is a subset of C_{k} and X_{k+1} is a subset of A_{k+1}. But any two crosses have at least two elements in common, whereas A_{k+1} and C_{k} are disjoint. Contradiction.

© John Scholes

jscholes@kalva.demon.co.uk

16 Dec 2002