4. On a $100 \times 100$ chessboard, 1975 rooks were placed (each rook occupies one cell, different rooks stand on different cells). What is the maximum number of pairs of rooks that could be attacking each other? Recall that a rook can attack any number of cells along a row or column, but does not attack a rook that is blocked by another rook. (I. Rubanov)
Answer: 3861. Solution: Sequentially remove from the $100 \times 100$ board the verticals and horizontals that do not contain rooks, each time gluing the edges of the removed strip. We will get a rectangle $\pi$, in each vertical and each horizontal of which there is at least one rook (obviously, the number of pairs of rooks attacking each other does not change in the process). Let there be $a$ horizontals and $b$ verticals in it. Note that if there are $k>0$ rooks in a horizontal or vertical, then there are exactly $k-1$ pairs of rooks attacking each other in it. Summing over all horizontals and verticals, we get that the number of pairs of rooks attacking each other is $1975 \cdot 2-(a+b)$ (*). At the same time, the area of the rectangle $\pi$ is not less than the number of rooks. We get that $a+b \geq 2 \sqrt{a b} \geq 2 \sqrt{1975}>2 \sqrt{1936}=88$, from which $a+b \geq 89$. Thus, the number of pairs of rooks attacking each other is no more than $1975 \cdot 2-89=3861$. To get an example where there are exactly 3861, it is sufficient to arbitrarily place 1975 rooks in some rectangle of size $45 \times 44$. This is possible since $45 \times 44=1980>1975$.