4. C4 (CZE) Let $n$ and $k$ be positive integers such that $n / 2<k \leq 2 n / 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.
4. 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, \ldots, 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, 2 n-2 k$, and $2 n-3 k$ squares, which adds up to $4 n-4 k$ pawns in total.
Now we shall prove that a good placement must contain at least $4 n-4 k$ pawns. Suppose we have a good placement of $m$ pawns. Partition the board into nine rectangular regions as shown in the picture. Let $a, b, \ldots, h$ be the numbers of pawns in the rectangles $A, B, \ldots, H$ respectively. Note that each row that passes through $A, B$, and $C$ either contains a pawn inside $B$, or contains a pawn in both $A$ and $C$. It follows that $a+c+2 b \geq 2(n-k)$. We similarly obtain that $c+e+2 d, e+g+2 f$, and $g+a+2 h$ are all at least $2(n-k)$. Adding and dividing by 2 yields $a+b+\cdots+h \geq 4(n-k)$, which proves the statement.