Alekseev V.B.
In a table of size $n \times n$ cells: two opposite corner cells are black, and the rest are white. What is the
minimum number of white cells that need to be repainted black so that after this, using transformations consisting of repainting all cells in any column or any row to the opposite color, all cells in the table can be made black?
Let some coloring $P$ can be transformed into a completely black square using the specified transformations. Then the same transformations in reverse order will transform a completely black square into the coloring $P$. During each of these transformations, identically colored rows or oppositely colored rows (i.e., rows whose corresponding cells are colored differently) also transition into identically or oppositely colored rows. Therefore, all rows of the coloring $P$ were identically or oppositely colored. Conversely, from any coloring with this property, the specified transformations can first make all rows identical, and then completely black. Each such coloring satisfies one of the following conditions.

1) In each row, all cells are of the same color. Then, from the condition, it follows that in the first and last rows, all cells are black, meaning there are at least $2 n$ black cells in total.
2) In each row, there are at least two black cells, meaning there are at least $2 n$ black cells in total.
3) There exists a row with exactly one black cell. Then either the first or the last row does not match it and, consequently, is opposite to it, meaning it contains $n-1$ black cells. In this case, the total number of black cells is at least $(n-1) \cdot 1 + 1 \cdot (n-1) = 2 n - 2$.

Thus, in any case, the coloring $P$ must have at least $2 n - 2$ black cells. Therefore, the number of cells that need to be pre-painted is at least $2 n - 4$. The figure below shows an $n \times n$ square, all rows of which are colored identically or oppositely, and the number of cells pre-painted black is $2 n - 4$.

![](https://cdn.mathpix.com/cropped/2024_05_06_b86fbfb53af157d03a0ag-09.jpg?height=414&width=418&top_left_y=845&top_left_x=823)

## Answer

$2 n-4$ cells.

Submit a comment