Введём систему координат так, чтобы центры кубиков имеют координаты от $1$ до $3n$ по каждой оси. Каждому кубику приписываем координаты его центра. Таким образом, кубик чёрный тогда и только тогда, когда все его координаты дают остаток $2$ при делении на $3$.

Окрасим красным все белые кубики с координатами $(a, b, c)$, где $a$ делится на $3$, а $b \equiv c \equiv 2 \pmod{3}$, а также все кубики с координатами $(1, b, c)$, где $b \equiv c \equiv 2 \pmod{3}$. Нетрудно видеть, что получилось $(n+1)n^2$ красных кубиков, и требования задачи выполнены. Осталось показать, что добиться требуемого нельзя, окрасив менее $(n+1)n^2$ кубиков.

При $i = 1, 2, \dots, n$ положим $w_{3i} = i$, $w_{3i-1} = 0$, $w_{3i-2} = n+1-i$; последовательность $(w_i)$ выглядит так: $n, 0, 1, n-1, 0, 2, n-2, \dots, 1, 0, n$. Запишем в каждый кубик с координатами $(a, b, c)$ число $w_a w_b w_c$ (в частности, в чёрных кубиках записаны нули). Тогда общая сумма всех чисел, записанных в белых кубиках, окажется равной $\Sigma = (w_1 + \dots + w_{3n})^3 = n^3(n+1)^3$.

Назовём ценой $S(X)$ кубика $X$ сумму чисел во всех кубиках, имеющих с ним общую вершину (включая сам $X$). Тогда в любой окраске, удовлетворяющей требованиям, сумма цен красных кубиков не меньше, чем $\Sigma$. Докажем теперь, что $S(X) \le (n+1)^2 n$ для любого белого кубика $X$. Из этого будет следовать, что в красный цвет надо окрасить не менее, чем $\frac{\Sigma}{(n+1)^2 n} = (n+1)n^2$ кубиков, что и требовалось.

Пусть $(a, b, c)$ — координаты кубика $X$. Абсциссы всех кубиков, имеющих с ним общую вершину, равны $a$ или $a \pm 1$; такое же утверждение верно для остальных координат. Поэтому $S(X) = (w_{a-1} + w_a + w_{a+1})(w_{b-1} + w_b + w_{b+1})(w_{c-1} + w_c + w_{c+1})$, где мы полагаем $w_0 = w_{3n+1} = 0$. Осталось заметить, что $w_{t-1} + w_t + w_{t+1} = n$, если $t \neq 2 \pmod{3}$, иначе $w_{t-1} + w_t + w_{t+1} = n+1$. Поскольку не все координаты $X$ дают остаток $2$, отсюда следует, что $S(X) \le (n+1)^2 n$.