8.5. On a 10 by 10 cell board, some 10 cells are marked. For what largest $n$ is it always possible, regardless of which cells are marked, to find a rectangle consisting of several cells, the perimeter of which will be at least $n$? The length or width of the rectangle can be equal to one cell.
Answer: $n=20$.

Solution. First, we prove that when $n=20$, it is always possible to find such a rectangle. Suppose 10 cells are colored. If there is a column or row without colored cells, then a rectangle of $1 \times 9$ with a perimeter of 20 (or even $1 \times 10$ with a perimeter of 22) can be cut from it. Now, let's assume that there is a colored cell in each column and each row. If the colored cell in the top row is in the column numbered $k$, then a rectangle of $1 \times 9$ with a perimeter of 20 can be cut from this column from the bottom.

When $n=22$, the required result is not always possible. For this, we color the cells along the diagonal. In this case, a rectangle can only be cut from the lower (or only from the upper part), but then the sum of the length and width cannot exceed 10, and the entire perimeter cannot exceed 20.