MathDB

Column/Row contains a block of k adjacent unoccupied squares

Source: IMO Shortlist 2000, C4

August 10, 2008

combinatoricsExtremal combinatoricsIMO Shortlistgraph theoryChessboard

Problem Statement

Let

n

and

k

be positive integers such that

\frac{1}{2} n < k \leq \frac{2}{3} n.

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.