9.5. Each face of a cube $1000 \times$ $\times 1000 \times 1000$ is divided into $1000^{2}$ square cells with side 1. What is the maximum number of these cells that can be painted so that no two painted cells share a side?

$$
\text { (S. Dolgikh) }
$$
Answer. $3 \cdot 1000^{2}-2000=$ $=2998000$ cells.

![](https://cdn.mathpix.com/cropped/2024_05_06_cb926aec0ebce5c9efcfg-7.jpg?height=504&width=519&top_left_y=305&top_left_x=772)

Solution. Consider an arbitrary coloring that satisfies the condition. Divide all the cells on the surface into "edges" as shown in Fig. 2 - 500 edges around each of the eight vertices (one of the edges is marked in gray). Then, in the $k$-th edge, counting from the vertex, there will be $S_{k}=6 k-3$ cells. Since no two colored cells can be adjacent, in this edge there will be no more than $\left[\frac{S_{k}}{2}\right]=3 k-2=\frac{S_{k}-1}{2}$ colored cells. Summing over all 4000 edges and noting that their total area is $6 \cdot 1000^{2}$, we get that the total number of colored cells does not exceed $\frac{6 \cdot 1000^{2}-4000}{2}=$ $=3 \cdot 10^{6}-2000$.

It remains to provide an example showing that so many cells can be colored. Let's call two opposite faces of the cube the top and bottom, and the others - side faces. On each of the side faces, half of the cells can be marked in a checkerboard pattern. After that, on the top and bottom faces, half of the cells can also be colored in all rows except the two outermost, leaving them empty - see Fig. 3, where two side faces and the top face are visible. It is easy to see that with such a coloring, in each edge there will be the maximum possible number of colored cells. (Instead of checking each edge, one can note that the entire surface is divided into strips $1 \times 100$,

![](https://cdn.mathpix.com/cropped/2024_05_06_cb926aec0ebce5c9efcfg-8.jpg?height=641&width=630&top_left_y=166&top_left_x=194)

Fig. 2

![](https://cdn.mathpix.com/cropped/2024_05_06_cb926aec0ebce5c9efcfg-8.jpg?height=495&width=472&top_left_y=241&top_left_x=822)

Fig. 3

four of which are empty, and in each of the others, exactly half of the cells are colored.)

Remark. There are other optimal examples. In particular, in the given example, the coloring of the top face can be changed as follows: divide the top face into 4 triangles with diagonals, and in each of them, color the cells in a checkerboard pattern (so that the coloring of this triangle agrees with the coloring of the adjacent side face).

Comment. Only the answer - 0 points.

Only provided a correct example of coloring $N=$ $=3 \cdot 1000^{2}-2000$ cells - 1 point.

Only proved that in any coloring satisfying the conditions, there are no more than $N$ colored cells - 5 points.