6. Each cell of a $10 \times 10$ board is painted black or white. A cell is said to be out of place if it has at least seven neighbors of a different color than itself. (Neighbors are cells that share a common side or corner.) What is the maximum number of cells on the board that can be out of place at the same time?
# Solution.

Answer 26. The example consists of 13 dominoes, which do not share any cells and do not touch the border of the board (see right).

Estimation. Let's call a cell that is not in its place an NVCT-cell. Obviously, NVCT-cells cannot be adjacent to the border. Let's examine what form a connected component of NVCT-cells can have, considering cells to be neighbors if they share a side or a corner. The simplest case is an isolated cell

(case $a$ in the figure).

Now, let's consider two neighboring NVCT-cells of the same color (say, the first). Then their neighbors - cells of the second color, each of which has at least two neighbors of the second color, are of the second color and each, by definition, borders cells of the second color, each of which has at least two neighbors of the second color, meaning they are not NVCT. We get cases $b$ and $c$.

Consider two neighboring NVCT-cells of different colors. They can only be adjacent by a corner, and such a picture is uniquely defined up to reflection. Further, among the neighboring cells, only those marked with "?" can be NVCT-cells, and so on, resulting in a "snake" (with two or more NVCT-cells - $g$).

![](https://cdn.mathpix.com/cropped/2024_05_06_3c7d0cd34a657b450ea4g-3.jpg?height=175&width=180&top_left_y=732&top_left_x=273)

$a$

![](https://cdn.mathpix.com/cropped/2024_05_06_3c7d0cd34a657b450ea4g-3.jpg?height=180&width=226&top_left_y=735&top_left_x=504)

$b$
![](https://cdn.mathpix.com/cropped/2024_05_06_3c7d0cd34a657b450ea4g-3.jpg?height=232&width=532&top_left_y=722&top_left_x=797)

![](https://cdn.mathpix.com/cropped/2024_05_06_3c7d0cd34a657b450ea4g-3.jpg?height=229&width=339&top_left_y=725&top_left_x=1441)

Now, for each cell, let's draw its 0.5-neighborhood - a square with a side of 2 (its sides do not follow the grid lines), in which our cell is in the center. The components into which the NVCT-cells are divided - single cells, dominoes, and "snakes" of $n$ cells (including 2 cells of the same color) - have neighborhoods of size 4, 6, and $3n+1$ cells, respectively. These neighborhoods do not overlap and lie within the central $9 \times 9$ square.
![](https://cdn.mathpix.com/cropped/2024_05_06_3c7d0cd34a657b450ea4g-3.jpg?height=208&width=1152&top_left_y=1311&top_left_x=455)

The area of the neighborhood of a component is at least three times the area of the component itself, and equality is only achieved for a domino. If there are 27 NVCT-cells, then the minimum area of the neighborhoods is exactly equal to the area of the $9 \times 9$ square ($27 \cdot 3 = 81$), but the ratio is exactly 3 only if everything is divided into dominoes, and 27 is odd - a contradiction.