Bulgarian National Mathematical Olympiad

Answer: 730.

Lemma. A sequence $A=a_1,a_2,\dots ,a_k$ consisting of distinct numbers does not possess 10 term increasing subsequence if and only if its terms can be colored in 9 colors such that the members of one and the same color from a decreasing sequence.

Proof. First, assume that such a coloring exists. Any 10-term subsequence of $A$ contains two terms colored in the same way. Hence, the sequence is not increasing.

Suppose now, $A$ does not contain 10-term increasing subsequence. Color in color $i$ any term $a$ of $A$ such that the longest increasing subsequence of $A$, having $a$ as its last element, has length $i$. It is easy to see that this coloring has the desired properties. This completes the proof of the Lemma.

We prove that among any 730 students there exist 10 that form a nice sequence.

Let $M_1,M_2,\dots ,M_{730}$ be a sequence in which the students are ordered in increasing order according to their algebra marks. Let $a_i$ be the geometry mark of $M_i$. If the sequence $a_1,a_2,\dots ,a_{730}$ has 10-term subsequence then we have a nice sequence.

In the opposite case according to the Lemma we color all students in 9 colors such that the geometry marks for any color form a decreasing subsequence. There exist at least 82 students having the same color. Let $N_1,N_2,\dots ,N_{82}$ be of the same color and they are ordered in increasing order for algebra marks and decreasing order for geometry marks.

Let $b_i$ be number theory mark for $N_i$. If the sequence $b_1,b_2,\dots ,b_{82}$ has 10-term decreasing subsequence, then we have the desired nice sequence. In the opposite case we can color students $N_1,N_2,\dots ,N_{82}$ in 9 colors such that number theory marks for any color to form increasing sequence. We have at least 10 students of the same color and they from nice subsequence with their marks in algebra and number theory.

It remains to show an example of 729 students without 10-term nice subsequence.

Let $k$ be an integer between 0 and 728. For $0\le i<j\le 2$ denote by $f_{ij}(k)$ the integer from representation of $k$ in base 9 when the digits in $i$-th and $j$-th place are replaced by their compliments to 8. (If $k\le 80$ then we add 0's to the left.)

Consider 729 students with algebra marks 0, 1, ..., 728 and the student of mark $k$ has geometry mark $f_{01}(k)$, number theory mark $-f_{02}(k)$, and combinationics mark $-f_{12}(k)$.

It is clear that for any two areas there exist two numbers $0\le i<j\le 2$, such that for any student one of the marks for these two areas is obtained from the other through the function $f_{ij}$.

We prove that a 10-term nice sequence for algebra and geometry does not exist. For remaining pairs the proof is the same.

Let $M_1,M_2,\dots ,M_{729}$ be the sequence in increasing order according to algebra marks. Let $a_i$ be the geometry mark of $M_i$. It suffices to show that a 10-term increasing subsequence of $a_1,a_2,\dots ,a_{729}$ does not exist.

For any $i$ color $a_i$ in color $s$ where $s$ is the second digit of the representation of base 9 of $a_i$. It is easy to see that any monochromatic subsequence of $a_1,a_2,\dots ,a_{729}$ is decreasing. Hence, according to the Lemma, the proof is complete.