What is the maximum number of pawns that can be placed on a $12 \times 12$ checkerboard such that no two pawns are on adjacent squares? (We say that two squares are adjacent if they touch at a side or a corner).
It is easy to find a configuration with 36 pawns, for example by numbering the rows and columns of the board, and placing a pawn on each square whose row and column numbers are even. Intuition tells us that this configuration is optimal, but we now need to prove it.

To do this, we divide our board into $6 \cdot 6=36$ small $2 \times 2$ blocks, and apply the pigeonhole principle. The principle tells us that if we place more than 37 pawns on the board, two of them will be in the same $2 \times 2$ block, and these two pawns will be adjacent. Therefore, we cannot do better than 36.

The following figure illustrates this proof in the case of a $6 \times 6$ board (it works the same way). The colored squares give one of the optimal configurations. We notice that this optimal configuration is not very regular. In particular, all attempts at flawed proofs based on "to be optimal, we are forced to place pawns in the corners and place the others as close as possible" are doomed to fail.

![](https://cdn.mathpix.com/cropped/2024_05_10_732985225e470d5c7305g-091.jpg?height=618&width=612&top_left_y=1884&top_left_x=713)