Question 6 In a Mathematical Olympiad, students received scores in four categories: algebra, geometry, number theory, and combinatorics. It is known that no two students have the same scores in all four categories. A group of students is called "good" if these students can be arranged in an order such that their scores in at least two of the four categories are simultaneously increasing. Find the smallest positive integer $N$, such that among any $N$ students, there exists a good group of 10 students.
(2015, Bulgarian Mathematical Olympiad)
Solution 1 The smallest positive integer $N=730$ satisfies the conditions.
First, prove a lemma.
Lemma: A sequence $\left\{a_{n}\right\}$ does not contain a 10-element increasing subsequence if and only if $\left\{a_{n}\right\}$ can be colored with nine colors such that elements of the same color are monotonically decreasing.

Proof: If $\left\{a_{n}\right\}$ is colored with nine colors, and elements of the same color are monotonically decreasing, then any 10-element subsequence of $\left\{a_{n}\right\}$ must contain two elements of the same color, which are decreasing. Therefore, this 10-element subsequence is not increasing. Hence, $\left\{a_{n}\right\}$ does not contain a 10-element increasing subsequence.

If $\left\{a_{n}\right\}$ does not contain a 10-element increasing subsequence, then color the last element of the longest increasing subsequence of length $i$ with color $i$. That is, if $a_{j}$ is colored with color $i$, then there are $i-1$ elements before $a_{j}$ that are smaller than $a_{j}$. Clearly, $1 \leqslant i \leqslant 9$. If $a_{j}$ and $a_{k}$ are both colored with color $i$ and $j < k$, then $a_{k} < a_{j}$; otherwise, there would be at least $i$ elements before $a_{k}$ that are smaller than $a_{k}$, which is a contradiction.
Thus, elements of the same color are monotonically decreasing.
The lemma is proved.
Now, prove that $N=730$ satisfies the conditions.

Let the 730 students be ordered by their algebra scores as $N_{1}, N_{2}, \cdots, N_{730}$. Let $b_{1}, b_{2}, \cdots, b_{730}$ be the number theory scores of $N_{1}, N_{2}, \cdots, N_{730}$.
If $b_{1}, b_{2}, \cdots, b_{730}$ contains a 10-element increasing subsequence, then the conclusion is proved.
Assume $b_{1}, b_{2}, \cdots, b_{730}$ does not contain a 10-element increasing subsequence.
By the lemma, $b_{1}, b_{2}, \cdots, b_{730}$ can be colored with nine colors such that elements of the same color are monotonically decreasing. Therefore, there must be 82 elements of the same color, which are decreasing.
Let the corresponding students be $M_{1}, M_{2}, \cdots, M_{82}$, whose algebra scores are increasing and number theory scores are decreasing.
Let $c_{1}, c_{2}, \cdots, c_{82}$ be the combinatorial scores of $M_{1}, M_{2}, \cdots, M_{82}$.
If $c_{1}, c_{2}, \cdots, c_{82}$ does not contain a 10-element increasing subsequence, then by the lemma, $c_{1}, c_{2}, \cdots, c_{82}$ can be colored with nine colors such that elements of the same color are monotonically decreasing.
Therefore, there must be 10 students whose $c_{i}$ are of the same color, and these $c_{i}$ are increasing.
Let these 10 students be $L_{1}, L_{2}, \cdots, L_{10}$, whose number theory scores are decreasing and combinatorial scores are increasing. Hence, $L_{10}, L_{9}, \cdots, L_{1}$ form a valid group.
Now, show that $N=729$ does not satisfy the conditions.
Assume the algebra scores of 729 students are 0, 1, ..., 728, ordered in increasing sequence. Represent the score $k (0 \leqslant k \leqslant 728)$ in base 9 as $k=(i, j, l)$, where $0 \leqslant i, j, l \leqslant 8$, and satisfy $k=i \times 9^{2}+j \times 9+l$.
Let the number theory score of the student with algebra score $k$ be $n_{k}=f_{12}(k)=(8-i, 8-j, l)$,
the combinatorial score be $c_{k}=f_{13}(k)=(8-i, j, 8-l)$,
and the geometry score be $g_{k}=f_{23}(k)=(i, 8-j, 8-l)$.
First, consider the number theory score $n_{k}=(8-i, 8-j, l)$.
Color the scores with the same third digit with the same color, then all scores can be colored with nine colors, and elements of the same color are decreasing. By the lemma, $\left\{n_{k}\right\}$ does not contain a 10-element increasing subsequence.

Similarly, color the combinatorial scores $c_{k}$ and geometry scores $g_{k}$ with the same second and first digits, respectively. By the above discussion, $\left\{c_{k}\right\}$ and $\left\{g_{k}\right\}$ do not contain a 10-element increasing subsequence.

Additionally, note that $n_{k}, c_{k}, g_{k}$ operate differently on $(i, j, l)$. Observing these three sets of numbers, it is easy to see that there does not exist a 10-element subsequence that is simultaneously decreasing in any two of these sets.
Therefore, $N=729$ does not satisfy the conditions.
In conclusion, $N_{\text {min }}=730$.
Solution 2 First, prove a lemma.
Lemma (Erdos - Szekeres Theorem): Let $m, n$ be positive integers. Then any sequence of $m n+1$ distinct real numbers $a_{1}, a_{2}, \cdots, a_{m n+1}$ must contain an increasing subsequence of length $m+1$ or a decreasing subsequence of length $n+1$.

Proof: Proof by contradiction.
Assume there is neither an increasing subsequence of length $m+1$ nor a decreasing subsequence of length $n+1$.
Let $L\left(a_{i}\right)$ be the maximum length of an increasing subsequence starting with $a_{i}$. Then $L\left(a_{i}\right) \leqslant m (i=1,2, \cdots, m n+1)$.
Thus, there must exist $i_{1}<i_{2}<\cdots<i_{n+1}$ such that $L\left(a_{i_{1}}\right)=L\left(a_{i_{2}}\right)=\cdots=L\left(a_{i_{n+1}}\right)$.
We can prove that $a_{i_{1}}, a_{i_{2}}, \cdots, a_{i_{n+1}}$ form a decreasing subsequence.

Otherwise, there exists $j \in\{1,2, \cdots, n\}$ such that $a_{i_{j}}<a_{i_{j+1}}$. Then the maximum increasing subsequence starting with $a_{i_{j}}$ contains the maximum increasing subsequence starting with $a_{i_{j+1}}$.
Thus, $L\left(a_{i_{j}}\right) \geqslant L\left(a_{i_{j+1}}\right)+1$, which is a contradiction.
Therefore, $a_{i_{1}}, a_{i_{2}}, \cdots, a_{i_{n+1}}$ form a decreasing subsequence, which contradicts the assumption.
The lemma is proved.
Now, prove that $N=730$ satisfies the conditions.
Let $N_{1}, N_{2}, \cdots, N_{730}$ be the students ordered by their algebra scores. Let $b_{1}, b_{2}, \cdots, b_{730}$ be the number theory scores of $N_{1}, N_{2}, \cdots, N_{730}$.
By the lemma, $b_{1}, b_{2}, \cdots, b_{730}$ must contain a 10-element increasing subsequence or an 82-element decreasing subsequence.
If there is a 10-element increasing subsequence, then the conclusion is proved. Otherwise, there must be an 82-element decreasing subsequence. Let the corresponding students be $M_{1}, M_{2}, \cdots, M_{82}$. Then their algebra scores are increasing and number theory scores are decreasing.
Let $c_{1}, c_{2}, \cdots, c_{82}$ be the combinatorial scores of $M_{1}, M_{2}, \cdots, M_{82}$. By the lemma, $c_{1}, c_{2}, \cdots, c_{82}$ must contain a 10-element increasing subsequence or a 10-element decreasing subsequence.

If there is a 10-element increasing subsequence, then the conclusion is proved. Otherwise, there are 10 students among $M_{1}, M_{2}, \cdots, M_{82}$ whose combinatorial scores are increasing.