, 2018

The maximal number is $\frac{n(n+1)(2n+1)}{6}$.

Call a $n \times n \times 1$ box an x-box, an y-box, or a z-box according to its orientation.
Let $N$ be the number of colors in a valid configuration. We start with the upper bound for $N$.

Let $D_1, D_2$ and $D_3$ be the sets of colors which appear in the big cube exactly once, exactly twice, and at least thrice, respectively. Let $M_i$ be the set of unit cubes whose colors are in $D_i$, and denote $n_i = |M_i|$.

Consider any x-box $X$, and let $Y$ and $Z$ be a y- and a z-box containing the same set of colors as $X$ does. Let us first prove that

Claim: $4|X \cap M_1| + |X \cap M_2| \le 3n + 1$.

Proof: We distinguish two cases.

Case 1: $X \cap M_1 \neq \emptyset$

A cube from $X \cap M_1$ should appear in all three boxes $X$, $Y$ and $Z$ (since that color only appears once), so it should lie in $X \cap Y \cap Z$. Thus, $X \cap M_1 = X \cap Y \cap Z$, and thus $|X \cap M_1| = 1$.

Now consider the cubes in $X \cap M_2$. There are at most $2(n-1)$ of them lying in $X \cap Y$ or $X \cap Z$ (since the cube from $X \cap Y \cap Z$ is in $M_1$). Let $a$ be a cube from $X \cap M_2$ that is NOT in $Y$ or $Z$. Since $a \in M_2$, there is exactly one other cube $a'$ sharing the color with $a$. But since $a$ is in $X$ but not in $Y$ or $Z$, $Y$ and $Z$ must both contain $a'$, that is $a' \in (Y \cap Z) - X$. In addition, since $a \to a'$ is clearly injective, the number of cubes $a$ above would not exceed $|(Y \cap Z) - X| = n-1$. Combining all of the above, we have

$$|X \cap M_2| \leq |X \cap M_2 \cap (Y \cup Z)| + |X \cap M_2 - (Y \cup Z)| \leq 2(n-1) + (n-1) = 3(n-1).$$

Easy check shows that Claim holds.

Case 2: $X \cap M_1 = \emptyset$

In this case, the same argument applies with several changes. Indeed, $X \cap M_2$ now contains at most $2n-1$ cubes from $X \cap Y$ or $X \cap Z$. Any other cube $a$ in $X \cap M_2$ corresponds to some $a' \in Y \cap Z$, possibly with $a' \in X$, so there are at most $|Y \cap Z| = n$ of them. All this results in $|X \cap M_2| \leq (2n-1)+n = 3n-1$. Easy check shows that Claim holds.

Summing up Claim over all $x$-boxes $X$, we get

$$4n_1 + n_2 \leq n(3n + 1).$$

Obviously, we also have $n_1 + n_2 + n_3 = n^3$.

Now we are prepared to estimate $N$. Due to the definition of $M_i$, we have $n_i \geq i|D_i|$, so

$$\begin{aligned} N &\leq n_1 + \frac{n_2}{2} + \frac{n_3}{3} = \frac{n_1 + n_2 + n_3}{3} + \frac{4n_1 + n_2}{6} \\ &\leq \frac{n^3}{3} + \frac{3n^2 + n}{6} = \frac{n(n+1)(2n+1)}{6}. \end{aligned}$$

It remains to present an example that reaches this upper bound. Color each set with a different color to provide the desired example.

(i) $n$ sets of the form $\{(i, i, i)\}$ ($1 \le i \le n$);

(ii) $C_2^n$ sets of the form $\{(i, j, j), (j, i, i)\}$, $C_2^n$ sets of the form $\{(j, i, j), (i, j, i)\}$, and $C_2^n$ sets of the form $\{(j, j, i), (i, i, j)\}$ ($1 \le i < j \le n$);

(iii) $C_3^n$ sets of the form $\{(i, j, k), (j, k, i), (k, i, j)\}$ with $1 \le i < j < k \le n$, and $C_3^n$ sets of the form $\{(i, j, k), (j, k, i), (k, i, j)\}$ with $1 \le i < k < j \le n$.