Problem 950

The 99th problem:
Solution: Consider the generalized problem.
For an $\mathrm{m} \times \mathrm{n}$ grid, where $\mathrm{m}$ and $\mathrm{n}$ are both odd numbers not less than 3, color the grid in black and white. In a given coloring scheme, all cells can be divided into several connected components, such that cells within the same connected component are connected to each other, and cells in different connected components are not connected. The number of connected components is denoted as $\mathrm{K}$.
We will prove the following using mathematical induction:
(1) $K \leq \frac{(m+1)(n+1)}{4}+1$;
(2) When $K=\frac{(m+1)(n+1)}{4}+1$, each cell at the four corners of the grid is not connected to any other cell.
When $\mathrm{m}=\mathrm{n}=3$, the eight cells on the outermost perimeter can belong to at most four connected components of a different color from the central cell, so $\mathrm{K} \leq 5$. The equality holds if and only if the cells at the four corners are of a different color from the other five cells.

Next, assume $m \geq 5$. Let the second row from left to right form $\mathrm{k}$ alternating black and white segments: $\mathrm{A}_{1}, \mathrm{~A}_{2}, \ldots, A_{k}$, with the number of cells in each segment being $x_{1}, x_{2}, \ldots, x_{k}$. Let $P$ be the number of connected components that contain cells from the first row but not from the second row.
We now estimate $P$.
If $\mathrm{k} \geq 2$, the last cell of $\mathrm{A}_{1}$ is the same color as either the last cell of $\mathrm{A}_{1}$ or the first cell of $\mathrm{A}_{2}$, thus it is connected to a cell in the second row; among the first $x_{1}-1$ cells, at most $\left\lceil\frac{x_{1}-1}{2}\right\rceil$ cells are of a different color from $\mathrm{A}_{1}$ and are not connected to each other. Similarly, among the cells above $\mathrm{A}_{k}$, at most $\left\lceil\frac{x_{k}-1}{2}\right\rceil$ cells are of a different color from the second row and are not connected to each other.

For $1<\mathrm{i}<\mathrm{k}$, among the $\mathrm{x}_{\mathrm{i}}-2$ cells in the middle of $\mathrm{A}_{\mathrm{i}}$, at most $\left\lceil\frac{\mathrm{x}_{\mathrm{i}}-2}{2}\right\rceil$ cells are of a different color from $\mathrm{A}_{\mathrm{i}}$ and are not connected to each other.
Thus, $P \leq\left\lceil\frac{x_{1}-1}{2}\right\rceil+\left\lceil\frac{x_{k}-1}{2}\right\rceil+\sum_{i=2}^{k-1}\left\lceil\frac{x_{i}-2}{2}\right\rceil \leq \frac{n-k+2}{2}$.
If $\mathrm{k}=1$, then $\mathrm{P} \leq\left\lceil\frac{\mathrm{n}}{2}\right\rceil \leq \frac{\mathrm{n}-\mathrm{k}+2}{2}$.
Let $Q$ be the number of connected components that contain cells from the second row but not from the third row. Since $\mathrm{A}_{\mathrm{i}}$ and $\mathrm{A}_{\mathrm{i}+1}$ always have one segment connected to the third row (consider the last cell of $\mathrm{A}_{\mathrm{i}}$ and the first cell of $\mathrm{A}_{\mathrm{i}+1}$, one of them must be connected to the third row), we have $Q \leq\left\lceil\frac{k}{2}\right\rceil \leq \frac{k+1}{2}$.
Let $R$ be the number of connected components that contain cells from the third to the $m$-th row. According to the induction hypothesis (1), we have $R \leq \frac{(m-1)(n+1)}{4}+1$.
We now prove: If $Q=\frac{k+1}{2}$ (for odd $k$) or $Q=\frac{k}{2}$ (for even $k$), then $R \leq \frac{(m-1)(n+1)}{4}$.
In fact, when $k$ is odd and $Q=\frac{k+1}{2}$, if $k=1$, then $Q=1$, all cells in the second row are the same color, and all cells in the third row are also the same color. By the induction hypothesis (2), we have $R \leq \frac{(m-1)(n+1)}{4}$.

If $k$ is an odd number and $k \geq 3$, let the cells below $\mathrm{A}_{\mathrm{i}}$ be $\mathrm{B}_{\mathrm{i}}$. Since $\mathrm{A}_{1}, \mathrm{A}_{3}, \ldots, \mathrm{A}_{k}$ are not connected to the third row, $\mathrm{B}_{1}, \mathrm{B}_{3}, \ldots, \mathrm{B}_{k}$ are of a different color from $\mathrm{A}_{1}, \mathrm{A}_{3}, \ldots, \mathrm{A}_{k}$, and thus are the same color as $\mathrm{A}_{2}, \mathrm{A}_{4}, \ldots, \mathrm{A}_{k-1}$. Therefore, $\mathrm{B}_{1}, \mathrm{A}_{2}, \mathrm{B}_{3}, \mathrm{A}_{4}, \mathrm{B}_{5}, \ldots, \mathrm{A}_{k-1}, \mathrm{B}_{k}$ are all connected. By the induction hypothesis (2), we have $R \leq \frac{(m-1)(n+1)}{4}$.

When $k$ is even and $Q=\frac{k}{2}$, if $R=\frac{(m-1)(n+1)}{4}+1$, then by the induction hypothesis (2), the first cell in the third row is of a different color from the second cell. Thus, $\mathrm{A}_{1}$ is connected to the third row. Similarly, $\mathrm{A}_{\mathrm{k}}$ is also connected to the third row. Therefore, among $\mathrm{A}_{2}, \mathrm{A}_{3}, \ldots, \mathrm{A}_{k-1}$, at most $\frac{k-2}{2}$ segments are not connected to the third row. Hence, $Q \leq \frac{k-2}{2}$, which contradicts the assumption that $\mathrm{Q}=\frac{\mathrm{k}}{2}$.
Therefore, when $Q=\left\lceil\frac{k}{2}\right\rceil$, we have $R \leq \frac{(m-1)(n+1)}{4}$. Thus, we have:
$K=P+Q+R \leq \frac{n-k+2}{2}+\frac{k+1}{2}+\frac{(m-1)(n+1)}{4}=\frac{(m+1)(n+1)}{4}+1$

When the equality holds, $k$ must be odd, and $P=\frac{n-k+2}{2}$.
Considering the condition for the equality in the estimation of $\mathrm{P}$, we know that the first and last cells of the first row are each surrounded by three cells of a different color. By the symmetry of the grid, we know that each cell at the four corners is not connected to any other cell.

Finally, it is easy to verify that for the cell at the $i$-th row and $j$-th column, if $ij$ is even, color it black; if $ij$ is odd, color it white. In these two coloring schemes, we have $K=\frac{(m+1)(n+1)}{4}+1$.
In summary, the required $M=\frac{(\mathrm{n}+1)^{2}}{4}+1$.