NMO Selection Tests for BMO and IMO

The required maximum is $n(n+1)(2n+1)/6$ and is achieved, for instance, by colouring cells as described below. For each colour, we list the set of all cells bearing that colour:
* $n$ singletons of the form $\{(i, i, i)\}$, where $1 \le i \le n$;
* $3\binom{n}{2}$ doubletons of the form $\{(i, j, j), (j, i, i)\}$, $\{(j, i, j), (i, j, i)\}$ and $\{(j, j, i), (i, i, j)\}$, where $1 \le i < j \le n$; and
* $2\binom{n}{3}$ triplets of the form $\{(i, j, k), (j, k, i), (k, i, j)\}$, where $1 \le i < j < k \le n$ or $1 \le i < k < j \le n$.

Thus, $Q$ bears exactly $n + 3\binom{n}{2} + 2\binom{n}{3} = n(n+1)(2n+1)/6$ colours, and it is easily seen that the rank $i$ boxes in the three directions all share the same colour set.

We will now show that, under the conditions in the statement, the number of colours $Q$ bears does not exceed $n(n+1)(2n+1)/6$.

Fix such a colouring and split the set $C$ of all colours in $Q$ into three subsets: The set $C_1$ of all colours that appear exactly once, the set $C_2$ of all colours that appear exactly twice, and the set $C_3$ of all colours that appear at least thrice. Let $S_i$ be set of all cells in $Q$ bearing a colour in $C_i$. Since $|S_i| \ge i|C_i|$,
$$\begin{aligned} |C| &= |C_1| + |C_2| + |C_3| \le |S_1| + \frac{1}{2}|S_2| + \frac{1}{3}|S_3| \\ &= \frac{|S_1| + |S_2| + |S_3|}{3} + \frac{4|S_1| + |S_2|}{6} = \frac{n^3}{3} + \frac{4|S_1| + |S_2|}{6}, \end{aligned}$$
and it is therefore sufficient to show that $4|S_1| + |S_2| \le n(3n+1)$.

To this end, we fix a box $X$ of the form $1 \times n \times n$ and prove that $4|X \cap S_1| + |X \cap S_2| \le 3n + 1$. Summing over all such boxes $X$, we get the desired upper bound. Let $Y$ and $Z$ be $n \times 1 \times n$ and $n \times n \times 1$ boxes, respectively, sharing the colour set of $X$.

If $X \cap S_1$ is non-empty, then a cell in this set also lies in both $Y$ and $Z$, hence in $X \cap Y \cap Z$. Consequently, $X \cap S_1 = X \cap Y \cap Z$ and $|X \cap S_1| = 1$.

Consider now the cells in $X \cap S_2$. There are at most $(n-1) + (n-1) = 2(n-1)$ such in the cross $(X \cap Y) \cup (X \cap Z)$, since the cell in $X \cap Y \cap Z$ is in $S_1$. Let now $c$ be any other cell in $X \cap S_2$. Recall that there is only one other cell $c'$ in $Q$ sharing the colour of $c$. Since $Y \cup Z$ does not contain $c$, and $Y$ and $Z$ each contains a cell sharing its colour, it follows that they both contain $c'$. And since the cell in $X \cap Y \cap Z$ is in $S_1$, the cell $c'$ lies in $(Y \cap Z) \setminus X$. The assignment $c \mapsto c'$ is clearly injective, so the number of cells $c$ under current consideration does not exceed $|(Y \cap Z) \setminus X| = n-1$. Consequently, $|X \cap S_2| \le 2(n-1) + (n-1) = 3(n-1)$, and hence $4|X \cap S_1| + |X \cap S_2| \le 4 + 3(n-1) = 3n+1$.

To deal with the case where $X \cap S_1$ is empty, proceed similarly with minor changes. This time $X \cap S_2$ contains at most $2n-1$ cells from the cross $(X \cap Y) \cup (X \cap Z)$. To any other cell $c$ in $X \cap S_2$ there corresponds a cell $c'$ in $Y \cap Z$ (not necessarily outside $X$), so there are at most $n$ such. Consequently, $|X \cap S_2| \le (2n-1) + n = 3n-1$, a wee bit better than needed.