5. There is an infinite grid plane, none of the points of which are painted blue. For one ruble, you can choose a cell and paint all its sides blue, even if some side was already painted. What is the minimum amount of money you need to pay to get a grid square $1001 \times 1001$, all grid lines inside and on the boundary of which will be painted blue? It is not required that only the grid lines of the square are painted in the end.
Answer: 503000 rubles.

Solution: We will call a segment in the solution any segment connecting grid nodes at a distance equal to the side of a cell. Let $s$ be our $1001 \times 1001$ square. Any cell either has two common segments with the perimeter of $s$ (in which case it falls into a corner of $s$), or has no more than one common segment with it. If we take fewer than 4000 cells, they will cover fewer than $2 \cdot 4 + 4000 - 4 = 4004$ segments of the perimeter, and thus will not cover the perimeter, so to cover the perimeter, we need to paint no fewer than 4000 cells.

Consider the $999 \times 999$ square obtained from $s$ by removing a border of width 1. Divide it into $\frac{999 \cdot 999 - 1}{2}$ rectangles of $1 \times 2$ and one cell. In each rectangle, a cell must be painted, otherwise the smaller median line of this rectangle will not be painted (it belongs only to the two cells of this rectangle). Therefore, in such rectangles, no fewer than $\frac{999 \cdot 999 - 1}{2} = 500 \cdot 998 = 499000$ cells must be painted.

Note that no cell inside the $999 \times 999$ square can have common segments with the perimeter of $s$. Therefore, the number of necessary cells is no less than $499000 + 4000 = 503000$. We will construct an example for which exactly 503000 cells need to be painted. Paint each cell from the border of width 1 of our square, which will cost 4000 rubles. Mentally color the previously encountered $999 \times 999$ square in a chessboard pattern with green and red colors, with fewer green cells than red ones. If we pay for each green cell, we will get a properly painted $s$ square and will spend a total of $\frac{999 \cdot 999 - 1}{2} + 4000 = 503000$ rubles.

Comment: Answer -1 point.

Example of coloring - 2 points.

Proved that it is necessary to spend no less than 4000 rubles on the perimeter of $s$ - 1 point.

Proved that it is necessary to spend no less than 499000 rubles on painting the inner $999 \times 999$ square - 3 points.

Points for the above items are cumulative.

If the solution is generally correct but lacks an explanation of why the sets of cells involved in the two estimates do not intersect - 6 points.