IMO 2000 SL C4

Origin: CZE | Category: Combinatorics

Problem

Let n and k be positive integers such that n/2 < k \leq2n/3. Find the least number m for which it is possible to place m pawns on m squares of an n \times n chessboard so that no column or row contains a block of k adjacent unoccupied squares.

Solution

By a good placement of pawns we mean the placement in which there is no block of k adjacent unoccupied squares in a row or column. We can make a good placement as follows: Label the rows and columns with 0, 1, . . . , n −1 and place a pawn on a square (i, j) if and only if k divides i + j + 1. This is obviously a good placement in which the pawns are placed on three lines with k, 2n−2k, and 2n−3k squares, which adds up to 4n −4k pawns in total. Now we shall prove that a good placement must contain at least 4n −4k pawns. Suppose we have a good placement of m pawns. Parti- tion the board into nine rectangular regions as shown in the picture. Let a, b, . . . , h be the numbers of pawns in the rectangles A, B, . . . , H re- spectively. Note that each row that passes through A, B, and C either A B C D E F G H n −k n −k n −k n −k 2k −n 2k −n contains a pawn inside B, or contains a pawn in both A and C. It follows that a + c + 2b \geq2(n −k). We similarly obtain that c + e + 2d, e + g + 2f, and g + a + 2h are all at least 2(n −k). Adding and dividing by 2 yields a + b + \cdot \cdot \cdot + h \geq4(n −k), which proves the statement.