IMO 1988 SL 4

Origin: CZS

Problem

An n \times n chessboard (n \geq2) is numbered by the numbers 1, 2, . . . , n2 (every number occurs once). Prove that there exist two neigh- boring (which share a common edge) squares such that their numbers differ by at least n.

Solution

Suppose that the numbers of any two neighboring squares differ by at most n −1. For k = 1, 2, . . . , n2 −n, let Ak, Bk, and Ck denote, respectively, the sets of squares numbered by 1, 2, . . ., k; of squares numbered by k + n, k + n + 1, . . . , n2; and of squares numbered by k + 1, . . . , k + n −1. By the assumption, the squares from Ak and Bk have no edge in common; Ck has n −1 elements only. Consequently, for each k there exists a row and a column all belonging either to Ak, or to Bk. For k = 1, it must belong to Bk, while for k = n2 −n it belongs to Ak. Let k be the smallest index such that Ak contains a whole row and a whole column. Since Bk−1 has that property too, it must have at least two squares in common with Ak, which is impossible.