Problem 2

Let $a_{1}, a_{2}, \ldots, a_{n}$ be a finite sequence of natural numbers. Its subsequences are sequences of the form $a_{i}, a_{i+1}, \ldots, a_{j}$ such that $1 \leqslant i \leqslant j \leqslant n$. Two subsequences are equal if they have the same length and are composed of the same terms; in other words, the subsequences $a_{i}, a_{i+1}, \ldots, a_{j}$ and $a_{u}, a_{u+1}, \ldots, a_{v}$ are considered equal if and only if $j-i=v-u$ and $a_{i+k}=a_{u+k}$ for all integers $k$ such that $0 \leqslant k \leqslant j-i$. Finally, a subsequence $a_{i}, a_{i+1}, \ldots, a_{j}$ is said to be palindromic if it reads the same way in both directions, that is, if $a_{i+k}=a_{j-k}$ for all integers $k$ such that $0 \leqslant k \leqslant j-i$.

What is the largest number of distinct palindromic subsequences that such a sequence of length $n$ can contain?

## §
Solution

First, if $a_{1}=a_{2}=\ldots=a_{n}=0$, all subsequences formed of $k$ consecutive zero terms are indeed palindromic subsequences, regardless of the integer $k \leqslant n$. A sequence of length $n$ can therefore contain $n$ distinct palindromic subsequences.

Conversely, let us prove that it cannot contain more than $n$ distinct subsequences. To do this, given a palindromic subsequence $\mathbf{a}=a_{i}, \ldots, a_{j}$, we call the origin of $\mathbf{a}$ the largest integer $s$ such that $\mathbf{a}$ coincides with the subsequence $a_{s}, \ldots, a_{s+j-i}$.

We then prove that any integer is the origin of at most one palindromic subsequence. Indeed, if $s$ is the origin of two palindromic subsequences $\mathbf{a}$ and $\mathbf{a}^{\prime}$ of lengths $\ell<\ell^{\prime}$ respectively, let $s^{\prime}=s+\ell^{\prime}-\ell$. Then, for any integer $k$ such that $0 \leqslant k \leqslant \ell$, we observe that

$$
a_{s^{\prime}+k}=a_{s+\ell^{\prime}-\ell+k}=a_{s+\ell-k}=a_{s+k}
$$

This means that the sequence $a_{s^{\prime}}, \ldots, a_{s^{\prime}+\ell}$ coincides with the sequence $\mathbf{a}^{\prime}$, which contradicts the fact that $s$ is the origin of $\mathbf{a}^{\prime}$. Therefore, the sequence $a_{1}, \ldots, a_{n}$ contains at most $n$ palindromic subsequences.