China Team Selection Test

Let $n \geq 2$ be a natural number. Define
$$X = \{ (a_1, a_2, \cdots, a_n) \mid a_k \in \{0, 1, 2, \cdots, k\}, k = 1, 2, \cdots, n \}.$$
For any two elements $s = (s_1, s_2, \cdots, s_n) \in X$ and $t = (t_1, t_2, \cdots, t_n) \in X$, define
$$s \vee t = (\max \{s_1, t_1\}, \max \{s_2, t_2\}, \cdots, \max \{s_n, t_n\} )$$
and
$$s \wedge t = (\min \{s_1, t_1\}, \min \{s_2, t_2\}, \cdots, \min \{s_n, t_n\}).$$
We aim to find the largest possible size of a proper subset $A$ of $X$ such that for any $s, t \in A$, one has $s \vee t \in A$ and $s \wedge t \in A$.

Consider some $A$ with $|A| > (n + 1)! - (n - 1)!$. Call $a = (a_1, a_2, \cdots, a_n) \in X$ interesting if $a_k \ne 0$ for at most one $k$. Let $\mathbf{x}_k$ be the interesting element of $X$ whose $k$th entry equals $k$. We refer to the $\mathbf{x}_i$'s as elementary. Note that if $A$ contains all interesting elements of $X$, then $A$ contains all elements of $X$, because an arbitrary element $(a_1, a_2, \cdots, a_n) \in X$ can be written as
$$(a_1, 0, \cdots, 0) \vee (0, a_2, 0, \cdots, 0) \vee \cdots \vee (0, \cdots, 0, a_n),$$
where the operations are performed in any order. We will in fact prove the stronger statement that if $A$ contains all elementary elements of $X$, then $A$ contains all elements of $X$.

We need the following preliminary result:

Lemma: Fix some $0 \le j \le n$. Then for each $k \ge \max\{1, j\}$, there is an element $a = (a_1, a_2, \cdots, a_n) \in A$ with $a_k = j$.

Proof: Suppose that $A$ does not contain such an element. Then there are at most $k$ choices for the $k$th entry of an element of $A$. Hence,
$$|A| \le (n + 1)!\left(\frac{k}{k + 1}\right) \le (n + 1)!\left(\frac{n}{n + 1}\right) = (n + 1)! - n!,$$
which contradicts our assumption on $|A|$. $\blacksquare$

Now, suppose that $A$ contains all elementary elements of $X$. We will show that $A$ contains all interesting elements of $X$ (and consequently all elements of $X$). Take some interesting $a = (a_1, a_2, \cdots, a_n) \in X$ with possibly $a_k \ne 0$. By the lemma, there exists some $b = (b_1, b_2, \cdots, b_n) \in A$ with $b_k = a_k$. It follows that $a = b \vee \mathbf{x}_k \in A$, as desired.

Therefore, as $A$ is a proper subset of $X$, it follows that $A$ cannot contain all elementary elements. So suppose that $\mathbf{x}_k \not\in A$ for some $0 \le k \le n$. We will find $(n - 1)!$ elements of $X$ that do not belong to $A$, thus contradicting our assumption on $|A|$.

Denote $B = \{a = (a_1, a_2, \cdots, a_n) \in A : a_k = k\}$. Since $\mathbf{x}_k \not\in B$, it follows that for some $j \ne k$, we have $a_j \neq 0$ for all $a \in B$. This is because if there were an element with $a_j = 0$ for each $j$, we could repeatedly apply the $\vee$ operation on said elements to obtain $\mathbf{x}_k$, which is impossible. Hence, there are at most $j$ choices for the $j$th entry of an element in $B$. It follows that for any $a = (a_1, a_2, \cdots, a_n) \in X$ with $a_k = k$ and $a_j = 0$, we have $a \not\in B$ and therefore $a \not\in A$. But there are evidently
$$\frac{(n + 1)!}{(j + 1)(k + 1)} \ge \frac{(n + 1)!}{n(n + 1)} = (n - 1)!$$
elements $a$ of this form. Thus, we have found $(n - 1)!$ elements of $X$ that do not belong to $A$, as needed.

It remains to provide an equality case. Inspired by the above reasoning, we let $A$ contain all elements of $X$ except those of the form $(a_1, a_2, \cdots, a_n)$ with $a_n = n$ and $a_{n - 1} = 0$. It is easy to check that this construction works, because no element of $X$ whose final two entries are $0, n$ can be obtained by applying the $\vee$ or $\wedge$ operation to two elements of $A$. This completes the proof. $\square$

The answer is: $\boxed{(n + 1)! - (n - 1)!}$.