Problem 1722

1. Setup and Definitions:
- Divide the upper right quadrant of the plane into square cells with side length $1$.
- Denote each cell with coordinates $(a,b)$ where $a, b \in \mathbb{N}$, starting from the bottom left cell with coordinates $(1,1)$.
- Assume $n^2$ cells are colored.

2. Diagonal Line Analysis:
- Consider the cells colored diagonally as in a chessboard starting from $(1,1)$. The set of cells arranged diagonally is the set of coordinates $(x,y)$ such that $x+y$ is constant.
- Denote the $k$-th diagonal line as the set of cells $(x,y)$ where $x+y=k$.

3. Claim 1:
- If we have $k$ colored cells on some $m$-th diagonal line, then there are at least $k+1$ neighboring cells $(a,b)$ such that $a+b > m$. These are called *upper neighbor cells*.
- The upper neighbor cells of colored cells in the $k$-th diagonal line lie on the $(m+1)$-th diagonal line. Therefore, the sets of upper neighbor cells in any two distinct diagonal lines are disjoint.

4. Induction Hypothesis:
- We proceed by induction on $n$.
- Assume the statement is true for $n-1$, i.e., for $(n-1)^2$ colored cells, there are at least $(n-1)^2 + (n-1)$ cells that have at least one colored neighbor.

5. Inductive Step:
- Among the $n^2$ colored cells, take out $2n-1$ colored cells (call them red cells) following these steps:
1. Take out cells $(x,y)$ in descending order of $x+y$.
2. Among the cells $(x,y)$ with $x+y=k$, take out cells in descending order of $y$.
- After this, we are left with $(n-1)^2$ colored cells (call them blue cells) which will have $(n-1)^2 + (n-1)$ neighbor cells. Let $S_{n-1}$ be the set of neighbor cells for these $(n-1)^2$ blue cells.

6. Analysis of Red Cells:
- Suppose the $2n-1$ red cells lie on $h$ diagonal lines starting from the $k$-th diagonal line to the $(k+h-1)$-th diagonal line. Denote $a_i$ as the number of red cells in the $i$-th diagonal line.
- From the claim, there will be no blue cells on the $i$-th diagonal line where $k < i \leq k+h-1$. Therefore, the $a_i$ cells on the $i$-th diagonal line will contribute at least $a_i + 1$ neighbor cells to the total $S_n$ (not including neighbor cells $S_{n-1}$ of blue cells).

7. Special Cases:
- For $a_k$ red cells on the $k$-th diagonal line, if there is no blue cell on the $k$-th diagonal line, then we will have extra $a_k + 1$ neighbor cells added to $S_n$. However, if there is at least one blue cell, then the blue cells will have at most one common upper neighbor cell with such $a_k$ red cells, resulting in extra $a_k$ neighbor cells added to $S_n$ (not including neighbor cells $S_{n-1}$ of blue cells).

8. Conclusion:
- Since $\sum_{i=k}^{k+h-1} a_i = 2n-1$, if either no blue cell on the $k$-th diagonal line or $h \geq 2$, then:
$$S_n \geq S_{n-1} + \sum_{i=k}^{k+h-1} a_i + h - 2 = n^2 + n + h - 2 \geq n^2 + n.$$
- If $h = 1$, then all $2n-1$ cells plus at least one blue cell can be put on the $k$-th diagonal line. Hence, $k \geq 2n$ and this last $k$-th diagonal line contains at least $2n$ colored cells. Denote $b_i$ as the number of colored cells on the $i$-th diagonal line, then $b_k \geq 2n$. It's not hard to show that for $2 \leq i \leq k$, the number of neighbor cells on the $i$-th diagonal line is at least $(b_{i-1} + b_{i+1})/2$. Note that $b_{k+1} = 0$ and the $(k+1)$-th diagonal line has at least $b_k + 1 \geq 2n + 1$ neighbor cells. Therefore,
$$|S_n| \geq \sum_{i=2}^{k} \frac{b_{i-1} + b_{i+1}}{2} + b_k + 1 = \sum_{i=1}^{k} b_i + \frac{1}{2} (b_k - b_1) + 1 = n^2 + \frac{1}{2} (b_k - b_1) + 1 > n^2 + n.$$

$\blacksquare$