The squares of an n x n chessboard are numbered in an arbitrary manner from 1 to n2 (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, ... , n2 - n, we may partition {1, 2, 3, ... , n2} into the three non-empty sets Ak = {1, 2, 3, ... , k}, Bk = {k+1, k+2, ... , k+n-1}, Ck = {k+n, k+n+1, ... , n2}.
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 Bk has less than n elements, we can choose a row and a column which do not contain an element of Bk. Their union is the cross Xk. If Xk contains an element of Ak and an element of Ck, then it must contain two elements in adjacent squares, one in Ak and one in Ck. Contradiction (because these elements must differ by at least n). So Xk is either a subset of Ak or a subset of Ck.
Since A1 only has one element, X1 must be a subset of C1. Similarly, since CN only has one element, XN must be a subset of AN (where N = n2 - n). Hence for some k, Xk is a subset of Ck and Xk+1 is a subset of Ak+1. But any two crosses have at least two elements in common, whereas Ak+1 and Ck are disjoint. Contradiction.
© John Scholes
jscholes@kalva.demon.co.uk
16 Dec 2002