Let $n>1$ be an integer. An $n \times n \times n$ cube is composed of $n^{3}$ unit cubes. Each unit cube is painted with one color. For each $n \times n \times 1$ box consisting of $n^{2}$ unit cubes (of any of the three possible orientations), we consider the set of the colors present in that box (each color is listed only once). This way, we get $3 n$ sets of colors, split into three groups according to the orientation. It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$, the maximal possible number of colors that are present. (Russia)
Call a $n \times n \times 1$ box an $x$-box, a $y$-box, or a $z$-box, according to the direction of its short side. Let $C$ be the number of colors in a valid configuration. We start with the upper bound for $C$.  Let $\mathcal{C}_{1}, \mathcal{C}_{2}$, and $\mathcal{C}_{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 $\mathcal{C}_{i}$, and denote $n_{i}=\left|M_{i}\right|$.  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. Claim. $4\left|X \cap M_{1}\right|+\left|X \cap M_{2}\right| \leqslant 3 n+1$. Proof. We distinguish two cases. Case 1: $X \cap M_{1} \neq \varnothing$. A cube from $X \cap M_{1}$ should appear in all three boxes $X, Y$, and $Z$, so it should lie in $X \cap Y \cap Z$. Thus $X \cap M_{1}=X \cap Y \cap Z$ and $\left|X \cap M_{1}\right|=1$.  Consider now 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$ (because the cube from $X \cap Y \cap Z$ is in $M_{1}$ ). Let $a$ be some other cube from $X \cap M_{2}$. Recall that there is just one other cube $a^{\prime}$ sharing a color with $a$. But both $Y$ and $Z$ should contain such cube, so $a^{\prime} \in Y \cap Z$ (but $a^{\prime} \notin X \cap Y \cap Z$ ). The map $a \mapsto a^{\prime}$ is clearly injective, so the number of cubes $a$ we are interested in does not exceed $|(Y \cap Z) \backslash X|=n-1$. Thus $\left|X \cap M_{2}\right| \leqslant 2(n-1)+(n-1)=3(n-1)$, and hence $4\left|X \cap M_{1}\right|+\left|X \cap M_{2}\right| \leqslant 4+3(n-1)=3 n+1$. Case 2: $X \cap M_{1}=\varnothing$.  In this case, the same argument applies with several changes. Indeed, $X \cap M_{2}$ contains at most $2 n-1$ cubes from $X \cap Y$ or $X \cap Z$. Any other cube $a$ in $X \cap M_{2}$ corresponds to some $a^{\prime} \in Y \cap Z$ (possibly with $a^{\prime} \in X$ ), so there are at most $n$ of them. All this results in $\left|X \cap M_{2}\right| \leqslant(2 n-1)+n=3 n-1$, which is even better than we need (by the assumptions of our case).  Summing up the inequalities from the Claim over all $x$-boxes $X$, we obtain  $$ 4 n_{1}+n_{2} \leqslant n(3 n+1) $$  Obviously, we also have $n_{1}+n_{2}+n_{3}=n^{3}$. Now we are prepared to estimate $C$. Due to the definition of the $M_{i}$, we have $n_{i} \geqslant i\left|\mathcal{C}_{i}\right|$, so  $$ C \leqslant n_{1}+\frac{n_{2}}{2}+\frac{n_{3}}{3}=\frac{n_{1}+n_{2}+n_{3}}{3}+\frac{4 n_{1}+n_{2}}{6} \leqslant \frac{n^{3}}{3}+\frac{3 n^{2}+n}{6}=\frac{n(n+1)(2 n+1)}{6} $$  It remains to present an example of an appropriate coloring in the above-mentioned number of colors. For each color, we present the set of all cubes of this color. These sets are:  1. $n$ singletons of the form $S_{i}=\{(i, i, i)\}$ (with $1 \leqslant i \leqslant n$ ); 2. $3\binom{n}{2}$ doubletons of the forms $D_{i, j}^{1}=\{(i, j, j),(j, i, i)\}, D_{i, j}^{2}=\{(j, i, j),(i, j, i)\}$, and $D_{i, j}^{3}=$ $\{(j, j, i),(i, i, j)\}$ (with $1 \leqslant i<j \leqslant n)$; 3. $2\binom{n}{3}$ triplets of the form $T_{i, j, k}=\{(i, j, k),(j, k, i),(k, i, j)\}$ (with $1 \leqslant i<j<k \leqslant n$ or $1 \leqslant i<k<j \leqslant n)$.  One may easily see that the $i^{\text {th }}$ boxes of each orientation contain the same set of colors, and that  $$ n+\frac{3 n(n-1)}{2}+\frac{n(n-1)(n-2)}{3}=\frac{n(n+1)(2 n+1)}{6} $$  colors are used, as required.