Problem 814

Answer. $(n+1) n^{2}$.

Solution. Introduce a coordinate system so that the centers of the cubes have coordinates from 1 to $3 n$ along each axis. Assign each cube the coordinates of its center. Thus, a cube is black if and only if all its coordinates give a remainder of 2 when divided by 3.

Paint red all white cubes with coordinates $(a, b, c)$, where $a$ is divisible by 3, and $b \equiv c \equiv 2(\bmod 3)$, as well as all cubes with coordinates $(1, b, c)$, where $b \equiv c \equiv 2 \quad(\bmod 3)$. It is easy to see that this results in $(n+1) n^{2}$ red cubes, and the problem's requirements are met. It remains to show that the required result cannot be achieved by painting fewer than $(n+1) n^{2}$ cubes.

For $i=1,2, \ldots, n$ set $w_{3 i}=i, w_{3 i-1}=0, w_{3 i-2}=$ $=n+1-i$; the sequence $\left(w_{i}\right)$ looks like this: $n, 0,1, n-$ $-1,0,2, n-2, \ldots, 1,0, n$. Write the number $w_{a} w_{b} w_{c}$ in each cube with coordinates $(a, b, c)$ (in particular, zeros are written in black cubes). Then the total sum of all numbers written in white cubes will be $\Sigma=\left(w_{1}+\ldots+w_{3 n}\right)^{3}=n^{3}(n+1)^{3}$.

Let the cost $S(X)$ of a cube $X$ be the sum of the numbers in all cubes that share a vertex with it (including $X$ itself). Then, in any coloring that satisfies the requirements, the sum of the costs of the red cubes is not less than $\Sigma$. We will now prove that $S(X) \leqslant(n+1)^{2} n$ for any white cube $X$. From this it follows that at least $\frac{\Sigma}{(n+1)^{2} n}=(n+1) n^{2}$ cubes must be painted red, as required.

Let $(a, b, c)$ be the coordinates of the cube $X$. The abscissas of all cubes that share a vertex with it are equal to $a$ or $a \pm 1$; the same statement is true for the other coordinates. Therefore, $S(X)=\left(w_{a-1}+w_{a}+w_{a+1}\right)\left(w_{b-1}+w_{b}+w_{b+1}\right)\left(w_{c-1}+w_{c}+\right.$ $\left.+w_{c+1}\right)$, where we set $w_{0}=w_{3 n+1}=0$. It remains to note that $w_{t-1}+w_{t}+w_{t+1}=n$ if $t \not \equiv 2(\bmod 3)$, and $w_{t-1}+w_{t}+w_{t+1}=n+1$ otherwise. Since not all coordinates of $X$ give a remainder of 2, it follows that $S(X) \leqslant(n+1)^{2} n$.