Theme and Variations

Hi, it's Choo Ray. Recently, I visited a SIMO National Team training session to soak in the atmosphere and meet some young friends. The session was about sequences and had quite a few interesting questions, so it was a pity that attendance was low (coincidentally many students were involved in the National Olympiad in Informatics). Today I would like to highlight a particular question that intrigued me and discuss some variations.

Full Score

For those of you looking for a challenge, I will list all variations here.

Sequences, Example 2.3
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive integers.
Prove that there exist different indices, $r,s,t$ such that $a_r \ge a_s \ge a_t$ and $b_r \ge b_s \ge b_t$ and $c_r \ge c_s \ge c_t$.

Variation 1: Distinct positive integers
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of distinct positive integers.
Prove that there exist different indices, $r,s,t$ such that $a_r \ge a_s \ge a_t$ and $b_r \ge b_s \ge b_t$ and $c_r \ge c_s \ge c_t$.

Variation 2: Infinite indices, increasing
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive integers.
Does there always exist different indices, $\lambda_1,\lambda_2,\lambda_3,...$ such that
$a_{\lambda_1} \le a_{\lambda_2} \le a_{\lambda_3} \le ...$ and
$b_{\lambda_1} \le b_{\lambda_2} \le b_{\lambda_3} \le ...$ and
$c_{\lambda_1} \le c_{\lambda_2} \le c_{\lambda_3} \le ...$ ?

Variation 3: Infinite indices, decreasing
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive integers.
Does there always exist different indices, $\lambda_1,\lambda_2,\lambda_3,...$ such that
$a_{\lambda_1} \ge a_{\lambda_2} \ge a_{\lambda_3} \ge ...$ and
$b_{\lambda_1} \ge b_{\lambda_2} \ge b_{\lambda_3} \ge ...$ and
$c_{\lambda_1} \ge c_{\lambda_2} \ge c_{\lambda_3} \ge ...$ ?

Variation 4: Positive reals
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive reals.
Does there always exist different indices $r,s,t$ such that $a_r \ge a_s \ge a_t$ and $b_r \ge b_s \ge b_t$ and $c_r \ge c_s \ge c_t$?

Variation 5: Infinitely many sequences
$\forall i\in \Z^+$, let $a_{i,1},a_{i,2},...$ be an infinite sequence of positive integers.
Does there always exist different indices, $r,s,t$ such that
$\forall i\in \Z^+, a_{i,r} \ge a_{i,s} \ge a_{i,t}$?

For those of you who just want to enjoy the show, read on! Before we get to the solution, let us see how a 2-time IMO medallist from Singapore managed to fake-solve this problem.

Simplification

After pushing through some algebraic manipulation in the first two examples, I must have been overexcited at seeing a question that did not involve any complicated recurrence formulae. On autopilot, I thought of the following line of reasoning:

Set $t=1$. There are only finitely many positive integers below $a_1$, therefore after some point these will no longer appear and the remaining terms are all larger, that is, $\exists N_a, \forall n\ge N_a, a_n> a_1$ We can repeat this argument for the other sequences, so analagously $\exists N_b, \forall n\ge N_b, b_n>b_1$ $\exists N_c, \forall n\ge N_c, c_n>c_1$ Therefore, taking $s=max(N_a,N_b,N_c)$, we have simultaneously $a_s>a_1$ and $b_s>b_1$ and $c_s>c_1$.

Now we can repeat this setup. For sufficiently large $m$ the terms smaller than $a_s$ will no longer appear, so that $\exists M_a, \forall m\ge M_a, a_m>a_s$ and similar for $b,c$. Then take $r=max(M_a,M_b,M_c)$. So $a_r>a_s>a_t$ and $b_r>b_s>b_t$ and $c_r>c_s>c_t$ as desired.

Of course, the eagle-eyed among you will have spotted that the very first line is already wrong. Just because there are finitely many positive integers below $a_1$ does not mean that they appear finitely many times, since some term can repeat infinitely! I got a nasty surprise towards the end of the session when I saw Xinyue write the word "constant" on the board, which sounded off countless alarm bells in my head.

However, the logic is otherwise sound and solves the following variation:

Variation 1: Distinct positive integers
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of distinct positive integers.
Prove that there exist different indices, $r,s,t$ such that $a_r \ge a_s \ge a_t$ and $b_r \ge b_s \ge b_t$ and $c_r \ge c_s \ge c_t$.

Returning to the Main Theme

To fix the solution above, we have to investigate further what happens when things are not as first expected. So what does happen when terms smaller than $a_1$ do not "run out"? Then at least one of these terms must appear infinitely many times. We can formulate this observation as a useful lemma:

Lemma: In a sequence of positive integers $\{x_n\}$, there must exist either an infinite constant subsequence or an infinite strictly increasing subsequence (possibly both).
Therefore there exists an infinite increasing subsequence. (Here subsequence means that we choose some subset of the terms but preserve the order of terms.)

Proof: If some term repeats infinitely many times, we get an infinite constant subsequence.
So now suppose that each term can only appear finitely many times. We will construct a strictly increasing subsequence $\{y_n\}$ from terms of $\{x_n\}$.
Let $y_1=x_1$. Now the integers $1,2,\cdots,y_1$ each appear finitely many times in $\{x_n\}$, so there is a last occurrence of these integers. So taking a term past this last occurence, we have some $i$ with $x_i>y_1$.
Take $y_2=x_i$. Repeating the argument, integers $1,2,\cdots,y_2$ each appear finitely many times in $\{x_n\}$, so there is a last occurrence of these integers. Take a term past this last occurrence, we have some $j$ with $x_j>y_2$. Note also that $j>i$ since to go past the last occurrence we must pass $a_i$ itself, so our chosen elements are in the right order.
Now set $y_3=x_j$. We can repeat this argument inductively to construct the infinite strictly increasing subsequence $\{y_n\}$.

Great, but now there is a little trap when we try to combine information from the three different sequences $\{a_n\}, \{b_n\}, \{c_n\}$. Unlike in Variation 0 where we had the luxury of finding $N_a,N_b,N_c$, then setting $s$ to be the maximum, here if we choose subsequences from each sequence, we have no guarantee that the subsequences overlap at all!

To get around this, the trick is to "pass to a subsequence". The idea is that we first consider the sequence $\{a_n\}$ only. We build an infinite strictly increasing subsequence out of its terms and discard all the remaining terms, simultaneously discarding the correspondingly-indexed terms in sequences $\{b_n\},\{c_n\}$. It is also usual practice to re-index the terms, so that the subsequences keep the names of the original sequences (so we can now refer to the first 3 terms of the $a$-subsequence as $a_1, a_2, a_3$ instead of something like $a_{\lambda_1},a_{\lambda_2},a_{\lambda_3}$).

By doing this, we have essentially converted the first sequence to become increasing, while imposing no extra conditions on the second and third. Then it is easy to see that we can apply the same argument, working on the second sequence, so that by passing to a subsequence, now both the first and second sequences are increasing. Applying the argument one last time to the third sequence makes all three sequences increasing. This solves the original problem and we also get the following for free:

Variation 2: Infinite indices, increasing
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive integers.
Does there always exist different indices, $\lambda_1,\lambda_2,\lambda_3,...$ such that
$a_{\lambda_1} \le a_{\lambda_2} \le a_{\lambda_3} \le ...$ and
$b_{\lambda_1} \le b_{\lambda_2} \le b_{\lambda_3} \le ...$ and
$c_{\lambda_1} \le c_{\lambda_2} \le c_{\lambda_3} \le ...$ ? Yes!

Easy Variations

For finitely many indices, flipping the direction of the signs makes no difference since we can simply flip the order of finitely many $\lambda$s. However, for infinite indices, it may matter.

Variation 3: Infinite indices, decreasing
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive integers.
Does there always exist different indices, $\lambda_1,\lambda_2,\lambda_3,...$ such that
$a_{\lambda_1} \ge a_{\lambda_2} \ge a_{\lambda_3} \ge ...$ and
$b_{\lambda_1} \ge b_{\lambda_2} \ge b_{\lambda_3} \ge ...$ and
$c_{\lambda_1} \ge c_{\lambda_2} \ge c_{\lambda_3} \ge ...$ ?

We will quickly realise that it is much harder to construct an infinite decreasing sequence, since now "running out of options" is a very real possibility. Indeed, for a simple counterexample, if we pick the sequence $a_n=n$, then once we pick $\lambda_1$, we only have $\lambda_1$ terms that do not exceed it, so there is no way we can construct an infinite decreasing sequence.

Variation 4: Positive reals
Let $a_1,a_2,...$ and $b_1,b_2,...$ and $c_1,c_2,...$ be three arbitrary infinite sequences of positive reals.
Does there always exist different indices $r,s,t$ such that $a_r \ge a_s \ge a_t$ and $b_r \ge b_s \ge b_t$ and $c_r \ge c_s \ge c_t$?

A key component of our proof for the main problem is that there are finitely many "small" positive integers. So changing it to reals should violate this property. Does it still hold in this case? We can observe that a counterexample is given by picking the sequences $a_n=n$, $b_n=\frac{1}{n}$. One sequence is strictly increasing and the other is strictly decreasing, so for any two indices $r,s$ we must have either $a_r>a_s$ or $b_r>b_s$. Note that this counterexample works for positive rationals, and we can use the increasing/decreasing idea to give a similar counterexample for (not necessarily positive) integers in general.

A Harder Variation

We have seen that the original problem naturally extends to having infinite indices. What about having infinitely many sequences?

Variation 5: Infinitely many sequences
$\forall i\in \Z^+$, let $a_{i,1},a_{i,2},...$ be an infinite sequence of positive integers.
Does there always exist different indices, $r,s,t$ such that
$\forall i\in \Z^+, a_{i,r} \ge a_{i,s} \ge a_{i,t}$?

I posed this question to the participants with whom I had travelled to IMO 2024 last year towards the end of the session. They were in the midst of predicting topics for the IMO 2025 national team selection test in a few weeks, seemingly confident with the session material already. I asked if they thought the answer to this variation were yes or no.

Initially, they were noncommittal in their answers. When I returned a few minutes later and asked the same question, one of them had come up with the following line of reasoning:

The proof in the original question involves examinining the first sequence and passing to a subsequence, then doing the same for the second and third sequences. So we should be able to extend this process infinitely.

This seemed to sway the opinion of the others. Certainly, we can inductively extend the proof to work with any finite number of sequences and it is now quite conceivable that extending infinitely it would be possible to find $r,s,t$ that satisfies the conditions for all infinitely many sequences. The vote was now majority "Yes".

With a slight smirk on my face, I walked up to the whiteboard and presented the following:

Counterexample:
Let $a_{i,j} = j+1$ when $i\ne j$ and let $a_{i,i}=1$
i.e. we have the sequences
1,3,4,5,6,7,...
2,1,4,5,6,7,...
2,3,1,5,6,7,...
2,3,4,1,6,7,... ...
This makes $a_{i,i}$ the lowest terms in their sequence. In particular, for any $i\le j$, we have $a_{i,i}\lt a_{i,j}$ but $a_{j,i}\gt a_{j,j}$ also! Therefore, no $r,s,t$ will work.

So it is actually much trickier to extend inductive arguments to the infinite then we might intuitively expect!

The Value of Variations

You might realise that my counterexample uses distinct positive integers when we could have easily replaced all the terms that are not 1 with 2. In fact, I thought of this variation even before I realised my original solution was wrong!

Working on variations has been a skill that I have been focusing on recently. When I entered university, I received advice that when I encounter a theorem, I should enhance my understanding by examining why each condition is useful and go through the exercise of modifying conditions and providing proofs/counterexamples for each variation.

For the last variation I discussed today, I was aided by having solved similar variations of analysis problems a few months ago (e.g. if I have a finite number of convergent sequences their termwise maximums will tend to the maximum of their limits, but this is not necessarily true for infinite sequences even if the infinite maximums exist). The central idea is that with finitely many sequences, the "well-behaved" region can only shrink by a finite amount with each additional sequence, but with infinitely many sequences we can now shrink it infinitely many times and we can engineer it such that we end up with no well-behaved region whatsoever.

When developing variations, there is sometimes a worry that we may end up with a problem we do not have the tools to solve. However, I believe this is the very essence of mathematics! It is a skill in itself to know what problems are worth pursuing, and many great mathematical stories and tools come from trying to extend existing theory (e.g. quadratic formula -> solving the cubic -> impossibility of the quintic). On the flip side, most variations are probably simple to solve from modifying the original proof and these exercises are valuable to familiarise ourselves with existing tools.

So, start composing your own variations today!